Proceedings

Generalised Fictitious Play for a Continuum of Anonymous Players

Download BibTeX Cite

Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 245-249.

© 2009 International Joint Conferences on Artificial Intelligence

Abstract

Recently, efficient approximation algorithms for finding Nash equilibria have been developed for the interesting class of anonymous games, where a player's utility does not depend on the identity of its opponents. In this paper, we tackle the problem of computing equilibria in such games with continuous player types, extending the framework to encompass settings with imperfect information. In particular, given the existence result for pure Bayes-Nash equilibiria in these games, we generalise the fictitious play algorithm by developing a novel procedure for finding a best response strategy, which is specifically designed to deal with continuous and, therefore, infinite type spaces. We then combine the best response computation with the general fictitious play structure to obtain an equilibrium. To illustrate the power of this approach, we apply our algorithm to the domain of simultaneous auctions with continuous private values and discrete bids, in which the algorithm shows quick convergence.Zinovi Rabinovich, Enrico Gerding, Maria Polukarov, Nicholas R. Jennings

  1. M. Blonski. Equilibrium characterization in large anonymous games. Working paper, University of Manheim, 2001.
  2. G. W. Brown. Iterative solutions of games by fictitious play. In Activity Analysis of Production and Allocation. Wiley, 1951.
  3. C. Daskalakis and C. H. Papadimitriou. Computing equilibria in anonymous games. In FOCS, 2007.
  4. E. H. Gerding, R. K. Dash, D. C. K. Yuen, and N. R. Jennings. Bid- ding optimally in concurrent second-price auctions of perfectly substitutable goods. In AAMAS, pages 267-274, 2007.
  5. E. H. Gerding, Z. Rabinovich, A. Byde, E. Elkind, and N.R. Jen- nings. Approximating mixed nash equilibria using smooth ficti- tious play in simultaneous auctions. In AAMAS, 2008.
  6. P. R. Jordan, Y. Vorobeychik, and M. P. Wellman. Searching for approximate equilibria in empirical games. In AAMAS, 2008.
  7. M. A. Khan, K. P. Rath, and Y. Sun. On the existence of pure strategy equilibria in games with a continuum of players. J. of Economic Theory, 76(1):13-46, 1997.
  8. A. Mas-Colell. On a theorem of Schmeidler. J. of Mathematical Economics, 13:201-206, 1984.
  9. D. Monderer and L. S. Shapley. Fictitious play property for games with identical interests. J. of Economic Theory, 68(1):258-265, 1996.
  10. R. Radner and R. W. Rosenthal. Private information and pure- strategy equilibria. Mathematics of Operations Research, 7(3):401-409, 1982.
  11. K. P. Rath, Y. Sun, and S. Yamashige. The nonexistence of symmet- ric equilibria in anonymous games with compact action spaces. J. of Mathematical Economics, 24:331-346, 1995.
  12. D. M. Reeves and M. P. Wellman. Computing best-response strate- gies in infinite games of incomplete information. In UAI, 2004.
  13. D. Schmeidler. Equilibrium points of nonatomic games. J. of Statis- tical Physics, 7(4):295-300, 1973.
  14. J. von Neumann and G. W. Brown. Solutions of games by differ- ential equations. In Contributions to the Theory of Games, pages 73-79. Princeton University Press, 1950.
  15. E. Vorobeychik and M. P. Wellman. Stochastic search methods for Nash equilibrium approximation in simulation-based games. In AAMAS, pages 1055-1062, 2008.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards