publication . Other literature type . Preprint . Article . 2018

Empirical Centroid Fictitious Play: An Approach for Distributed Learning in Multi-Agent Games

Swenson, Brian; Soummya Kar; Joao Xavier;
  • Published: 01 Jan 2018
  • Publisher: Figshare
Abstract
The paper is concerned with distributed learning in large-scale games. The well-known fictitious play (FP) algorithm is addressed, which, despite theoretical convergence results, might be impractical to implement in large-scale settings due to intense computation and communication requirements. An adaptation of the FP algorithm, designated as the empirical centroid fictitious play (ECFP), is presented. In ECFP players respond to the centroid of all players' actions rather than track and respond to the individual actions of every player. Convergence of the ECFP algorithm in terms of average empirical frequency (a notion made precise in the paper) to a subset of t...
Subjects
arXiv: Computer Science::Computer Science and Game Theory
free text keywords: Computer Engineering, 90699 Electrical and Electronic Engineering not elsewhere classified, Mathematics - Optimization and Control, Computer Science - Computer Science and Game Theory, Computer Science - Systems and Control, Mathematics, Nash equilibrium, symbols.namesake, symbols, Mathematical optimization, Fictitious play, Permutation, Convergence (routing), Algorithm design, Centroid, Potential game, Special case
Funded by
FCT| CMU-PT/SIA/0026/2009
Project
CMU-PT/SIA/0026/2009
Novel information processing methodologies for intelligent sensor networks
  • Funder: Fundação para a Ciência e a Tecnologia, I.P. (FCT)
  • Project Code: 111106
  • Funding stream: 3599-PPCDT
44 references, page 1 of 3

[1] G. W. Brown, ”Iterative Solutions of Games by Fictitious Play” In Activity Analysis of Production and Allocation, T. Coopmans, Ed. New York: Wiley, 1951.

[2] L. S. Shapley, “Some topics in two-person games,” Advances in game theory, vol. 52, pp. 1-29, 1964. [OpenAIRE]

[3] J. S. Jordan, “Three problems in learning mixed-strategy Nash equilibria,” Games and Economic Behavior, vol. 5, no. 3, pp. 368-386, Jul. 1993.

[4] D. P. Foster and H. P. Young, “On the nonconvergence of fictitious play in coordination games,” Games and Economic Behavior, vol. 25, no. 1, pp. 79-96, Oct. 1998.

[5] J. Robinson, “An iterative method of solving a game,” The Annals of Mathematics, vol. 54, no. 2, pp. 296-301, Sep. 1951. [OpenAIRE]

[6] K. Miyasawa, “On the convergence of the learning process in a 2 x 2 non-zero-sum two-person game,” DTIC Document, Tech. Rep., 1961.

[7] D. Monderer and L. S. Shapley, “Fictitious play property for games with identical interests,” Journal of Economic Theory, vol. 68, no. 1, pp. 258-265, Jan. 1996. [OpenAIRE]

[8] M. Benaım and M. W. Hirsch, “Mixed equilibria and dynamical systems arising from fictitious play in perturbed games,” Games and Economic Behavior, vol. 29, no. 1, pp. 36-72, Oct. 1999.

[9] B. Swenson, S. Kar, and J. Xavier, “Distributed learning in large-scale multi-agent games: A modified fictitious play approach,” in 46th Asilomar Conference on Signals, Systems, and Computers, Pacifc Grove, CA, USA, Nov. 4 - 7 2012, pp. 1490 - 1495.

[10] C. H. Papadimitriou and T. Roughgarden, “Computing equilibria in multi-player games,” in Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 2005, pp. 82-91.

[11] R. W. Rosenthal, “A class of games possessing pure-strategy nash equilibria,” International Journal of Game Theory, vol. 2, no. 1, pp. 65-67, 1973.

[12] S.-F. Cheng, D. M. Reeves, Y. Vorobeychik, and M. P. Wellman, “Notes on equilibria in symmetric games,” in Proceedings of Workshop on Game Theory and Decision Theory, 2004.

[13] C. Daskalakis and C. Papadimitriou, “Computing equilibria in anonymous games,” in 48th Annual IEEE Symposium on Foundations of Computer Science, Oct. 2007, pp. 83-93.

[14] M. Kearns, M. L. Littman, and S. Singh, “Graphical models for game theory,” in Proceedings of the Seventeenth conference on Uncertainty in artificial intelligence. Morgan Kaufmann Publishers Inc., 2001, pp. 253-260.

[15] D. Gale and S. Kariv, “Bayesian learning in social networks,” Games and Economic Behavior, vol. 45, no. 2, pp. 329-346, Nov. 2003.

44 references, page 1 of 3
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue