Regret minimization and the price of total anarchy

ABSTRACT

We propose weakening the assumption made when studying the price of anarchy: Rather than assume that self-interested players will play according to a Nash equilibrium (which may even be computationally hard to find), we assume only that selfish players play so as to minimize their own regret. Regret minimization can be done via simple, efficient algorithms even in many settings where the number of action choices for each player is exponential in the natural parameters of the problem. We prove that despite our weakened assumptions, in several broad classes of games, this "price of total anarchy" matches the Nash price of anarchy, even though play may never converge to Nash equilibrium. In contrast to the price of anarchy and the recently introduced price of sinking, which require all players to behave in a prescribed manner, we show that the price of total anarchy is in many cases resilient to the presence of Byzantine players, about whom we make no assumptions. Finally, because the price of total anarchy is an upper bound on the price of anarchy even in mixed strategies, for some games our results yield as corollaries previously unknown bounds on the price of anarchy in mixed strategies.

REFERENCES

• 1: Baruch Awerbuch , Yossi Azar , Amir Epstein, Large the price of routing unsplittable flow, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060599]
• 2: Baruch Awerbuch , Robert D. Kleinberg, Adaptive routing with end-to-end feedback: distributed learning and geometric approaches, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007367]
• 3: Moshe Babaioff , Robert Kleinberg , Christos H. Papadimitriou, Congestion games with malicious players, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250926]
• 4: Xi Chen , Xiaotie Deng, Settling the Complexity of Two-Player Nash Equilibrium, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.261-272, October 21-24, 2006 [doi>10.1109/FOCS.2006.69]
• 5: Steve Chien , Alistair Sinclair, Convergence to approximate Nash equilibria in congestion games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.169-178, January 07-09, 2007, New Orleans, Louisiana
• 6: G. Christodoulou and E. Koutsoupias. On the price of anarchy and stability of correlated equilibria of linear congestion games. ESA, pages 59--70, 2005.
• 7: George Christodoulou , Elias Koutsoupias, The price of anarchy of finite congestion games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060600]
• 8: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 9: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, ACM Transactions on Algorithms (TALG), v.3 n.1, February 2007 [doi>10.1145/1186810.1186814]
• 10: Varsha Dani , Thomas P. Hayes, Robbing the bandit: less regret in online geometric optimization against an adaptive adversary, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.937-943, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109660]
• 11: Alex Fabrikant , Ankur Luthra , Elitza Maneva , Christos H. Papadimitriou , Scott Shenker, On a network creation game, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.347-351, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872088]
• 12: D. P. Foster and R. V. Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 1997.
• 13: J. J. Gabszewicz and J.-F. Thisse. Location. In R. Aumann and S. Hart, editors, Handbook of Game Theory with Economic Applications, volume 1, chapter 9. Elsevier Science Publishers (North-Holland), 1992.
• 14: M. Goemans, L. Li, V. Mirrokni, and M. Thottan. Market sharing games applied to content distribution in ad hoc networks. Selected Areas in Communications, IEEE Journal on, 24(5):1020--1033, 2006.
• 15: Michel Goemans , Vahab Mirrokni , Adrian Vetta, Sink Equilibria and Convergence, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.142-154, October 23-25, 2005 [doi>10.1109/SFCS.2005.68]
• 16: J. Hannan. Approximation to Bayes risk in repeated play. In M. Dresher, A. Tucker, and P. Wolfe, editors, Contributions to the Theory of Games, volume III, pages 97--139. 1957.
• 17: S. Hart and A. Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 2000.
• 18: H. Hotelling. Stability in competition. The Economic Journal, 39(153):41--57, 1929.
• 19: Sham M. Kakade , Adam Tauman Kalai , Katrina Ligett, Playing games with approximation algorithms, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250870]
• 20: A. Kalai and S. Vempala. Efficient algorithms for on-line optimization. In COLT, pages 26--40, 2003.
• 21: Maureen Kilkenny , Jacques-François Thisse, Economics of location:: a selective survey, Computers and Operations Research, v.26 n.14, p.1369-1394, Dec. 1999 [doi>10.1016/S0305-0548(99)00041-6]
• 22: Robert Kleinberg, Anytime algorithms for multi-armed bandit problems, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.928-936, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109659]
• 23: E. Koutsoupias, M. Mavronikolas, and P. Spirakis. Approximate equilibria and ball fusion. Theory of Computing Systems, 36(6):683--693, 2003.
• 24: E. Koutsoupias and C. H. Papadimitriou. Worst-case equilibria. In STACS, pages 404--413, 1999.
• 25: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 26: H. McMahan and A. Blum. Online geometric optimization in the bandit setting against an adaptive adversary. In COLT, 2004.
• 27: V. S. Mirrokni and A. Vetta. Convergence issues in competitive games. In APPROX-RANDOM, 2004.
• 28: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 29: Subhash Suri , Csaba D. Toth , Yunhong Zhou, Selfish Load Balancing and Atomic Congestion Games, Algorithmica, v.47 n.1, p.79-96, January 2007 [doi>10.1007/s00453-006-1211-4]
• 30: Adrian Vetta, Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.416, November 16-19, 2002
• 31: M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In ICML, pages 928--936, 2003.

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
algorithmic game theory, nash equilibria, regret minimization