Choosing Samples to Compute Heuristic-Strategy Nash Equilibrium

By William E. Walsh, D. Parkes, Rajarshi Das. 2003

65 citations recorded by the source corpus.

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.

Subfields: Management Information Systems, Management Science and Operations Research, Marketing, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Information Systems

In Management Science and Operations Research

In Marketing

In Game & Decision Theory

Citations in the corpus

OpenSpiel: A Framework for Reinforcement Learning in Games (2019, background): “Visualization of Evolutionary and Policy Learning Dynamics One common visualization tool in the multiagent learning literature (especially in games) is a phase portrait that shows a vector field and/or trajectories of particle the depict local changes to the policy under specific update dynamics [64”
A Generalised Method for Empirical Game Theoretic Analysis (2018, background): “Works by Walsh et al. [14, 15] and Wellman et al. [16], have shown the great potential of using heuristic strategies and empirical game theory to examine such interactions at a higher meta-level, instead of trying to capture the decision-making processes at the level of the atomic actions involved.”
α-Rank: Multi-Agent Evaluation by Evolution (2019, background): “The purpose of the first applications of EGTA was to reduce the complexity of large economic problems in electronic commerce, such as continuous double auctions, supply chain management, market games, and automated trading [6, 7, 71, 72].”
Methods for empirical game-theoretic analysis (extended abstract) (2006, background): “Walsh et al. (2003) have proposed information-theoretic criteria for selecting profiles to sample, and other approaches from Monte Carlo analysis and active learning should be applicable as well.”
Actor-Critic Policy Optimization in Partially Observable Multiagent Environments (2018, background): “These analyses are common in multiagent learning as they allow visual depiction of the policy changes and how different factors affect the (convergence) behavior [83, 92, 13, 91, 11, 94, 1, 99, 98, 8, 89].”
Re-evaluating evaluation (2018, methodology): “We also draw on empirical game theory [52,53], by using a meta-game to “evaluate evaluations”, see section 4.”
Methods for Empirical Game-Theoretic Analysis (2006, background): “Walsh et al. (2003) have proposed information-theoretic criteria for selecting profiles to sample, and other approaches from Monte Carlo analysis and active learning should be applicable as well.”