Fast convergence to nearly optimal solutions in potential games

ABSTRACT

We study the speed of convergence of decentralized dynamics to approximately optimal solutions in potential games. We consider α-Nash dynamics in which a player makes a move if the improvement in his payoff is more than an α factor of his own payoff. Despite the known polynomial convergence of α-Nash dynamics to approximate Nash equilibria in symmetric congestion games [7], it has been shown that the convergence time to approximate Nash equilibria in asymmetric congestion games is exponential [25]. In contrast to this negative result, and as the main result of this paper, we show that for asymmetric congestion games with linear and polynomial delay functions, the convergence time of α-Nash dynamics to an approximate optimal solution is polynomial in the number of players, with approximation ratio that is arbitrarily close to the price of anarchy of the game. In particular, we show this polynomial convergence under the minimal liveness assumption that each player gets at least one chance to move in every T steps. We also prove that the same polynomial convergence result does not hold for (exact) best-response dynamics, showing the α-Nash dynamics is required. We extend these results for congestion games to other potential games including weighted congestion games with linear delay functions, cut games (also called party affiliation games) and market sharing games.

REFERENCES

• 1: Heiner Ackermann , Heiko Roglin , Berthold Vocking, On the Impact of Combinatorial Structure on Congestion Games, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.613-622, October 21-24, 2006 [doi>10.1109/FOCS.2006.55]
• 2: Elliot Anshelevich , Anirban Dasgupta , Jon Kleinberg , Eva Tardos , Tom Wexler , Tim Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.295-304, October 17-19, 2004 [doi>10.1109/FOCS.2004.68]
• 3: 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]
• 4: M. Charikar, C. Mattieu, H. Karloff, S. Naor, and M. Saks. Best response dynamics in multicast cost sharing. 2007. Unpublished Manuscript.
• 5: Chandra Chekuri , Julia Chuzhoy , Liane Lewin-Eytan , Joseph (Seffi) Naor , Ariel Orda, Non-cooperative multicast and facility location games, Proceedings of the 7th ACM conference on Electronic commerce, p.72-81, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134716]
• 6: 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]
• 7: 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
• 8: G. Christodolou, V. S. Mirrokni, and A. Sidiropolous. Convergence and approximation in potential games. In Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2006.
• 9: 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]
• 10: 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
• 11: Constantinos Daskalakis , Paul W. Goldberg , Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132527]
• 12: Alex Fabrikant , Christos Papadimitriou , Kunal Talwar, The complexity of pure Nash equilibria, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007445]
• 13: A. Fanelli, M. Flammini, and L. Moscardelli. The speed of convergence in congestion games under best-response dynamics. In ICALP 2008. To appear.
• 14: Angelo Fanelli , Michele Flammini , Luca Moscardelli, On the convergence of multicast games in directed networks, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248433]
• 15: Dimitris Fotakis , Spyros Kontogiannis , Paul Spirakis, Selfish unsplittable flows, Theoretical Computer Science, v.348 n.2, p.226-239, 8 December 2005 [doi>10.1016/j.tcs.2005.09.024]
• 16: Michel Goemans , Li Erran Li , Vahab S. Mirrokni , Marina Thottan, Market sharing games applied to content distribution in ad-hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989467]
• 17: 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]
• 18: David S. Johnson , Christos H. Papadimtriou , Mihalis Yannakakis, How easy is local search?, Journal of Computer and System Sciences, v.37 n.1, p.79-100, August 1988 [doi>10.1016/0022-0000(88)90046-3]
• 19: Vahab S. Mirrokni , Michel X. Goemans, Approximation algorithms for distributed and selfish agents, Massachusetts Institute of Technology, Cambridge, MA, 2005
• 20: V.S. Mirrokni and A. Vetta. Convergence issues in competitive games. In RANDOM-APPROX, pages 183--194, 2004.
• 21: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 22: R. W. Rosenthal. A class of games possesing pure-strategy nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
• 23: 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]
• 24: Alejandro A. Schäffer , Mihalis Yannakakis, Simple local search problems that are hard to solve, SIAM Journal on Computing, v.20 n.1, p.56-87, Feb. 1991 [doi>10.1137/0220004]
• 25: Alexander Skopalik , Berthold Vöcking, Inapproximability of pure nash equilibria, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374428]
• 26: 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

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

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

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Algorithms, Economics, Theory

Keywords:
congestion games, convergence time, game theory, nash equilibrium, potential games, price of anarchy