×

On approximate pure Nash equilibria in weighted congestion games with polynomial latencies. (English) Zbl 1480.91023

Summary: We consider weighted congestion games with polynomial latency functions of maximum degree \(d\geq 1\). For these games, we investigate the existence and efficiency of approximate pure Nash equilibria which are obtained through sequences of unilateral improvement moves by the players. By exploiting a simple technique, we firstly show that these games admit an infinite set of \(d\)-approximate potential functions. This implies that there always exists a \(d\)-approximate pure Nash equilibrium which can be reached through any sequence of \(d\)-approximate improvement moves by the players. As a corollary, we also obtain that, under mild assumptions on the structure of the players’ strategies, these games also admit a constant approximate potential function. Secondly, using a simple potential function argument, we are able to show that a \((d+\delta)\)-approximate pure Nash equilibrium of cost at most \((d+1)/(d+\delta)\) times the cost of an optimal state always exists, for every \(\delta\in[0,1]\).

MSC:

91A14 Potential and congestion games
91A11 Equilibrium refinements

References:

[1] Aland, Sebastian; Dumrauf, Dominic; Gairing, Martin; Monien, Burkhard; Schoppmann, Florian, Exact price of anarchy for polynomial congestion games, SIAM J. Comput., 40, 5, 1211-1233 (2011) · Zbl 1231.91008
[2] Awerbuch, Baruch; Azar, Yossi; Epstein, Amir; Mirrokni, Vahab S.; Skopalik, Alexander, Fast convergence to nearly optimal solutions in potential games, (Proceedings 9th ACM Conference on Electronic Commerce (EC) (2008)), 264-273
[3] Bilò, Vittorio; Flammini, Michele; Monaco, Gianpiero; Moscardelli, Luca, Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions, (Proceedings of the 11th International Conference on Web and Internet Economics (WINE) (2015)), 118-131 · Zbl 1404.91044
[4] Caragiannis, Ioannis; Fanelli, Angelo; Gravin, Nick; Skopalik, Alexander, Efficient computation of approximate pure Nash equilibria in congestion games, (Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2011)), 532-541 · Zbl 1292.91012
[5] Caragiannis, Ioannis; Fanelli, Angelo; Gravin, Nick; Skopalik, Alexander, Approximate pure Nash equilibria in weighted congestion games: existence, efficient computation, and structure, ACM Trans. Econ. Comput., 3, 1, Article 2 pp. (2015)
[6] Caragiannis, Ioannis; Flammini, Michele; Kaklamanis, Christos; Kanellopoulos, Panagiotis; Moscardelli, Luca, Tight bounds for selfish and greedy load balancing, Algorithmica, 61, 3, 606-637 (2011) · Zbl 1237.91049
[7] Chien, Steve; Sinclair, Alistair, Convergence to approximate Nash equilibria in congestion games, Games Econ. Behav., 71, 2, 315-327 (2011) · Zbl 1209.91020
[8] Christin, Nicolas; Grossklags, Jens; Chuang, John, Near rationality and competitive equilibria in networked systems, (Proceedings of the ACM SIGCOMM Workshop on Practice and Theory of Incentives in Networked Systems (PINS) (2004)), 213-219
[9] Christodoulou, George; Gairing, Martin, Price of stability in polynomial congestion games, ACM Trans. Econ. Comput., 4, 2, Article 10 pp. (2016) · Zbl 1335.91006
[10] Christodoulou, George; Gairing, Martin; Giannakopoulos, Yiannis; Spirakis, Paul G., The price of stability of weighted congestion games, SIAM J. Comput., 48, 5, 1544-1582 (2019) · Zbl 1426.91048
[11] Christodoulou, George; Koutsoupias, Elias, On the price of anarchy and stability of correlated equilibria of linear congestion games, (Proceedings of the 13th Annual European Symposium on Algorithms (ESA) (2005)), 59-70 · Zbl 1162.91305
[12] Dunkel, Juliane; Schulz, Andreas S., On the complexity of pure-strategy Nash equilibria in congestion and local-effect games, Math. Oper. Res., 33, 4, 851-868 (2008) · Zbl 1231.91010
[13] Feldotto, Matthias; Gairing, Martin; Kotsialou, Grammateia; Skopalik, Alexander, Computing approximate pure Nash equilibria in Shapley value weighted congestion games, (Proceedings of the 11th International Conference on Web and Internet Economics (WINE) (2017)), 191-204 · Zbl 1405.91073
[14] Fotakis, Dimitris; Kontogiannis, Spyros C.; Spirakis, Paul G., Selfish unsplittable flows, Theor. Comput. Sci., 348, 2-3, 226-239 (2005) · Zbl 1152.90355
[15] Giannakopoulos, Yiannis; Noarov, Georgy; Schulz, Andreas S., An improved algorithm for computing approximate equilibria in weighted congestion games (2018), CoRR
[16] Goemans, Michel X.; Mirrokni, Vahab S.; Vetta, Adrian, Sink equilibria and convergence, (Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2005)), 142-154
[17] Hansknecht, Christoph; Klimm, Max; Skopalik, Alexander, Approximate pure Nash equilibria in weighted congestion games, (Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) (2014)), 242-257 · Zbl 1360.91013
[18] Harks, Tobias; Klimm, Max, On the existence of pure Nash equilibria in weighted congestion games, Math. Oper. Res., 37, 3, 419-436 (2012) · Zbl 1297.91008
[19] Libman, Lavy; Orda, Ariel, Atomic resource sharing in noncooperative networks, Telecommun. Syst., 17, 4, 385-409 (2001) · Zbl 0971.68664
[20] Panagopoulou, Panagiota N.; Spirakis, Paul G., Algorithms for pure Nash equilibria in weighted congestion games, ACM J. Exp. Algorithmics, 11 (2006) · Zbl 1169.68319
[21] Rosenthal, Robert W., A class of games possessing pure-strategy Nash equilibria, Int. J. Game Theory, 2, 65-67 (1973) · Zbl 0259.90059
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.