{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:30Z","timestamp":1740109290409,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2021,2]]},"DOI":"10.1007\/s00446-020-00381-4","type":"journal-article","created":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T20:03:49Z","timestamp":1592856229000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions"],"prefix":"10.1007","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7848-4904","authenticated-orcid":false,"given":"Vittorio","family":"Bil\u00f2","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0327-3728","authenticated-orcid":false,"given":"Michele","family":"Flammini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0998-5649","authenticated-orcid":false,"given":"Gianpiero","family":"Monaco","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9256-481X","authenticated-orcid":false,"given":"Luca","family":"Moscardelli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"381_CR1","doi-asserted-by":"publisher","DOI":"10.1145\/1455248.1455249","author":"H Ackermann","year":"2008","unstructured":"Ackermann, H., R\u00f6glin, H., V\u00f6cking, B.: On the impact of combinatorial structure on congestion games. J. ACM (2008). https:\/\/doi.org\/10.1145\/1455248.1455249","journal-title":"J. ACM"},{"issue":"4","key":"381_CR2","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1080\/15427951.2012.754800","volume":"9","author":"S Albers","year":"2013","unstructured":"Albers, S., Lenzner, P.: On approximate Nash equilibria in network design. Internet Math. 9(4), 384\u2013405 (2013)","journal-title":"Internet Math."},{"issue":"4","key":"381_CR3","doi-asserted-by":"publisher","first-page":"1602","DOI":"10.1137\/070680096","volume":"38","author":"E Anshelevich","year":"2008","unstructured":"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\u20131623 (2008)","journal-title":"SIAM J. Comput."},{"key":"381_CR4","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, V., Flammini, M., Monaco, G., Moscardelli, L.: Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions. In: Proceedings of the 11th Workshop on Internet and Network Economics (WINE), pp. 118\u2013131 (2015)","DOI":"10.1007\/978-3-662-48995-6_9"},{"key":"381_CR5","unstructured":"Caragiannis, I., Fanelli, A.: On approximate pure Nash equilibria in weighted congestion games with polynomial latencies. In: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 133:1\u2013133:12 (2019)"},{"key":"381_CR6","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., 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\u2013541 (2011)","DOI":"10.1109\/FOCS.2011.50"},{"issue":"1","key":"381_CR7","doi-asserted-by":"publisher","first-page":"2:1","DOI":"10.1145\/2614687","volume":"3","author":"I Caragiannis","year":"2015","unstructured":"Caragiannis, I., Fanelli, A., Gravin, N., Skopalik, A.: Approximate pure Nash equilibria in weighted congestion games: existence, efficient computation, and structure. ACM Trans. Econ. Comput. 3(1), 2:1\u20132:32 (2015)","journal-title":"ACM Trans. Econ. Comput."},{"issue":"1","key":"381_CR8","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jagm.1999.1042","volume":"33","author":"M Charikar","year":"1999","unstructured":"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\u201391 (1999)","journal-title":"J. Algorithms"},{"issue":"2","key":"381_CR9","first-page":"8:1","volume":"2","author":"X Chen","year":"2014","unstructured":"Chen, X., Doerr, B., Doerr, C., Hu, X., Ma, W., Stee, R.V.: The price of anarchy for selfish ring routing is two. ACM Trans. Econ. Comput. 2(2), 8:1\u20138:24 (2014)","journal-title":"ACM Trans. Econ. Comput."},{"issue":"2","key":"381_CR10","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.geb.2009.05.004","volume":"71","author":"S Chien","year":"2011","unstructured":"Chien, S., Sinclair, A.: Convergence to approximate Nash equilibria in congestion games. Games Econ. Behav. 71(2), 315\u2013327 (2011)","journal-title":"Games Econ. Behav."},{"key":"381_CR11","doi-asserted-by":"crossref","unstructured":"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\u2013612 (2004)","DOI":"10.1145\/1007352.1007445"},{"key":"381_CR12","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.tcs.2014.09.035","volume":"562","author":"A Fanelli","year":"2015","unstructured":"Fanelli, A., Leniowski, D., Monaco, G., Sankowski, P.: The ring design game with fair cost allocation. Theor. Comput. Sci. 562, 90\u2013100 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"381_CR13","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\log n$$ for approximating set-cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"381_CR14","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/j.jcss.2011.05.009","volume":"78","author":"M Feldman","year":"2012","unstructured":"Feldman, M., Kortsarz, G., Nutov, Z.: Improved approximation algorithms for directed Steiner forest. J. Comput. Syst. Sci. 78(1), 279\u2013292 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"36","key":"381_CR15","doi-asserted-by":"publisher","first-page":"3305","DOI":"10.1016\/j.tcs.2008.01.004","volume":"410","author":"D Fotakis","year":"2009","unstructured":"Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., Spirakis, P.: The structure and complexity of Nash equilibria for a selfish routing game. Theor. Comput. Sci. 410(36), 3305\u20133326 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"381_CR16","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"D Johnson","year":"1988","unstructured":"Johnson, D., Papadimitriou, C., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79\u2013100 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"381_CR17","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (STACS), pp. 404\u2013413 (1999)","DOI":"10.1007\/3-540-49116-3_38"},{"key":"381_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511805318","volume-title":"Distributed Computing: Principles, Algorithms, and Systems","author":"AD Kshemkalyani","year":"2008","unstructured":"Kshemkalyani, A.D., Singhal, M.: Distributed Computing: Principles, Algorithms, and Systems. Cambridge University Press, Cambridge (2008)"},{"key":"381_CR19","doi-asserted-by":"crossref","unstructured":"Magniez, F., de Rougemont, M., Santha, M., Zeitoun, X.: The complexity of approximate Nash equilibrium in congestion games with negative delays. In: Proceedings of the 7th Workshop on Internet and Network Economics (WINE), pp. 266\u2013277 (2011)","DOI":"10.1007\/978-3-642-25510-6_23"},{"issue":"4","key":"381_CR20","doi-asserted-by":"publisher","first-page":"1113","DOI":"10.1007\/s00182-017-0600-z","volume":"47","author":"A Mamageishvili","year":"2018","unstructured":"Mamageishvili, A., Mihal\u00e1k, M., Montemezzani, S.: Improved bounds on equilibria solutions in the network design game. Int. J. Game Theory 47(4), 1113\u20131135 (2018)","journal-title":"Int. J. Game Theory"},{"key":"381_CR21","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1006\/game.1996.0044","volume":"14","author":"D Monderer","year":"1996","unstructured":"Monderer, D., Shapley, L.: Potential games. Games Econ. Behav. 14, 124\u2013143 (1996)","journal-title":"Games Econ. Behav."},{"key":"381_CR22","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"JF Nash","year":"1950","unstructured":"Nash, J.F.: Equilibrium points in $$n$$-person games. Proc. Natl. Acad. Sci. 36, 48\u201349 (1950)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"3","key":"381_CR23","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"381_CR24","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01737559","volume":"2","author":"R Rosenthal","year":"1973","unstructured":"Rosenthal, R.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65\u201367 (1973)","journal-title":"Int. J. Game Theory"},{"key":"381_CR25","doi-asserted-by":"crossref","unstructured":"Skopalik, A., V\u00f6cking, B.: Inapproximability of pure Nash equilibria. In: Proceedings of the 40th ACM Symposium on Theory of Computing (STOC), pp. 355\u2013364 (2008)","DOI":"10.1145\/1374376.1374428"},{"key":"381_CR26","doi-asserted-by":"crossref","unstructured":"Syrgkanis, V.: The complexity of equilibria in cost sharing games. In: Proceedings of the 6th Workshop on Internet and Network Economics (WINE), pp. 366\u2013377 (2010)","DOI":"10.1007\/978-3-642-17572-5_30"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00381-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-020-00381-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00381-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,21]],"date-time":"2021-06-21T23:54:37Z","timestamp":1624319677000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-020-00381-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["381"],"URL":"https:\/\/doi.org\/10.1007\/s00446-020-00381-4","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"3 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}