Stochastic search methods for nash equilibrium approximation in simulation-based games

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Stochastic search methods for nash equilibrium approximation in simulation-based games

Full text

Pdf (727 KB)

Source

International Conference on Autonomous Agents archive
Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2 table of contents

Estoril, Portugal

SESSION: Economic paradigms table of contents

Pages 1055-1062

Year of Publication: 2008

ISBN:978-0-9817381-1-6

Authors

Yevgeniy Vorobeychik	University of Michigan, Ann Arbor, MI
Michael P. Wellman	University of Michigan, Ann Arbor, MI

Sponsors

AAAI : Association for the Advancement of Artifical Intelligence
ACM: Association for Computing Machinery

Publisher

International Foundation for Autonomous Agents and Multiagent Systems Richland, SC

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 62, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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.
	2	Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
	3	D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1991.
	4	A. Ghate and R. L. Smith. Adaptive search with stochastic acceptance probabilities for global optimization. draft, 2006.
	5	J. Kiefer and J. Wolfowitz. Stochastic estimation of the maximum of a regression function. Annals of Mathematical Statistics, 23(3):462--466, 1952.
	6	V. Krishna. Auction Theory. Academic Press, 1st edition, 2002.
	7	R. D. McKelvey, A. M. McLennan, and T. L. Turocy. Gambit: Software tools for game theory, version 0.2005.06.13, 2005.
	8	P. Milgrom and J. Roberts. Rationalizability, learning, and equilibrium in games with strategic complementarities. Econometrica, 58(6):1255--1277, 1990.
	9	D. Monderer and L. S. Shapley. Potential games. Games and Economics Behavior, 14:124--143, 1996.
	10	Daniel M. Reeves , Michael P. Wellman, Computing best-response strategies in infinite games of incomplete information, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.470-478, July 07-11, 2004, Banff, Canada
	11	James C. Spall, Introduction to Stochastic Search and Optimization, John Wiley & Sons, Inc., New York, NY, 2003
	12	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.