Choosing Samples to Compute Heuristic-Strategy Nash Equilibrium

DSpace/Manakin Repository

Choosing Samples to Compute Heuristic-Strategy Nash Equilibrium

Citable link to this page

. . . . . .

Title: Choosing Samples to Compute Heuristic-Strategy Nash Equilibrium
Author: Walsh, William E.; Parkes, David C.; Das, Rajarshi

Note: Order does not necessarily reflect citation order of authors.

Citation: Walsh, William E., David C. Parkes, and Rajarshi Das. 2004. Choosing samples to compute Heuristic-Strategy Nash Equilibrium. In Agent-mediated electronic commerce V: Designing mechanisms and systems, ed. P. Faratin, et al., 109-123. New York, NY: Springer. Previously published in Lecture Notes in Computer Science 3048: 109-123.
Access Status: At the direction of the depositing author this work is not currently accessible through DASH.
Full Text & Related Files:
Abstract: Auctions define games of incomplete information for which it is often too hard to compute the exact Bayesian-Nash equilibrium. Instead, the infinite strategy space is often populated with heuristic strategies, such as myopic best-response to prices. Given these heuristic strategies, it can be useful to evaluate the strategies and the auction design by computing a Nash equilibrium across the restricted strategy space. First, it is necessary to compute the expected payoff for each heuristic strategy profile. This step involves sampling the auction and averaging over multiple simulations, and its cost can dominate the cost of computing the equilibrium given a payoff matrix. In this paper, we propose two information theoretic approaches to determine the next sample through an interleaving of equilibrium calculations and payoff refinement. Initial experiments demonstrate that both methods reduce error in the computed Nash equilibrium as samples are performed at faster rates than naive uniform sampling. The second, faster method, has a lower metadeliberation cost and better scaling properties. We discuss how our sampling methodology could be used within experimental mechanism design.
Published Version: doi:10.1007/b99040
Other Sources: http://www.eecs.harvard.edu/econcs/pubs/sampling_long.pdf
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:4686810

Show full Dublin Core record

This item appears in the following Collection(s)

  • FAS Scholarly Articles [7594]
    Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
 
 

Search DASH


Advanced Search
 
 

Submitters