The communication complexity of uncoupled nash equilibrium procedures

ABSTRACT

We study the question of how long it takes players to reach a Nashequilibrium in uncoupled setups, where each player initially knowsonly his own payoff function. We derive lower bounds on the communication complexity of reaching a Nash equilibrium, i.e., on thenumber of bits that need to be transmitted, and thus also on the requirednumber of steps. Specifically, we show lower bounds that are exponential inthe number of players in each one of the following cases: (1) reaching apure Nash equilibrium; (2) reaching a pure Nash equilibrium in a Bayesiansetting; and (3) reaching a mixed Nash equilibrium. We then show that, incontrast, the communication complexity of reaching a correlated equilibriumis polynomial in the number of players.

REFERENCES

• 1: R.J. Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1:67--96, 1974.
• 2: A. Blum and Y. Mansour. From external to internal regret. In COLT, pages 621--636, 2005.
• 3: A. Cahn. General procedures leading to correlated equilibria. International Journal of Game Theory, 33:21--40, 2004.
• 4: Nicolò Cesa-Bianchi , Gábor Lugosi, Potential-Based Algorithms in On-Line Prediction and Game Theory, Machine Learning, v.51 n.3, p.239-261, June 2003 [doi>10.1023/A:1022901500417]
• 5: Nicolo Cesa-Bianchi , Gabor Lugosi, Prediction, Learning, and Games, Cambridge University Press, New York, NY, 2006
• 6: Vincent Conitzer , Tuomas Sandholm, Communication complexity as a lower bound for learning in games, Proceedings of the twenty-first international conference on Machine learning, p.24, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015351]
• 7: D. Foster and S.M. Kakade. Deterministic calibration and Nash equilibrium. In COLT, pages 33--48, 2004.
• 8: D. Foster and R. Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21:40--55, 1997.
• 9: D. Foster and H.P. Young. Learning, hypothesis testing, and Nash equilibrium. Games and Economic Behaviour, 45(1):73--96, Oct 2003.
• 10: D. Foster and H.P. Young. Regret testing: learning to play Nash equilibrium without knowing you have an opponent. Theoretical Economics, 1:341----367, 2006.
• 11: Drew Fudenberg and David K. Levine. The theory of learning in games. MIT press, 1998.
• 12: F. Germano and G. Lugosi. Global Nash convergence of Foster and Young's regret testing. Games and Economic Behavior, 2006. To appear.
• 13: S. Hart. Adaptive heuristics. Econometrica, 73:1401--1430, 2005.
• 14: S. Hart and A. Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68:1127--1150, 2000.
• 15: S. Hart and A. Mas-Colell. A general class of adaptive strategies. Journal of Economic Theory, 98:26--54, 2001.
• 16: S. Hart and A. Mas-Colell. Uncoupled dynamics do not lead to Nash equilibrium. American Economic Review, 93(5):1830--1836, 2003.
• 17: S. Hart and A. Mas-Colell. Stochastic uncoupled dynamics and Nash equilibrium. Games and Economic Behavior, 57:286--303, 2006.
• 18: S. Hart , D. Schmeidler, Existence of correlated equilibria, Mathematics of Operations Research, v.14 n.1, p.18-25, Feb. 1989 [doi>10.1287/moor.14.1.18]
• 19: J. Jordan. Three problems in learning mixed equilibria. Games and Economic Behaviour, 5:368--386, 1993.
• 20: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 21: D. Monderer and L.S. Shapley. Potential games. Games and Economic Behaviour, 14:124--143, 1996.
• 22: Christos H. Papadimitriou, Computing correlated equilibria in multi-player games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060598]
• 23: Gilles Stoltz , Gábor Lugosi, Internal Regret in On-Line Portfolio Selection, Machine Learning, v.59 n.1-2, p.125-159, May 2005 [doi>10.1007/s10994-005-0465-4]
• 24: G. Stoltz and G. Lugosi. Learning correlated equilibria in games with compact sets of strategies. Games and Economic Behavior, 2006. To appear.
• 25: H.P. Young. Strategic Learning and Its Limits. Oxford University Press, 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Economics, Theory

Keywords:
communication complexity, computational game theory