Yevgeniy Vorobeychik
Michael P. Wellman
ABSTRACT
We define the class of games called simulation-based games, in which the payoffs are available as an output of an oracle (simulator), rather than specified analytically or using a payoff matrix. We then describe a convergent algorithm based on a hierarchical application of simulated annealing for estimating Nash equilibria in simulation-based games with finite-dimensional strategy sets. Additionally, we present alternative algorithms for best response and Nash equilibrium estimation, with a particular focus on one-shot infinite games of incomplete information. Our experimental results demonstrate that all the approaches we introduce are efficacious, albeit some more so than others. We show, for example, that while iterative best response dynamics has relatively weak convergence guarantees, it outperforms our convergent method experimentally. Additionally, we provide considerable evidence that a method based on random search outperforms gradient descent in our setting.
- B. Blum, C. R. Shelton, and D. Koller. A continuation method for Nash equilibria in structured games. Journal of Artificial Intelligence Research, 25:457--502, 2006. Google Scholar
Digital Library
- P. Cramton, Y. Shoham, and R. Steinberg, editors. Combinatorial Auctions. The MIT Press, 2006. Google ScholarDigital Library
- D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1991.Google Scholar
- A. Ghate and R. L. Smith. Adaptive search with stochastic acceptance probabilities for global optimization. draft, 2006.Google Scholar
- J. Kiefer and J. Wolfowitz. Stochastic estimation of the maximum of a regression function. Annals of Mathematical Statistics, 23(3):462--466, 1952.Google ScholarCross Ref
- V. Krishna. Auction Theory. Academic Press, 1st edition, 2002.Google Scholar
- R. D. McKelvey, A. M. McLennan, and T. L. Turocy. Gambit: Software tools for game theory, version 0.2005.06.13, 2005.Google Scholar
- P. Milgrom and J. Roberts. Rationalizability, learning, and equilibrium in games with strategic complementarities. Econometrica, 58(6):1255--1277, 1990.Google ScholarCross Ref
- D. Monderer and L. S. Shapley. Potential games. Games and Economics Behavior, 14:124--143, 1996.Google ScholarCross Ref
- D. M. Reeves and M. P. Wellman. Computing best-response strategies in infinite games of incomplete information. In Twentieth Conference on Uncertainty in Artificial Intelligence, pages 470--478, 2004. Google ScholarDigital Library
- J. C. Spall. Introduction to Stochastic Search and Optimization. John Wiley and Sons, Inc, 2003. Google ScholarDigital Library
- Y. Vorobeychik, D. M. Reeves, and M. P. Wellman. Constrained automated mechanism design for infinite games of incomplete information. In The Twenty-Third Conference on Uncertainty in Artificial Intelligence, pages 400--407, 2007.Google ScholarDigital Library
Index Terms
- Stochastic search methods for nash equilibrium approximation in simulation-based games
Recommendations
Stochastic Nash equilibrium problems: sample average approximation and applications
This paper presents a Nash equilibrium model where the underlying objective functions involve uncertainty and nonsmoothness. The well-known sample average approximation method is applied to solve the problem and the first order equilibrium conditions ...
Nash equilibrium based fairness
GameNets'09: Proceedings of the First ICST international conference on Game Theory for NetworksThere are several approaches of sharing resources among users. There is a noncooperative approach wherein each user strives to maximize its own utility. The most common optimality notion is then the Nash equilibrium. Nash equilibria are generally Pareto ...
Searching for approximate equilibria in empirical games
AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2When exploring a game over a large strategy space, it may not be feasible or cost-effective to evaluate the payoff of every relevant strategy profile. For example, determining a profile payoff for a procedurally defined game may require Monte Carlo ...
Comments