Abstract
We study the speed of convergence to approximately optimal states in two classes of potential games. We provide bounds in terms of the number of rounds, where a round consists of a sequence of movements, with each player appearing at least once in each round. We model the sequential interaction between players by a best-response walk in the state graph, where every transition in the walk corresponds to a best response of a player. Our goal is to bound the social value of the states at the end of such walks. In this paper, we focus on two classes of potential games: selfish routing games, and cut games (or party affiliation games [7]).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Awerbuch, B., Azar, Y., Epstein, A.: The price of routing unsplittable flow. In: STOC, pp. 57–66 (2005)
Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Machine Learning 56, 89–113 (2004)
Charikar, M., Wirth, A.: Maximizing quadratic programs: extending Grothendieck’s inequality. In: FOCS (page to appear, 2004)
Christodoulou, G., Koutsoupias, E.: On the price of anarchy and stability of correlated equilibria of linear congestion games. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 59–70. Springer, Heidelberg (2005)
Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: STOC, pp. 67–73 (2005)
Even-dar, E., Kesselman, A., Mansour, Y.: Convergence time to Nash equilibria. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 502–513. Springer, Heidelberg (2003)
Fabrikant, A., Papadimitriou, C., Talwar, K.: On the complexity of pure equilibria. In: STOC (2004)
Fliescher, L., Goemans, M., Mirrokni, V.S., Sviridenko, M. (almost) tight approximation algorithms for maximizing general assignment problems(submitted, 2004)
Fotakis, D., Kontogiannis, S., Spirakis, P.: Selfish unsplittable flow. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 593–605. Springer, Heidelberg (2004)
Goemans, M., Li, L., Mirrokni, V.S., Thottan, M.: Market sharing games applied to content distribution in ad-hoc networks. In: MOBIHOC (2004)
Goemans, M., Mirrokni, V.S., Vetta, A.: Sink equilibria and convergence. In: FOCS (2005)
Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115–1145 (1995)
Johnson, D., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Computer and System Sciences 37, 79–100 (1988)
Mirrokni, V.S., Vetta, A.: Convergence issues in competitive games. In: RANDOM-APPROX, pp. 183–194 (2004)
Monderer, D., Shapley, L.: Potential games. Games and Economics Behavior 14, 124–143 (1996)
Papadimitriou, C.: Algorithms, games, and the Internet. In: STOC (2001)
Poljak, S.: Integer linear programs and local search for max-cut. Siam Journal of Computing 24(4), 822–839 (1995)
Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory 2, 65–67 (1973)
Roughgarden, T., Tardos, E.: How bad is selfish routing? J. ACM 49(2), 236–259 (2002)
Tóth, C.D., Suri, S., Zhou, Y.: Selfish load balancing and atomic congestion games. In: SPAA, pp. 188–195 (2004)
Tóth, C.D., Suri, S., Zhou, Y.: Uncoordinated load balancing and congestion games in p2p systems. In: Voelker, G.M., Shenker, S. (eds.) IPTPS 2004. LNCS, vol. 3279, pp. 123–130. Springer, Heidelberg (2005)
Schaffer, A., Yannakakis, M.: Simple local search problems that are hard to solve. SIAM journal on Computing 20(1), 56–87 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Christodoulou, G., Mirrokni, V.S., Sidiropoulos, A. (2006). Convergence and Approximation in Potential Games. In: Durand, B., Thomas, W. (eds) STACS 2006. STACS 2006. Lecture Notes in Computer Science, vol 3884. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11672142_28
Download citation
DOI: https://doi.org/10.1007/11672142_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32301-3
Online ISBN: 978-3-540-32288-7
eBook Packages: Computer ScienceComputer Science (R0)