{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T08:56:28Z","timestamp":1768553788399,"version":"3.49.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2017,12,2]],"date-time":"2017-12-02T00:00:00Z","timestamp":1512172800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s00224-017-9826-1","type":"journal-article","created":{"date-parts":[[2017,12,2]],"date-time":"2017-12-02T05:14:40Z","timestamp":1512191680000},"page":"1288-1317","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["A Unifying Tool for Bounding the Quality of Non-Cooperative Solutions in Weighted Congestion Games"],"prefix":"10.1007","volume":"62","author":[{"given":"Vittorio","family":"Bil\u00f2","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,2]]},"reference":[{"issue":"5","key":"9826_CR1","doi-asserted-by":"crossref","first-page":"1211","DOI":"10.1137\/090748986","volume":"40","author":"S Aland","year":"2011","unstructured":"Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F.: Exact price of anarchy for polynomial congestion games. SIAM J. Comput. 40(5), 1211\u20131233 (2011)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9826_CR2","doi-asserted-by":"crossref","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."},{"issue":"3","key":"9826_CR3","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1007\/s00224-008-9112-3","volume":"45","author":"S Athanassopoulos","year":"2009","unstructured":"Athanassopoulos, S., Caragiannis, I., Kaklamanis, C.: Analysis of Approximation algorithms for k-Set cover using factor-revealing linear programs. Theory of Computing Systems 45(3), 555\u2013576 (2009)","journal-title":"Theory of Computing Systems"},{"key":"9826_CR4","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Epstein, A.: The price of routing unsplittable flow. In: Proceedings of the 37th annual ACM symposium on theory of computing (STOC), pp 57\u201366. ACM Press, New York (2005)","DOI":"10.1145\/1060590.1060599"},{"key":"9826_CR5","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Grove, E. F., Kao, M. -Y., Krishnan, P., Vitter, J.S.: Load balancing in the l p norm. In: Proceedings of the 36th annual symposium on foundations of computer science (FOCS). IEEE Computer Society, pp 383\u2013391 (1995)","DOI":"10.1109\/SFCS.1995.492494"},{"issue":"4","key":"9826_CR6","doi-asserted-by":"crossref","first-page":"14:1","DOI":"10.1145\/2629666","volume":"2","author":"K Bhawalkar","year":"2014","unstructured":"Bhawalkar, K., Gairing, M., Roughgarden, T.: Weighted congestion Games: price of anarchy, universal worst-Case examples, and tightness. ACM Trans. Econ. Comput. 2(4), 14:1\u201314:23 (2014)","journal-title":"ACM Trans. Econ. Comput."},{"key":"9826_CR7","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, V.: A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games. In: Proceedings of the 10th workshop on approximation and online algorithms (WAOA), LNCS 7846, pp 215\u2013228. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-38016-7_18"},{"key":"9826_CR8","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, V.: On linear congestion games with altruistic social context. In: Proceedings of the 20th international computing and combinatorics conference (COCOON), LNCS 8591, pp 547\u2013558. Springer, Berlin (2014)","DOI":"10.1007\/978-3-319-08783-2_47"},{"key":"9826_CR9","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, V.: On the robustness of the approximate price of anarchy in generalized congestion games. In: Proceedings of the 9th international symposium on algorithmic game theory (SAGT), LNCS 9928, pp 93\u20131004. Springer, Berlin (2016)","DOI":"10.1007\/978-3-662-53354-3_8"},{"issue":"1","key":"9826_CR10","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/s00224-010-9309-0","volume":"49","author":"V Bil\u00f2","year":"2011","unstructured":"Bil\u00f2, V., Fanelli, A., Flammini, M., Moscardelli, L.: Performances of One-Round walks in linear congestion games. Theory of Computing Systems 49(1), 24\u201345 (2011)","journal-title":"Theory of Computing Systems"},{"issue":"2","key":"9826_CR11","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1017\/S0960129515000079","volume":"27","author":"V Bil\u00f2","year":"2017","unstructured":"Bil\u00f2, V., Fanelli, A., Moscardelli, L.: On lookahead equilibria in linear congestion games. Math. Struct. Comput. Sci. 27(2), 197\u2013214 (2017)","journal-title":"Math. Struct. Comput. Sci."},{"key":"9826_CR12","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, V., Flammini, M., Gallotti, V.: On bidimensional congestion games. In: Proceedings of the 19th international colloquium on structural information and communication complexity (SIROCCO), LNCS 7355, pp 147\u2013158. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-31104-8_13"},{"issue":"1","key":"9826_CR13","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1007\/s00224-013-9529-1","volume":"56","author":"V Bil\u00f2","year":"2015","unstructured":"Bil\u00f2, V., Flammini, M., Monaco, G., Moscardelli, L.: Some anomalies of farsighted strategic behavior. Theory of Computing Systems 56(1), 156\u2013180 (2015)","journal-title":"Theory of Computing Systems"},{"issue":"4","key":"9826_CR14","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1007\/s10878-015-9898-2","volume":"32","author":"V Bil\u00f2","year":"2016","unstructured":"Bil\u00f2, V., Paladini, M.: On the performance of mildly greedy players in cut games. J. Comb. Optim. 32(4), 1036\u20131051 (2016)","journal-title":"J. Comb. Optim."},{"key":"9826_CR15","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, V., Vinci, C.: On stackelberg strategies in affine congestion games. In: Proceedings of the 11th international conference on Web and internet economics (WINE), LNCS 9470, pp 132\u2013145. Springer, Berlin (2015)","DOI":"10.1007\/978-3-662-48995-6_10"},{"key":"9826_CR16","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, V., Vinci, C.: Dynamic taxes for polynomial congestion games. In: Proceedings of the ACM conference on economics and computation (EC), pp 839\u2013856. ACM Press, New York (2016)","DOI":"10.1145\/2940716.2940750"},{"issue":"2","key":"9826_CR17","doi-asserted-by":"crossref","first-page":"959","DOI":"10.1137\/06067660X","volume":"23","author":"I Caragiannis","year":"2009","unstructured":"Caragiannis, I.: Wavelength management in WDM rings to maximize the number of connections. SIAM J. Discret. Math. 23(2), 959\u2013978 (2009)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"9826_CR18","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/1868237.1868251","volume":"7","author":"I Caragiannis","year":"2010","unstructured":"Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Taxes for linear atomic congestion games. ACM Trans. Algorithms 7(1), 13 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"9826_CR19","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M., Papaioannou, E.: The impact of altruism on the efficiency of atomic congestion games. In: Proceedings of the 5th international symposium on trustworthly global computing (TGC), LNCS 6084, pp 172\u2013188. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-15640-3_12"},{"issue":"3","key":"9826_CR20","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1007\/s00453-010-9427-8","volume":"61","author":"I Caragiannis","year":"2011","unstructured":"Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.: Tight bounds for selfish and greedy load balancing. Algorithmica 61(3), 606\u2013637 (2011)","journal-title":"Algorithmica"},{"key":"9826_CR21","doi-asserted-by":"crossref","unstructured":"Chien, S., Sinclair, A.: Strong and pareto price of anarchy in congestion games. In: Proceedings of the 36th international colloquium on automata, languages and programming (ICALP), LNCS, pp 279\u2013291. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-02927-1_24"},{"issue":"2","key":"9826_CR22","first-page":"10","volume":"42","author":"G Christodoulou","year":"2016","unstructured":"Christodoulou, G., Gairing, M.: Price of stability in polynomial congestion games. ACM Trans. Econ. Comput. 42(2), 10 (2016)","journal-title":"ACM Trans. Econ. Comput."},{"key":"9826_CR23","doi-asserted-by":"crossref","unstructured":"Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proceedings of the 37th annual ACM Symposium on theory of computing (STOC), pp 67\u201373. ACM Press, New York (2005)","DOI":"10.1145\/1060590.1060600"},{"key":"9826_CR24","doi-asserted-by":"crossref","unstructured":"Christodoulou, G., Koutsoupias, E.: On the price of anarchy and stability of correlated equilibria of linear congestion games. In: Proceedings of the 13th annual European symposium on algorithms (ESA), LNCS 3669, pp 59\u201370. Springer, Berlin (2005)","DOI":"10.1007\/11561071_8"},{"issue":"1","key":"9826_CR25","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/s00453-010-9449-2","volume":"61","author":"G Christodoulou","year":"2011","unstructured":"Christodoulou, G., Koutsoupias, E., Spirakis, P. G.: On the performance of approximate equilibria in congestion games. Algorithmica 61(1), 116\u2013140 (2011)","journal-title":"Algorithmica"},{"key":"9826_CR26","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.tcs.2012.02.033","volume":"438","author":"G Christodoulou","year":"2012","unstructured":"Christodoulou, G., Mirrokni, V. S., Sidiropoulos, A.: Convergence and approximation in potential games. Theor. Comput. Sci. 438, 13\u201327 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9826_CR27","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1007\/s00453-013-9806-z","volume":"71","author":"U Feige","year":"2015","unstructured":"Feige, U., Jozeph, S.: Oblivious algorithms for the maximum directed cut problem. Algorithmica 71(2), 404\u2013428 (2015)","journal-title":"Algorithmica"},{"issue":"1","key":"9826_CR28","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1007\/s00224-008-9152-8","volume":"47","author":"D Fotakis","year":"2010","unstructured":"Fotakis, D.: Stackelberg strategies for atomic congestion games. Theory of Computing Systems 47(1), 218\u2013249 (2010)","journal-title":"Theory of Computing Systems"},{"key":"9826_CR29","doi-asserted-by":"crossref","unstructured":"Fotakis, D., Kontogiannis, S. C., Spirakis, P.G.: Symmetry in network congestion games pure equilibria and anarchy cost. In: Proceedings of the 3rd workshop on approximation and online algorithms (WAOA), LNCS 3879, pp 161\u2013175. Springer, Berlin (2005)","DOI":"10.1007\/11671411_13"},{"issue":"3","key":"9826_CR30","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1287\/moor.1120.0543","volume":"37","author":"T Harks","year":"2012","unstructured":"Harks, T., Klimm, M.: On the existence of pure nash equilibria in weighted congestion games. Math. Oper. Res. 37(3), 419\u2013436 (2012)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"9826_CR31","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1007\/s00224-011-9315-x","volume":"49","author":"T Harks","year":"2011","unstructured":"Harks, T., Klim, M., M\u00f6hring, R.H.: Characterizing the existence of potential functions in weighted congestion games. Theory of Computing Systems 49 (1), 46\u201370 (2011)","journal-title":"Theory of Computing Systems"},{"key":"9826_CR32","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, C.: Worst-Case Equilibria. In: Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science (STACS), LNCS 1563, pp 404\u2013413. Springer, Berlin (1999)","DOI":"10.1007\/3-540-49116-3_38"},{"issue":"6","key":"9826_CR33","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K Jain","year":"2003","unstructured":"Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with Factor-Revealing LP. J. ACM 50(6), 795\u2013824 (2003)","journal-title":"J. ACM"},{"key":"9826_CR34","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In: Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pp 597\u2013606. ACM Press, New York (2011)","DOI":"10.1145\/1993636.1993716"},{"key":"9826_CR35","doi-asserted-by":"crossref","unstructured":"Mirrokni, V. S., Thain, N., Vetta, A.: A theoretical examination of practical game playing lookahead search. In: Proceedings of the 5th international symposium on algorithmic game theory (SAGT), LNCS 7615, pp 251\u2013262. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-33996-7_22"},{"key":"9826_CR36","doi-asserted-by":"crossref","unstructured":"Mirrokni, V.S., Vetta, A.: Convergence issues in competitive games. In: Proceedings of the 7th international workshop on approximation algorithms for combinatorial optimization problems (APPROX), LNCS 3122, pp 183\u2013194. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-27821-4_17"},{"key":"9826_CR37","doi-asserted-by":"crossref","unstructured":"Nadav, U., Roughgarden, T.: The limits of smoothness: a primal-dual framework for price of anarchy bounds. In: Proceedings of the 6th international workshop on internet and network economics (WINE), LNCS 6484, pp 319\u2013326. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-17572-5_26"},{"key":"9826_CR38","doi-asserted-by":"crossref","unstructured":"Paes Leme, R., Syrgkanis, V., Tardos, \u00c9.: The curse of simultaneity. In: Proceedings of innovations in theoretical computer science (ITCS), pp 60\u201367. ACM press, New York (2012)","DOI":"10.1145\/2090236.2090242"},{"issue":"2","key":"9826_CR39","first-page":"7","volume":"11","author":"PN Panagopoulou","year":"2006","unstructured":"Panagopoulou, P.N., Spirakis, P.G.: Algorithms for pure nash equilibria in weighted congestion games. ACM J. Exp. Algorithmics 11(2), 7 (2006)","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"7","key":"9826_CR40","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1145\/2209249.2209274","volume":"55","author":"T Roughgarden","year":"2012","unstructured":"Roughgarden, T.: Intrinsic robustness of the price of anarchy. Commun. ACM 55(7), 116\u2013123 (2012)","journal-title":"Commun. ACM"},{"key":"9826_CR41","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF01737559","volume":"2","author":"RW Rosenthal","year":"1973","unstructured":"Rosenthal, R.W.: A class of games possessing pure-Strategy nash equilibria. Int. J. Game Theory 2, 65\u201367 (1973)","journal-title":"Int. J. Game Theory"},{"issue":"1","key":"9826_CR42","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s00453-006-1211-4","volume":"47","author":"S Suri","year":"2007","unstructured":"Suri, S., T\u00f3th, C., Zhou, Y.: Selfish load balancing and atomic congestion games. Algorithmica 47(1), 79\u201396 (2007)","journal-title":"Algorithmica"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9826-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9826-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9826-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T23:44:12Z","timestamp":1751067852000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9826-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,2]]},"references-count":42,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["9826"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9826-1","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,2]]}}}