{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:10:04Z","timestamp":1725559804105},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540275800"},{"type":"electronic","value":"9783540316916"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11523468_41","type":"book-chapter","created":{"date-parts":[[2010,7,18]],"date-time":"2010-07-18T18:58:59Z","timestamp":1279479539000},"page":"497-512","source":"Crossref","is-referenced-by-count":11,"title":["Braess\u2019s Paradox, Fibonacci Numbers, and Exponential Inapproximability"],"prefix":"10.1007","author":[{"given":"Henry","family":"Lin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim","family":"Roughgarden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u00c9va","family":"Tardos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Asher","family":"Walkover","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"41_CR1","doi-asserted-by":"crossref","unstructured":"Anshelevich, E., Dasgupta, A., Tardos, \u00c9., Wexler, T.: Near-optimal network design with selfish agents. In: Proceedings of the 35th Annual ACM Symposium on the Theory of Computing (STOC), pp. 511\u2013520 (2003)","DOI":"10.1145\/780615.780617"},{"key":"41_CR2","unstructured":"Beckmann, M., McGuire, C.B., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press (1956)"},{"key":"41_CR3","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/BF01918335","volume":"12","author":"D. Braess","year":"1968","unstructured":"Braess, D.: \u00dcber ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung\u00a012, 258\u2013268 (1968)","journal-title":"Unternehmensforschung"},{"issue":"5","key":"41_CR4","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0167-6377(03)00030-0","volume":"31","author":"C.K. Chau","year":"2003","unstructured":"Chau, C.K., Sim, K.M.: The price of anarchy for non-atomic congestion games with symmetric cost maps and elastic demands. Operations Research Letters\u00a031(5), 327\u2013335 (2003)","journal-title":"Operations Research Letters"},{"key":"41_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-540-25960-2_5","volume-title":"Integer Programming and Combinatorial Optimization","author":"J.R. Correa","year":"2004","unstructured":"Correa, J.R., Schulz, A.S., Stier Moses, N.E.: Computational complexity, fairness, and the price of anarchy of the maximum latency problem. In: Bienstock, D., Nemhauser, G.L. (eds.) IPCO 2004. LNCS, vol.\u00a03064, pp. 59\u201373. Springer, Heidelberg (2004)"},{"issue":"4","key":"41_CR6","doi-asserted-by":"publisher","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. Mathematics of Operations Research\u00a029(4), 961\u2013976 (2004)","journal-title":"Mathematics of Operations Research"},{"key":"41_CR7","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis, ch. 42","author":"A. Czumaj","year":"2004","unstructured":"Czumaj, A.: Selfish routing on the Internet. In: Leung, J. (ed.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis, ch. 42, CRC Press, Boca Raton (2004)"},{"key":"41_CR8","unstructured":"Devanur, N., Garg, N., Khandekar, R., Pandit, V., Saberi, A.: Price of anarchy, locality gap, and a network service provider game (2003) (Unpublished manuscript)"},{"key":"41_CR9","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C.H., Shenker, S.J.: On a network creation game. In: Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC), pp. 347\u2013351 (2003)","DOI":"10.1145\/872035.872088"},{"key":"41_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-540-45138-9_2","volume-title":"Mathematical Foundations of Computer Science 2003","author":"R. Feldmann","year":"2003","unstructured":"Feldmann, R., Gairing, M., L\u00fccking, T., Monien, B., Rode, M.: Selfish routing in non-cooperative networks: A survey. In: Rovan, B., Vojt\u00e1\u0161, P. (eds.) MFCS 2003. LNCS, vol.\u00a02747, pp. 21\u201345. Springer, Heidelberg (2003)"},{"key":"41_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"issue":"3","key":"41_CR12","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1287\/moor.1040.0091","volume":"29","author":"R. Johari","year":"2004","unstructured":"Johari, R., Tsitsiklis, J.N.: Efficiency loss in a network resource allocation game. Mathematics of Operations Research\u00a029(3), 407\u2013435 (2004)","journal-title":"Mathematics of Operations Research"},{"key":"41_CR13","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. In: Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 404\u2013413 (1999)","DOI":"10.1007\/3-540-49116-3_38"},{"key":"41_CR14","unstructured":"Lin, H., Roughgarden, T., Tardos, \u00c9.: A stronger bound on braess\u2019s paradox. In: Proceedings of the 15th Annual Symposium on Discrete Algorithms (SODA), pp. 333\u2013334 (2004)"},{"key":"41_CR15","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: Algorithms, games, and the Internet. In: Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing (STOC), pp. 749\u2013753 (2001)","DOI":"10.1145\/380752.380883"},{"key":"41_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/978-3-540-25960-2_4","volume-title":"Integer Programming and Combinatorial Optimization","author":"G. Perakis","year":"2004","unstructured":"Perakis, G.: The price of anarchy when costs are non-separable and asymmetric. In: Bienstock, D., Nemhauser, G.L. (eds.) IPCO 2004. LNCS, vol.\u00a03064, pp. 46\u201358. Springer, Heidelberg (2004)"},{"key":"41_CR17","doi-asserted-by":"crossref","unstructured":"Roughgarden, T.: Designing networks for selfish users is hard. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pp. 472\u2013481 (2001)","DOI":"10.1109\/SFCS.2001.959923"},{"issue":"2","key":"41_CR18","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/S0022-0000(03)00044-8","volume":"67","author":"T. Roughgarden","year":"2003","unstructured":"Roughgarden, T.: The price of anarchy is independent of the network topology. Journal of Computer and System Sciences\u00a067(2), 341\u2013364 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"41_CR19","unstructured":"Roughgarden, T.: The maximum latency of selfish routing. In: Proceedings of the 15th Annual Symposium on Discrete Algorithms (SODA), pp. 973\u2013974 (2004)"},{"key":"41_CR20","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":"2","key":"41_CR21","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/506147.506153","volume":"49","author":"T. Roughgarden","year":"2002","unstructured":"Roughgarden, T., Tardos, \u00c9.: How bad is selfish routing? Journal of the ACM\u00a049(2), 236\u2013259 (2002)","journal-title":"Journal of the ACM"},{"issue":"2","key":"41_CR22","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1016\/j.geb.2003.06.004","volume":"47","author":"T. Roughgarden","year":"2004","unstructured":"Roughgarden, T., Tardos, \u00c9.: Bounding the inefficiency of equilibria in nonatomic congestion games. Games and Economic Behavior\u00a047(2), 389\u2013403 (2004)","journal-title":"Games and Economic Behavior"},{"key":"41_CR23","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0191-2615(79)90022-5","volume":"13B","author":"M.J. Smith","year":"1979","unstructured":"Smith, M.J.: The existence, uniqueness and stability of traffic equilibria. Transportation Research\u00a013B, 295\u2013304 (1979)","journal-title":"Transportation Research"},{"key":"41_CR24","doi-asserted-by":"crossref","unstructured":"Vetta, A.: Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In: Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 416\u2013425 (2002)","DOI":"10.1109\/SFCS.2002.1181966"},{"key":"41_CR25","unstructured":"Weitz, D.: The price of anarchy (2001) (Unpublished manuscript)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11523468_41.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:06:08Z","timestamp":1605643568000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11523468_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540275800","9783540316916"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11523468_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}