Learning equilibria in repeated congestion games

ABSTRACT

While the class of congestion games has been thoroughly studied in the multi-agent systems literature, settings with incomplete information have received relatively little attention. In this paper we consider a setting in which the cost functions of resources in the congestion game are initially unknown. The agents gather information about these cost functions through repeated interaction, and observations of costs they incur. In this context we consider the following requirement: the agents' algorithms should themselves be in equilibrium, regardless of the actual cost functions and should lead to an efficient outcome. We prove that this requirement is achievable for a broad class of games: repeated symmetric congestion games. Our results are applicable even when agents are somewhat limited in their capacity to monitor the actions of their counterparts, or when they are unable to determine the exact cost they incur from every resource. On the other hand, we show that there exist asymmetric congestion games for which no such equilibrium can be found, not even an inefficient one. Finally we consider equilibria with resistance to the deviation of more than one player and show that these do not exist even in repeated resource selection games.

REFERENCES

• 1: Itai Ashlagi , Dov Monderer , Moshe Tennenholtz, Resource selection games with unknown number of players, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160782]
• 2: I. Ashlagi, D. Monderer, and M. Tennenholtz. Robust learning equilibrium. In Proc. of UAI06, pages 34--41. AUAI Press, 2006.
• 3: I. Ashlagi, D. Monderer, and M. Tennenholtz. Learning equilibrium in resource selection games. In Proc. of AAAI07, pages 18--23, 2007.
• 4: M. Bowling and M. Veloso. Rational and convergent learning in stochastic games. In Proc. 17th IJCAI, pages 1021--1026, 2001.
• 5: Ronen I. Brafman , Moshe Tennenholtz, Efficient learning equilibrium, Artificial Intelligence, v.159 n.1-2, p.27-47, November 2004 [doi>10.1016/j.artint.2004.04.013]
• 6: R. Brafman and M. Tennenholtz. Optimal Efficient Learning Equilibrium: Imperfect Monitoring. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI) 2005, 2005.
• 7: Ronen I. Brafman , Moshe Tennenholtz, R-max - a general polynomial time algorithm for near-optimal reinforcement learning, The Journal of Machine Learning Research, 3, p.213-231, 3/1/2003
• 8: Vincent Conitzer , Tuomas Sandholm, AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents, Machine Learning, v.67 n.1-2, p.23-43, May 2007 [doi>10.1007/s10994-006-0143-1]
• 9: I. Erev and A. Roth. Predicting how people play games: Reinforcement learning in games with unique strategy equilibrium. American Economic Review, 88:848--881, 1998.
• 10: D. Fudenberg and D. Levine. The theory of learning in games. MIT Press, 1998.
• 11: Martin Gairing , Burkhard Monien , Karsten Tiemann, Selfish routing with incomplete information, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074000]
• 12: D. Garg and Y. Narahari. Price of Anarchy of Network Routing Games with Incomplete Information. In Proc. of 1st Workshop on Internet and Network Economic, Springer Verlag LNCS series 3828, pages 1066--1075, 2005.
• 13: A. Greenwald, K. Hall, and R. Serrano. Correlated q-learning. In NIPS workshop on multi-agent learning, 2002.
• 14: Junling Hu , Michael P. Wellman, Multiagent Reinforcement Learning: Theoretical Framework and an Algorithm, Proceedings of the Fifteenth International Conference on Machine Learning, p.242-250, July 24-27, 1998
• 15: E. Koutsoupias and C. Papadimitriou. Worst-Case Equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, pages 404--413, 1999.
• 16: Hagay Levin , Michael Schapira , Aviv Zohar, Interdomain routing and games, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374388]
• 17: M. L. Littman. Markov games as a framework for multi-agent reinforcement learning. In Proc. 11th ICML, pages 157--163, 1994.
• 18: D. Monderer and L. Shapley. Potential Games. Games and Economic Behavior, 14:124--143, 1996.
• 19: Dov Monderer , Moshe Tennenholtz, Learning equilibrium as a generalization of learning to optimize, Artificial Intelligence, v.171 n.7, p.448-452, May, 2007 [doi>10.1016/j.artint.2007.01.002]
• 20: R. Rosenthal. A Class of Games Possessing Pure-Strategy Nash Equilibria. International Journal of Game Theory, 2:65--67, 1973.
• 21: Jeffrey Shneidman , David C. Parkes, Specification faithfulness in networks with rational nodes, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011781]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

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

General Terms:
Economics, Theory

Keywords:
congestion games, learning equilibrium, repeated games