Nash dynamics in constant player and bounded jump congestion games.

*(English)*Zbl 1262.91014
Mavronicolas, Marios (ed.) et al., Algorithmic game theory. Second international symposium, SAGT 2009, Paphos, Cyprus, October 18–20, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-04644-5/pbk). Lecture Notes in Computer Science 5814, 196-207 (2009).

Summary: We study the convergence time of Nash dynamics in two classes of congestion games – constant player congestion games and bounded jump congestion games. It was shown by H. Ackermann and A. Skopalik [Internet Math. 5, No. 4, 323–342 (2008; Zbl 1194.91055)] that even 3-player congestion games are PLS-complete. We design an FPTAS for congestion games with constant number of players. In particular, for any \(\epsilon > 0\), we establish a stronger result, namely, any sequence of \((1 + \epsilon )\)-greedy improvement steps converges to a \((1 + \epsilon )\)-approximate equilibrium in a number of steps that is polynomial in \(\epsilon ^{ - 1}\) and the size of the input. As the number of strategies of a player can be exponential in the size of the input, our FPTAS result assumes that a \((1 + \epsilon )\)-greedy improvement step, if it exists, can be computed in polynomial time. This assumption holds in previously studied models of congestion games, including network congestion games [A. Fabrikant et al., in: Proceedings of the 36th annual ACM symposium on theory of computing, STOC 2004. New York, NY: ACM Press. 604–612 (2004; Zbl 1192.91042)] and restricted network congestion games [Ackermann and Skopalik, loc. cit.].

For bounded jump games, where jumps in the delay functions of resources are bounded by \(\beta \), we show that there exists a game with an exponentially long sequence of \(\alpha \)-greedy best response steps that does not converge to an \(\alpha \)-approximate equilibrium, for all \(\alpha \leq \beta ^{o(n/\log n)}\), where \(n\) is the number of players and the size of the game is \(O(n)\). So in the worst case, Nash dynamics may fail to converge in polynomial time to such an approximate equilibrium. We also prove the same result for bounded jump network congestion games. In contrast, we observe that it is easy to show that a \(\beta ^{2n }\)-approximate equilibrium is reached in at most \(n\) best response steps.

For the entire collection see [Zbl 1176.68013].

For bounded jump games, where jumps in the delay functions of resources are bounded by \(\beta \), we show that there exists a game with an exponentially long sequence of \(\alpha \)-greedy best response steps that does not converge to an \(\alpha \)-approximate equilibrium, for all \(\alpha \leq \beta ^{o(n/\log n)}\), where \(n\) is the number of players and the size of the game is \(O(n)\). So in the worst case, Nash dynamics may fail to converge in polynomial time to such an approximate equilibrium. We also prove the same result for bounded jump network congestion games. In contrast, we observe that it is easy to show that a \(\beta ^{2n }\)-approximate equilibrium is reached in at most \(n\) best response steps.

For the entire collection see [Zbl 1176.68013].