Convergence to approximate Nash equilibria in congestion games

ABSTRACT

We study the ability of decentralized, local dynamics in non-cooperative games to rapidly reach an approximate Nash equilibrium. For symmetric congestion games in which the edge delays satisfy a "bounded jump" condition, we show that convergence to an ε-Nash equilibrium occurs within a number of steps that is polynomial in the number of players and ε^-1. This appears to be the first such result for a class of games that includes examples for which finding an exact Nash equilibrium is PLS-complete, and in which shortest paths to an exact equilibrium are exponentially long. We show moreover that rapid convergence holds even under only the apparently minimal assumption that no player is excluded from moving for arbitrarily many steps. We also prove that, in a generalized setting where players have different "tolerances" εi that specify their thresholds in the approximate Nash equilibrium, the number of moves made by a player before equilibrium is reached depends only on his associated εi, and not on those of the other players. Finally, we show that polynomial time convergence still holds even when a bounded number of edges are allowed to have arbitrary delay functions.

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: M. Beckmann, C. B. McGuire and C. B. Winsten, Studies in the Economics of Transportation. Yale University Press, 1956.
• 3: 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]
• 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: Xi Chen , Xiaotie Deng , Shang-Hua Teng, Computing Nash Equilibria: Approximation and Smoothed Complexity, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.603-612, October 21-24, 2006 [doi>10.1109/FOCS.2006.20]
• 6: 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]
• 7: 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]
• 8: E. Even-Dar, A. Kesselman and Y. Mansour, "Convergence time to Nash equilibria." Proc. 30th International Conference on Automata, Languages and Programming, 2003, pp. 502--513.
• 9: Eyal Even-Dar , Yishay Mansour, Fast convergence of selfish rerouting, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 10: 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]
• 11: Simon Fischer , Harald Räcke , Berthold Vöcking, Fast convergence to Wardrop equilibria by adaptive sampling methods, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132608]
• 12: 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]
• 13: Paul W. Goldberg, Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game, 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.1011787]
• 14: 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]
• 15: M. Kearns and Y. Mansour, "Efficient Nash computation in large population games with bounded influence." Proc. 18th Conference in Uncertainty in Artificial Intelligence, 2002, pp. 259--266.
• 16: Richard J. Lipton , Evangelos Markakis , Aranyak Mehta, Playing large games using simple strategies, Proceedings of the 4th ACM conference on Electronic commerce, p.36-41, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779933]
• 17: I. Milchtaich, "Congestion games with player-specific payoff functions," Games and Economic Behavior 13 (1996), pp. 111--124.
• 18: V. S. Mirrokni and A. Vetta, "Convergence issues in competitive games." Proc. 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2004, pp. 183--194.
• 19: D. Monderer and L. S. Shapley, "Potential games." Games and Economic Behavior 14 (1996), pp. 124--143.
• 20: J. F. Nash, "Equilibrium points in n-person games." Proc. National Academy of Sciences 36 (1950), pp. 48--49.
• 21: James B. Orlin , Abraham P. Punnen , Andreas S. Schulz, Approximate local search in combinatorial optimization, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 22: 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]
• 23: R. W. Rosenthal, "A class of games possessing pure-strategy Nash equilibria." International Journal of Game Theory 2 (1973), pp. 65--67.
• 24: Tim Roughgarden, Selfish Routing and the Price of Anarchy, The MIT Press, 2005
• 25: T. Roughgarden and E. Tardos, "Bounding the inefficiency of equilibria in nonatomic congestion games." Games and Economic Behavior 47 (2004), pp. 389--403.
• 26: 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]
• 27: 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