On the convergence of regret minimization dynamics in concave games

ABSTRACT

We study a general sub-class of concave games which we call socially concave games. We show that if each player follows any no-external regret minimization procedure then the dynamics will converge in the sense that both the average action vector will converge to a Nash equilibrium and that the utility of each player will converge to her utility in that Nash equilibrium. We show that many natural games are indeed socially concave games. Specifically, we show that linear Cournot competition and linear resource allocation games are socially-concave games, and therefore our convergence result applies to them. In addition, we show that a simple best response dynamics might diverge for linear resource allocation games, and is known to diverge for linear Cournot competition. For the TCP congestion games we show that "near" the equilibrium the games are socially-concave, and using our general methodology we show the convergence of a specific regret minimization dynamics.

REFERENCES

• 1: Sanjeev Arora , Bo Brinkman, A randomized online algorithm for bandwidth utilization, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.535-539, January 06-08, 2002, San Francisco, California
• 2: Avrim Blum , Eyal Even-Dar , Katrina Ligett, Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146392]
• 3: Avrim Blum , MohammadTaghi Hajiaghayi , Katrina Ligett , Aaron Roth, Regret minimization and the price of total anarchy, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374430]
• 4: Avrim Blum , Yishay Mansour, From External to Internal Regret, The Journal of Machine Learning Research, 8, p.1307-1324, 12/1/2007
• 5: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 6: 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]
• 7: A. A. Cournot. Recherches sur les principes mathÈmatiques de la theorie des richesses.(english translation: Researches into the mathematical principles of the theory of wealth). 1838.
• 8: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 9: D. Foster and S. M. Kakade. Deterministic calibration and nash equilibrium. In COLT, pages 33--48, 2004.
• 10: D. Foster and R. Vohra. Regret in the on-line decision problem. Games and Economic Behavior, 21:40--55, 1997.
• 11: D. Foster and H. P. Young. Learning, hypothesis testing, and Nash equilibrium. Games and Economic Behavior, 45:73--96, 2003.
• 12: 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.
• 13: Y. Freund and R. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29:79--103, 1999.
• 14: Drew Fudenberg and David K. Levine. The theory of learning in games. MIT press, 1998.
• 15: F. Germano and G. Lugosi. Global Nash convergence of Foster and Young's regret testing. Games and Economic Behavior, 60:135--154, 2007.
• 16: B. Hajek and G. Gopalakrishnan. Do greedy autonomous systems make for a sensible internet?, 2002. presented at the Conference on Stochastic Networks, Stanford University.
• 17: Sergiu Hart , Yishay Mansour, The communication complexity of uncoupled nash equilibrium procedures, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250843]
• 18: S. Hart and A. Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68:1127--1150, 2000.
• 19: S. Hart and A. Mas-Colell. Stochastic uncoupled dynamics and Nash equilibrium. Games and Economice Behavior, 57(2):286--303, 2006.
• 20: Elad Hazan , Amit Agarwal , Satyen Kale, Logarithmic regret algorithms for online convex optimization, Machine Learning, v.69 n.2-3, p.169-192, December 2007 [doi>10.1007/s10994-007-5016-8]
• 21: Ramesh Johari , John N. Tsitsiklis, Efficiency Loss in a Network Resource Allocation Game, Mathematics of Operations Research, v.29 n.3, p.407-435, August 2004 [doi>10.1287/moor.1040.0091]
• 22: Ramesh Johari , John N. Tsitsiklis, Efficiency Loss in a Network Resource Allocation Game, Mathematics of Operations Research, v.29 n.3, p.407-435, August 2004 [doi>10.1287/moor.1040.0091]
• 23: R. Karp , E. Koutsoupias , C. Papadimitriou , S. Shenker, Optimization problems in congestion control, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.66, November 12-14, 2000
• 24: F. P. Kelly. Charging and rate control for elastic traffic. European Transactions on Telecommunications, page 33ñ37, 1997.
• 25: A. Mas-Colell, J. Green, and M. D. Whinston. Microeconomic Theory. Oxford University Press, 1995.
• 26: J. B. Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econometrica, 33(3):520--534, 1965.
• 27: R. D. Theocharis. On the stability of the cournot solution on the oligopoly problem. The Review of Economic Studies., 27(2):133--134, 1960.
• 28: H. P. Young. Strategic Learning and Its Limits. Oxford University Press, 2004.
• 29: M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In ICML, pages 928--936, 2003.
• 30: M. Zinkevich. Theoretical guarantees for algorithms in multi-agent settings. Technical Report CMU-CS-04-161,, Carnegie Mellon University, 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Economics, Theory

Keywords:
algorithmic game theory, learning equilibrium, regret minimization