×

zbMATH — the first resource for mathematics

Convergence to approximate Nash equilibria in congestion games. (English) Zbl 1209.91020
Authors’ abstract: We study the ability of decentralized, local dynamics in non-cooperative games to rapidly reach an approximate (pure) Nash equilibrium. Our main result states that for symmetric congestion games in which the cost function associated with each resource satisfies a “bounded jump” condition, convergence to an \(\varepsilon \)-Nash equilibrium occurs within a number of steps that is polynomial in the number of players and \(\varepsilon ^{ - 1}\). We show moreover that this result holds under a variety of conventions governing the move orders among the players, including the minimal liveness assumption that no player is indefinitely blocked from moving. We also prove that in the generalized setting where players have different “tolerances” \(\varepsilon _i\), the number of moves a player makes before equilibrium is reached depends only on his associated \(\varepsilon _i\), and not on those of other players. Finally, we show that polynomial time convergence holds even when a constant number of resources have arbitrary cost functions.

MSC:
91A10 Noncooperative games
91A06 \(n\)-person games, \(n>2\)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ackermann, H.; Berenbrink, P.; Fischer, S.; Hoefer, M., Concurrent imitation dynamics in congestion games, (2008)
[2] Ackermann, H.; Röglin, H.; Vöcking, B., On the impact of combinatorial structure on congestion games, J. ACM, 55, (2008) · Zbl 1325.91010
[3] Awerbuch, B.; Azar, Y.; Epstein, A., The price of routing unsplittable flow, (), 57-66 · Zbl 1192.90099
[4] Awerbuch, B.; Azar, Y.; Epstein, A.; Mirrokni, V.S.; Skopalik, A., Fast convergence to nearly optimal solutions in potential games, (), 264-273
[5] Beckmann, M.; McGuire, C.B.; Winsten, C.B., Studies in the economics of transportation, (1956), Yale Univ. Press
[6] Berenbrink, P.; Friedetzky, T.; Goldberg, L.A.; Goldberg, P.; Hu, Z.; Martin, R., Distributed selfish load-balancing, SIAM J. comput., 37, 1163-1181, (2007) · Zbl 1141.68018
[7] Blum, A.; Even-Dar, E.; Ligett, K., Routing without regret: on convergence to Nash equilibria of regret-minimizing algorithms in routing games, (), 45-52 · Zbl 1314.91050
[8] Chen, X.; Deng, X., Settling the complexity of two-player Nash-equilibrium, (), 261-270
[9] Chien, S.; Sinclair, A., Convergence to approximate Nash equilibria in congestion games, (), 169-178 · Zbl 1303.91018
[10] Christodoulou, G.; Koutsoupias, E., The price of anarchy of finite congestion games, (), 67-73 · Zbl 1192.91039
[11] Daskalakis, C.; Goldberg, P.W.; Papadimitriou, C.H., The complexity of computing a Nash equilibrium, (), 71-78 · Zbl 1301.68142
[12] Even-Dar, E.; Kesselman, A.; Mansour, Y., Convergence time to Nash equilibria, (), 502-513 · Zbl 1039.68017
[13] Even-Dar, E.; Mansour, Y., Fast convergence of selfish rerouting, (), 772-781 · Zbl 1297.68034
[14] Fabrikant, A.; Papadimitriou, C.H.; Talwar, K., The complexity of pure Nash equilibria, (), 604-612 · Zbl 1192.91042
[15] Fischer, S.; Räcke, H.; Vöcking, B., Fast convergence to wardrop equilibria by adaptive sampling methods, (), 653-662 · Zbl 1300.91008
[16] Goemans, M.; Mirrokni, V.; Vetta, A., Sink equilibria and convergence, (), 142-154
[17] Goldberg, P.W., Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game, (), 131-140 · Zbl 1321.68082
[18] Johnson, D.S.; Papadimitriou, C.H.; Yannakakis, M., How easy is local search?, J. computer system sci., 37, 79-100, (1988) · Zbl 0655.68074
[19] Kearns, M.; Mansour, Y., Efficient Nash computation in large population games with bounded influence, (), 259-266
[20] Lipton, R.J.; Markakis, E.; Mehta, A., Playing large games using simple strategies, (), 36-41
[21] Milchtaich, I., Congestion games with player-specific payoff functions, Games econ. behav., 13, 111-124, (1996) · Zbl 0848.90131
[22] Mirrokni, V.S.; Vetta, A., Convergence issues in competitive games, (), 183-194 · Zbl 1105.91300
[23] Nash, J.F., Equilibrium points in n-person games, Proc. nat. acad. sci., 36, 48-49, (1950) · Zbl 0036.01104
[24] Orlin, J.; Punnen, A.; Schulz, A., Approximate local search in combinatorial optimization, (), 587-596 · Zbl 1318.68166
[25] Papadimitriou, C.H., Algorithms, games and the Internet, (), 749-753 · Zbl 1323.68022
[26] Rosenthal, R.W., A class of games possessing pure-strategy Nash equilibria, Int. J. game theory, 2, 65-67, (1973) · Zbl 0259.90059
[27] Roughgarden, T., Selfish routing and the price of anarchy, (2005), MIT Press
[28] Roughgarden, T.; Tardos, E., Bounding the inefficiency of equilibria in nonatomic congestion games, Games econ. behav., 47, 389-403, (2004) · Zbl 1068.91002
[29] Schäffer, A.A.; Yannakakis, M., Simple local search problems that are hard to solve, SIAM J. comput., 20, 56-87, (1991) · Zbl 0716.68048
[30] Skopalik, A.; Vöcking, B., Approximability of pure Nash equilibria, (), 355-364 · Zbl 1231.68146
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.