{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:18:37Z","timestamp":1773656317524,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540438649","type":"print"},{"value":"9783540454656","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45465-9_12","type":"book-chapter","created":{"date-parts":[[2007,5,26]],"date-time":"2007-05-26T21:12:57Z","timestamp":1180213977000},"page":"123-134","source":"Crossref","is-referenced-by-count":112,"title":["The Structure and Complexity of Nash Equilibria for a Selfish Routing Game"],"prefix":"10.1007","author":[{"given":"Dimitris","family":"Fotakis","sequence":"first","affiliation":[]},{"given":"Spyros","family":"Kontogiannis","sequence":"additional","affiliation":[]},{"given":"Elias","family":"Koutsoupias","sequence":"additional","affiliation":[]},{"given":"Marios","family":"Mavronicolas","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Spirakis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,6,25]]},"reference":[{"key":"12_CR1","unstructured":"A. Czumaj and B. V\u00f6cking, \u201cTight Bounds for Worst-Case Equilibria\u201d, Proceedings of the 13th Annual ACM Symposium on Discrete Algorithms, January 2002."},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"X. Deng, C. Papadimitriou and S. Safra, \u201cOn the Complexity of Equilibria\u201d, Proceedings of the 34th Annual ACM Symposium on Theory of Computing, May 2002.","DOI":"10.1145\/509907.509920"},{"key":"12_CR3","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0899-8256(89)90006-7","volume":"1","author":"I. Gilboa","year":"1989","unstructured":"I. Gilboa and E. Zemel, \u201cNash and Correlated Equilibria: Some Complexity Considerations\u201d, Games and Economic Behavior, Vol. 1, pp. 80\u201393, 1989.","journal-title":"Games and Economic Behavior"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"R. L. Graham","year":"1969","unstructured":"R. L. Graham, \u201cBounds on Multiprocessing Timing Anomalies,\u201d SIAM Journal on Applied Mathematics, Vol. 17, pp. 416\u2013429, 1969.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"12_CR5","unstructured":"G. R. Grimmett and D. R. Stirzaker, Probability and Random Processes, Oxford Science Publications, Second Edition, 1992."},{"key":"12_CR6","unstructured":"E. Koutsoupias, M. Mavronicolas and P. Spirakis, \u201cApproximate Equilibria and Ball Fusion,\u201d Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity, June 2002."},{"key":"12_CR7","series-title":"Lect Notes Comput Sci","first-page":"404","volume-title":"Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science","author":"K. E","year":"1999","unstructured":"E. Koutsoupias and C. H. Papadimitriou, \u201cWorst-case Equilibria,\u201d Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, LNCS 1563, pp. 404\u2013413, 1999."},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0112033","volume":"12","author":"C. E. Lemke","year":"1964","unstructured":"C. E. Lemke and J. T. Howson, \u201cEquilibrium Points of Bimatrix Games,\u201d Journal of the Society for Industrial and Applied Mathematics, Vol. 12, pp. 413\u2013423, 1964.","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"M. Mavronicolas and P. Spirakis, \u201cThe Price of Selfish Routing,\u201d Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 510\u2013519, 2001.","DOI":"10.1145\/380752.380846"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"R. D. McKelvey and A. McLennan, \u201cComputation of Equilibria in Finite Games,\u201d in Handbook of Computational Economics, H. Amman, D. Kendrick and J. Rust eds., pp. 87\u2013142, 1996.","DOI":"10.1016\/S1574-0021(96)01004-0"},{"key":"12_CR11","volume-title":"Research Report RJ6439","author":"N. Megiddo","year":"1988","unstructured":"N. Megiddo, \u201cA Note on the Complexity of P-Matrix LCP and Computing an Equilibrium,\u201d Research Report RJ6439, IBM Almaden Research Center, San Jose, CA95120, 1988."},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(91)90200-L","volume":"81","author":"N. Megiddo","year":"1991","unstructured":"N. Megiddo and C. H. Papadimitriou, \u201cOn Total Functions, Existence Theorems, and Computational Complexity,\u201d Theoretical Computer Science, Vol. 81, No. 2, pp. 317\u2013324, 1991.","journal-title":"Theoretical Computer Science"},{"key":"12_CR13","unstructured":"B. Monien, Personal Communication, April 2002."},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"J. F. Nash","year":"1951","unstructured":"J. F. Nash, \u201cNon-cooperative Games,\u201d Annals of Mathematics, Vol. 54, No. 2, pp. 286\u2013295, 1951.","journal-title":"Annals of Mathematics"},{"key":"12_CR15","unstructured":"M. J. Osborne and A. Rubinstein, A Course in Game Theory, MIT Press, 1994."},{"key":"12_CR16","unstructured":"C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994."},{"issue":"3","key":"12_CR17","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"C. H. Papadimitriou","year":"1994","unstructured":"C. H. Papadimitriou, \u201cOn the Complexity of the Parity Argument and Other Inefficient Proofs of Existence,\u201d Journal of Computer and System Sciences, Vol. 48, No. 3, pp. 498\u2013532, June 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"12_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-48224-5_1","volume-title":"Proceedings of the 28th International Colloquium on Automata, Languages and Programming","author":"C. H. Papadimitriou","year":"2001","unstructured":"C. H. Papadimitriou, \u201cAlgorithms, Games and the Internet,\u201d Proceedings of the 28th International Colloquium on Automata, Languages and Programming, LNCS 2076, pp. 1\u20133, 2001."},{"key":"12_CR19","unstructured":"B. von Stengel, \u201cComputing Equlibria for Two-Person Games,\u201d in Handbook of Game Theory, Vol. 3, R. J. Aumann and S. Hart eds., North Holland, 1998."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45465-9_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T07:05:40Z","timestamp":1556435140000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45465-9_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438649","9783540454656"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-45465-9_12","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}