zbMATH — the first resource for mathematics

Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions. (English) Zbl 1404.91044
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 118-131 (2015).
Summary: We consider the problem of computing approximate Nash equilibria in monotone congestion games with polynomially decreasing cost functions. This class of games generalizes the one of network congestion games, while polynomially decreasing cost functions also include the fundamental Shapley cost sharing value. We design an algorithm that, given a parameter \(\gamma >1\) and a subroutine able to compute \(\rho \)-approximate best-responses, outputs a \(\gamma (1/p+\rho)\)-approximate Nash equilibrium, where \(p\) is the number of players. The computational complexity of the algorithm heavily depends on the choice of \(\gamma \). In particular, when \(\gamma \in O(1)\), the complexity is quasi-polynomial, while when \(\gamma \in \varOmega (p^\epsilon)\), for a fixed constant \(\epsilon >0\), it becomes polynomial. Our algorithm provides the first non-trivial approximability results for this class of games and achieves an almost tight performance for network games in directed graphs. On the negative side, we also show that the problem of computing a Nash equilibrium in Shapley network cost sharing games is PLS-complete even in undirected graphs, where previous hardness results where known only in the directed case.
For the entire collection see [Zbl 1326.68026].

91A43 Games involving graphs
91A12 Cooperative games
91-04 Software, source code, etc. for problems pertaining to game theory, economics, and finance
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI
[1] Ackermann, H., Röglin, H., Vöcking, B.: On the impact of combinatorial structure on congestion games. J. ACM 55(6), 25 (2008) · Zbl 1325.91010 · doi:10.1145/1455248.1455249
[2] Albers, S., Lenzner, P.: On approximate Nash equilibria in network design. Internet Math. 9(4), 384–405 (2013) · Zbl 1341.91022 · doi:10.1080/15427951.2012.754800
[3] Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, E., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602–1623 (2008) · Zbl 1173.91321 · doi:10.1137/070680096
[4] Caragiannis, V., Fanelli, A., Gravin, N., Skopalik, A.: Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games. In: Proceedings of the IEEE 52nd Symposium on Foundations of Computer Science (FOCS), pp. 532–541 (2011) · Zbl 1292.91012 · doi:10.1109/FOCS.2011.50
[5] Charikar, M., Chekuri, C., Cheung, T., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner problems. J. Algorithms 33(1), 73–91 (1999) · Zbl 0937.68155 · doi:10.1006/jagm.1999.1042
[6] Magniez, F., de Rougemont, M., Santha, M., Zeitoun, X.: The complexity of approximate Nash equilibrium in congestion games with negative delays. In: Chen, N., Elkind, E., Koutsoupias, E. (eds.) Internet and Network Economics. LNCS, vol. 7090, pp. 266–277. Springer, Heidelberg (2011) · Zbl 05985917 · doi:10.1007/978-3-642-25510-6_23
[7] Chien, S., Sinclair, A.: Convergence to Approximate Nash Equilibria in Congestion Games. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 169–178. ACM Press (2007) · Zbl 1303.91018
[8] Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The complexity of pure Nash equilibria. In: Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), pp. 604–612 (2004) · Zbl 1192.91042 · doi:10.1145/1007352.1007445
[9] Feige, U.: A threshold of \[ \log n \]
for approximating set-cover. In: Proceedings of the 28th ACM Symposium on Theory of Computing (STOC), pp. 314–318 (1996) · Zbl 0922.68067
[10] Feldman, M., Kortsarz, G., Nutov, Z.: Improved approximation algorithms for Directed Steiner Forest. J. Comput. Syst. Sci. 78(1), 279–292 (2012) · Zbl 1237.68246 · doi:10.1016/j.jcss.2011.05.009
[11] Johnson, D., Papadimitriou, C., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79–100 (1988) · Zbl 0655.68074 · doi:10.1016/0022-0000(88)90046-3
[12] Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999) · Zbl 1099.91501 · doi:10.1007/3-540-49116-3_38
[13] Monderer, D., Shapley, L.: Potential games. Games Econ. Behav. 14, 124–143 (1996) · Zbl 0862.90137 · doi:10.1006/game.1996.0044
[14] Nash, J.F.: Equilibrium points in \[ n \]
-person games. In: Proceedings of the National Academy of Sciences, vol. 36, pp. 48-49 (1950) · Zbl 0036.01104 · doi:10.1073/pnas.36.1.48
[15] Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. In: Procedings of ACM Symposium on Theory of Computing (STOC), pp. 229–234 (1988) · doi:10.1145/62212.62233
[16] Rosenthal, R.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65–67 (1973) · Zbl 0259.90059 · doi:10.1007/BF01737559
[17] Skopalik, A., Vöcking, B.: Inapproximability of pure Nash equilibria. In: Proceedings of the 40th ACM Symposium on Theory of Computing (STOC), pp. 355–364 (2008) · Zbl 1231.68146 · doi:10.1145/1374376.1374428
[18] Syrgkanis, V.: The complexity of equilibria in cost sharing games. In: Saberi, A. (ed.) WINE 2010. LNCS, vol. 6484, pp. 366–377. Springer, Heidelberg (2010) · Zbl 05834649 · doi:10.1007/978-3-642-17572-5_30
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.