{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T10:49:45Z","timestamp":1758278985143},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,8,2]],"date-time":"2012-08-02T00:00:00Z","timestamp":1343865600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,5]]},"DOI":"10.1007\/s00224-012-9421-4","type":"journal-article","created":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T13:31:13Z","timestamp":1343827873000},"page":"763-801","source":"Crossref","is-referenced-by-count":10,"title":["Collusion in Atomic Splittable Routing Games"],"prefix":"10.1007","volume":"52","author":[{"given":"Chien-Chung","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,8,2]]},"reference":[{"key":"9421_CR1","volume-title":"Network Flows","author":"R. Ahuja","year":"1993","unstructured":"Ahuja, R., Magnanti, T., Orlin, J.: Network Flows. Prentice Hall, New York (1993)"},{"key":"9421_CR2","first-page":"218","volume-title":"STACS","author":"S. Aland","year":"2006","unstructured":"Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F.: Exact price of anarchy for polynomial congestion games. In: STACS, pp. 218\u2013229 (2006)"},{"issue":"6","key":"9421_CR3","doi-asserted-by":"crossref","first-page":"2273","DOI":"10.1137\/070701376","volume":"38","author":"S. Albers","year":"2009","unstructured":"Albers, S.: Strong and pareto price of anarchy in congestion games. SIAM J. Comput. 38(6), 2273\u20132302 (2009)","journal-title":"SIAM J. Comput."},{"key":"9421_CR4","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1109\/9.981725","volume":"47","author":"E. Altman","year":"2002","unstructured":"Altman, E., Basar, T., Jimenez, T., Shimkin, N.: Competitive routing in networks with polynomial costs. IEEE Trans. Autom. Control 47, 92\u201396 (2002)","journal-title":"IEEE Trans. Autom. Control"},{"key":"9421_CR5","first-page":"189","volume-title":"SODA","author":"N. Andelman","year":"2007","unstructured":"Andelman, N., Feldman, M., Mansour, Y.: Strong price of anarchy. In: SODA, pp. 189\u2013198 (2007)"},{"key":"9421_CR6","doi-asserted-by":"crossref","unstructured":"Aumann, R.: Acceptable points in general cooperative n-person games. Contrib. Theory Games 4 (1959)","DOI":"10.1515\/9781400882168-018"},{"key":"9421_CR7","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1145\/1060590.1060599","volume-title":"STOC","author":"B. Awerbuch","year":"2005","unstructured":"Awerbuch, B., Azar, Y., Epstein, A.: The price of routing unsplittable flow. In: STOC, pp. 57\u201366 (2005)"},{"key":"9421_CR8","first-page":"748","volume-title":"SODA","author":"U. Bhaskar","year":"2009","unstructured":"Bhaskar, U., Fleischer, L., Hoy, D., Huang, C.-C.: Equilibria of atomic flow games are not unique. In: SODA, pp. 748\u2013757 (2009)"},{"key":"9421_CR9","first-page":"313","volume-title":"IPCO","author":"U. Bhaskar","year":"2010","unstructured":"Bhaskar, U., Fleischer, L., Huang, C.-C.: The price of collusion in series-parallel networks. In: IPCO, pp. 313\u2013326 (2010)"},{"key":"9421_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern Graph Theory","author":"B. Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. Springer, Berlin (1998)"},{"issue":"2","key":"9421_CR11","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1287\/moor.1100.0442","volume":"35","author":"V. Bonifaci","year":"2010","unstructured":"Bonifaci, V., Harks, T., Sch\u00e4fer, G.: Stackelberg routing in arbitrary networks. Math. Oper. Res. 35(2), 330\u2013346 (2010)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"9421_CR12","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1287\/trsc.25.3.240","volume":"25","author":"S. Catoni","year":"1991","unstructured":"Catoni, S., Pallottino, S.: Traffic equilibrium paradoxes. Transp. Sci. 25(3), 240\u2013244 (1991)","journal-title":"Transp. Sci."},{"key":"9421_CR13","first-page":"279","volume-title":"ICALP","author":"S. Chien","year":"2009","unstructured":"Chien, S., Sinclair, A.: Strong and pareto price of anarchy in congestion games. In: ICALP, pp. 279\u2013291 (2009)"},{"key":"9421_CR14","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/1060590.1060600","volume-title":"STOC","author":"G. Christodoulou","year":"2005","unstructured":"Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: STOC, pp. 67\u201373 (2005)"},{"issue":"2","key":"9421_CR15","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(2), 116\u2013140 (2011)","journal-title":"Algorithmica"},{"issue":"6","key":"9421_CR16","doi-asserted-by":"crossref","first-page":"1421","DOI":"10.1287\/opre.1080.0653","volume":"57","author":"R. Cominetti","year":"2009","unstructured":"Cominetti, R., Correa, J.R., Stier-Moses, N.E.: The impact of oligopolistic competition in networks. Oper. Res. 57(6), 1421\u20131437 (2009)","journal-title":"Oper. Res."},{"issue":"4","key":"9421_CR17","doi-asserted-by":"crossref","first-page":"961","DOI":"10.1287\/moor.1040.0098","volume":"29","author":"J.R. Correa","year":"2004","unstructured":"Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: Selfish routing in capacitated networks. Math. Oper. Res. 29(4), 961\u2013976 (2004)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"9421_CR18","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"R. Duffin","year":"1965","unstructured":"Duffin, R.: Topology of series-parallel networks. J. Math. Anal. Appl. 10(2), 303\u2013318 (1965)","journal-title":"J. Math. Anal. Appl."},{"key":"9421_CR19","first-page":"84","volume-title":"EC","author":"A. Epstein","year":"2007","unstructured":"Epstein, A., Feldman, M., Mansour, Y.: Strong equilibrium in cost-sharing connection games. In: EC, pp. 84\u201392 (2007)"},{"key":"9421_CR20","first-page":"583","volume-title":"ICALP","author":"A. Fiat","year":"2007","unstructured":"Fiat, A., Levy, M., Kaplan, H., Olonetsky, S.: Strong price of anarchy for machine load balancing. In: ICALP, pp. 583\u2013594 (2007)"},{"issue":"2\u20133","key":"9421_CR21","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/j.tcs.2005.09.014","volume":"348","author":"L. Fleischer","year":"2005","unstructured":"Fleischer, L.: Linear tolls suffice: new bounds and algorithms for tolls in single source networks. Theor. Comput. Sci. 348(2\u20133), 217\u2013225 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9421_CR22","first-page":"277","volume-title":"FOCS","author":"L. Fleischer","year":"2004","unstructured":"Fleischer, L., Jain, K., Mahdian, M.: Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In: FOCS, pp. 277\u2013285 (2004)"},{"key":"9421_CR23","first-page":"123","volume-title":"ICALP","author":"D. Fotakis","year":"2002","unstructured":"Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., Spirakis, P.: The structure and complexity of Nash equilibria for a selfish routing game. In: ICALP, pp. 123\u2013134 (2002)"},{"key":"9421_CR24","first-page":"161","volume-title":"WAOA","author":"D. Fotakis","year":"2005","unstructured":"Fotakis, D., Kontogiannis, S., Spirakis, P.: Symmetry in network congestion games: pure equilibria and anarchy cost. In: WAOA, pp. 161\u2013175 (2005)"},{"key":"9421_CR25","doi-asserted-by":"crossref","unstructured":"Fotakis, D., Kontogiannis, S.C., Spirakis, P.: Selfish unsplittable flows. Theor. Comput. Sci. 226\u2013239 (2005)","DOI":"10.1016\/j.tcs.2005.09.024"},{"key":"9421_CR26","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/1383369.1383383","volume":"4","author":"D. Fotakis","year":"2008","unstructured":"Fotakis, D., Kontogiannis, S., Spirakis, P.: Atomic congestion games among coalitions. ACM Trans. Algorithms 4, 4 (2008). The conference version appeared in ICALP 2006","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"9421_CR27","doi-asserted-by":"crossref","first-page":"1430","DOI":"10.1137\/060670730","volume":"38","author":"R. Hariharan","year":"2008","unstructured":"Hariharan, R., Kavitha, T., Mehlhorn, K.: Faster algorithms for minimum cycle basis in directed graphs. SIAM J. Comput. 38(4), 1430\u20131447 (2008)","journal-title":"SIAM J. Comput."},{"key":"9421_CR28","doi-asserted-by":"crossref","unstructured":"Harks, T.: Stackelberg strategies and collusion in network games with splittable flow. Theory Comput. Syst. 781\u2013802 (2011)","DOI":"10.1007\/s00224-010-9269-4"},{"key":"9421_CR29","first-page":"463","volume-title":"WINE","author":"T. Harks","year":"2009","unstructured":"Harks, T., Klimm, M., M\u00f6hring, R.: Strong Nash equilibria in games with the lexicographical improvement property. In: WINE, pp. 463\u2013470 (2009)"},{"key":"9421_CR30","first-page":"29","volume-title":"ESA","author":"T. Harks","year":"2010","unstructured":"Harks, T., H\u00f6fer, M., Klimm, M., Skopalik, A.: Computing pure Nash and strong equilibria in bottleneck congestion games. In: ESA, pp. 29\u201338 (2010)"},{"key":"9421_CR31","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1145\/1132516.1132529","volume-title":"STOC","author":"A. Hayrapetyan","year":"2006","unstructured":"Hayrapetyan, A., Tardos, E., Wexler, T.: The effect of collusion in congestion games. In: STOC, pp. 89\u201398 (2006)"},{"key":"9421_CR32","first-page":"268","volume-title":"FOCS","author":"G. Karakostas","year":"2004","unstructured":"Karakostas, G., Kolliopoulos, S.G.: Edge pricing of multicommodity networks for heterogeneous selfish users. In: FOCS, pp. 268\u2013276 (2004)"},{"key":"9421_CR33","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1007\/3-540-49116-3_38","volume-title":"STACS","author":"E. Koutsoupias","year":"1999","unstructured":"Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: STACS, pp. 404\u2013413 (1999)"},{"issue":"4","key":"9421_CR34","doi-asserted-by":"crossref","first-page":"1667","DOI":"10.1137\/090769600","volume":"25","author":"H. Lin","year":"2011","unstructured":"Lin, H., Roughgarden, T., Tardos, E., Walkover, A.: Stronger bounds on Braess\u2019s paradox and the maximum latency of selfish routing. SIAM J. Discrete Math. 25(4), 1667\u20131686 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"9421_CR35","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0377-2217(84)90160-7","volume":"18","author":"M. Minoux","year":"1984","unstructured":"Minoux, M.: A polynomial algorithm for minimum quadratic cost flow problems. Eur. J. Oper. Res. 18, 377\u2013387 (1984)","journal-title":"Eur. J. Oper. Res."},{"key":"9421_CR36","volume-title":"Numerical Optimization","author":"J. Nocedal","year":"2006","unstructured":"Nocedal, J., Wright, S.: Numerical Optimization. Springer, Berlin (2006)"},{"issue":"5","key":"9421_CR37","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1109\/90.251910","volume":"1","author":"A. Orda","year":"1993","unstructured":"Orda, A., Rom, R., Shimkin, N.: Competitive routing in multiuser communication networks. IEEE\/ACM Trans. Netw. 1(5), 510\u2013521 (1993)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"3","key":"9421_CR38","doi-asserted-by":"crossref","first-page":"520","DOI":"10.2307\/1911749","volume":"33","author":"J.B. Rosen","year":"1965","unstructured":"Rosen, J.B.: Existence and uniqueness of equilibrium points for concave n-person games. Econometrica 33(3), 520\u2013534 (1965)","journal-title":"Econometrica"},{"issue":"2","key":"9421_CR39","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1137\/S0097539701397059","volume":"33","author":"T. Roughgarden","year":"2004","unstructured":"Roughgarden, T.: Stackelberg scheduling strategies. SIAM J. Comput. 33(2), 332\u2013350 (2004)","journal-title":"SIAM J. Comput."},{"key":"9421_CR40","volume-title":"Selfish Routing and the Price of Anarchy","author":"T. Roughgarden","year":"2005","unstructured":"Roughgarden, T.: Selfish Routing and the Price of Anarchy. MIT Press, Cambridge (2005)"},{"issue":"5","key":"9421_CR41","doi-asserted-by":"crossref","first-page":"922","DOI":"10.1016\/j.jcss.2005.05.009","volume":"72","author":"T. Roughgarden","year":"2006","unstructured":"Roughgarden, T.: On the severity of Braess\u2019s paradox: designing networks for selfish users is hard. J. Comput. Syst. Sci. 72(5), 922\u2013953 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9421_CR42","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1145\/1536414.1536485","volume-title":"STOC","author":"T. Roughgarden","year":"2009","unstructured":"Roughgarden, T.: Intrinsic robustness of the price of anarchy. In: STOC, pp. 513\u2013522 (2009)"},{"key":"9421_CR43","volume-title":"SODA","author":"T. Roughgarden","year":"2011","unstructured":"Roughgarden, T., Schoppmann, F.: Local smoothness and the price of anarchy in atomic splittable congestion game. In: SODA (2011)"},{"issue":"2","key":"9421_CR44","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1145\/506147.506153","volume":"49","author":"T. Roughgarden","year":"2002","unstructured":"Roughgarden, T., Tardos, E.: How bad is selfish routing? J. ACM 49(2), 236\u2013259 (2002)","journal-title":"J. ACM"},{"key":"9421_CR45","first-page":"1133","volume-title":"SODA","author":"C. Swamy","year":"2007","unstructured":"Swamy, C.: The effectiveness of Stackelberg strategies and tolls for network congestion games. In: SODA, pp. 1133\u20131142 (2007)"},{"issue":"4","key":"9421_CR46","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1002\/rsa.20325","volume":"37","author":"G. Valiant","year":"2010","unstructured":"Valiant, G., Roughgarden, T.: Braess\u2019s paradox in large random graphs. Random Struct. Algorithms 37(4), 495\u2013515 (2010)","journal-title":"Random Struct. Algorithms"},{"key":"9421_CR47","unstructured":"Wan, C.: Coalitions in nonatomic network congestion games. arXiv: 1203.5822v1"},{"key":"9421_CR48","first-page":"325","volume-title":"Proc. Institute of Civil Engineers, Pt. II","author":"J.G. Wardrop","year":"1952","unstructured":"Wardrop, J.G.: Some theoretical aspects of road traffic research. In: Proc. Institute of Civil Engineers, Pt. II, vol. 1, pp. 325\u2013378 (1952)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9421-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-012-9421-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9421-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,25]],"date-time":"2023-06-25T02:04:32Z","timestamp":1687658672000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-012-9421-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,2]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["9421"],"URL":"https:\/\/doi.org\/10.1007\/s00224-012-9421-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,2]]}}}