{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:52Z","timestamp":1759638292932},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540202165"},{"type":"electronic","value":"9783540452089"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45208-9_1","type":"book-chapter","created":{"date-parts":[[2010,6,28]],"date-time":"2010-06-28T00:49:20Z","timestamp":1277686160000},"page":"1-20","source":"Crossref","is-referenced-by-count":22,"title":["Extreme Nash Equilibria"],"prefix":"10.1007","author":[{"given":"Martin","family":"Gairing","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"L\u00fccking","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marios","family":"Mavronicolas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Burkhard","family":"Monien","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-2","key":"1_CR1","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0166-218X(96)00036-4","volume":"72","author":"P. Brucker","year":"1997","unstructured":"Brucker, P., Hurink, J., Werner, F.: Improving Local Search Heuristics for Some Scheduling Problems. Part II. Discrete Applied Mathematics\u00a072(1-2), 47\u201369 (1997)","journal-title":"Discrete Applied Mathematics"},{"key":"1_CR2","unstructured":"Czumaj, A., V\u00f6cking, B.: Tight Bounds forWorst-Case Equilibria. In: Proceedings of the 13th Annual ACM Symposium on Discrete Algorithms, January 2002, pp. 413\u2013420 (2002)"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Deng, X., Papadimitriou, C., Safra, S.: On the Complexity of Equilibri. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, May 2002, pp. 67\u201371 (2002)","DOI":"10.1145\/509907.509920"},{"key":"1_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1007\/3-540-45061-0_42","volume-title":"Automata, Languages and Programming","author":"R. Feldmann","year":"2003","unstructured":"Feldmann, R., Gairing, M., L\u00fccking, T., Monien, B., Rode, M.: Nashification and the Coordination Ratio for a Selfish Routing Game. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 514\u2013526. Springer, Heidelberg (2003)"},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/BF01930985","volume":"19","author":"G. Finn","year":"1979","unstructured":"Finn, G., Horowitz, E.: A linear time approximation algorithm for multiprocessor scheduling. BIT\u00a019, 312\u2013320 (1979)","journal-title":"BIT"},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/3-540-45465-9_12","volume-title":"Automata, Languages and Programming","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: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 123\u2013134. Springer, Heidelberg (2002)"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1137\/0204035","volume":"4","author":"M.R. Garey","year":"1975","unstructured":"Garey, M.R., Johnson, D.S.: Complexity Results for Multiprocessor Scheduling Under Resoiurce Constraints. SIAM Journal on Computing\u00a04, 397\u2013411 (1975)","journal-title":"SIAM Journal on Computing"},{"key":"1_CR8","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. W. H. Freeman and Company, New York (1979)"},{"issue":"2","key":"1_CR9","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/322248.322254","volume":"28","author":"G.H. Gonnet","year":"1981","unstructured":"Gonnet, G.H.: Expected Length of the Longest Probe Sequence in Hash Code Searching. Journal of the ACM\u00a028(2), 289\u2013304 (1981)","journal-title":"Journal of the ACM"},{"issue":"1","key":"1_CR10","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D.S. Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.: Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results. Journal of the ACM\u00a034(1), 144\u2013162 (1987)","journal-title":"Journal of the ACM"},{"issue":"2","key":"1_CR11","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1145\/321941.321951","volume":"23","author":"E. Horowitz","year":"1976","unstructured":"Horowitz, E., Sahni, S.: Exact and Approximate Algorithms for Scheduling Non-Identical Processors. Journal of the ACM\u00a023(2), 317\u2013327 (1976)","journal-title":"Journal of the ACM"},{"key":"1_CR12","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"1_CR13","volume-title":"Random Allocations","author":"V.F. Kolchin","year":"1978","unstructured":"Kolchin, V.F., Chistiakov, V.P., Sevastianov, B.A.: Random Allocations. V. H. Winston, New York (1978)"},{"key":"1_CR14","unstructured":"Koutsoupias, E., Mavronicolas, M., Spirakis, P.: Approximate Equilibria and Ball Fusion. In: Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity, Andros, Greece (June 2002) (Accepted to Theory of Computing Systems); Earlier version appeared as A Tight Bound on Coordination Ratio, Technical Report 0100229, Department of Computer Science, University of California at Los Angeles (April 2001)"},{"key":"1_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1007\/3-540-49116-3_38","volume-title":"STACS 99","author":"E. Koutsoupias","year":"1999","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: Worst-case Equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 404\u2013413. Springer, Heidelberg (1999)"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"L\u00fccking, T., Mavronicolas, M., Monien, B., Rode, M., Spirakis, P., Vrto, I.: Which is theWorst-case Nash Equilibrium? In: 26th International Symposium on Mathematical Foundations of Computer Science (August 2003) (to appear)","DOI":"10.1007\/978-3-540-45138-9_49"},{"key":"1_CR17","volume-title":"Theory of Majorization and Its Applications","author":"A. Marshall","year":"1979","unstructured":"Marshall, A., Olkin, I.: Theory of Majorization and Its Applications. Academic Press, Orlando (1979)"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Mavronicolas, M., Spirakis, P.: The Price of Selfish Routing. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, July 2001, pp. 510\u2013519 (2001)","DOI":"10.1145\/380752.380846"},{"key":"1_CR19","volume-title":"Probabilistic Methods for Algorithmic Discrete Mathematics","author":"C. McDiarmid","year":"1998","unstructured":"McDiarmid, C.: \u201cConcentration. In: Habib, M., McDiarmidt, C., Ramires-Alfonsin, J., Reed, B. (eds.) Probabilistic Methods for Algorithmic Discrete Mathematics, vol.\u00a0ch. 9, Springer, Heidelberg (1998)"},{"issue":"3\/4","key":"1_CR20","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF01769190","volume":"7","author":"H. Moulin","year":"1978","unstructured":"Moulin, H., Vial, L.: Strategically Zero-Sum Games: The Class of Games whose Completely Mixed Equilibria Cannot be Improved Upon. International Journal of Game Theory\u00a07(3\/4), 201\u2013221 (1978)","journal-title":"International Journal of Game Theory"},{"key":"1_CR21","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"J.F. Nash","year":"1950","unstructured":"Nash, J.F.: Equilibrium Points in N-Person Games. Proceedings of the National Academy of Sciences\u00a036, 48\u201349 (1950)","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"2","key":"1_CR22","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"J.F. Nash","year":"1951","unstructured":"Nash, J.F.: Non-cooperative Games. Annals of Mathematics\u00a054(2), 286\u2013295 (1951)","journal-title":"Annals of Mathematics"},{"key":"1_CR23","volume-title":"A Course in Game Theory","author":"M.J. Osborne","year":"1994","unstructured":"Osborne, M.J., Rubinstein, A.: A Course in Game Theory. The MIT Press, Cambridge (1994)"},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: Algorithms, Games and the Internet. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, July 2001, pp. 749\u2013753 (2001)","DOI":"10.1145\/380752.380883"},{"issue":"2","key":"1_CR25","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1112\/jlms\/2.Part_4.709","volume":"2","author":"T.E.S. Raghavan","year":"1970","unstructured":"Raghavan, T.E.S.: Completely Mixed Strategies in Bimatrix Games. Journal of London Mathematical Society\u00a02(2), 709\u2013712 (1970)","journal-title":"Journal of London Mathematical Society"},{"key":"1_CR26","volume-title":"Stochastic Processes","author":"S.M. Ross","year":"1996","unstructured":"Ross, S.M.: Stochastic Processes, 2nd edn. John Wiley & Sons, Inc., Chichester (1996)","edition":"2"},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"Schuurman, P., Vredeveld, T.: Performance Guarantees of Load Search for Multiprocessor Scheduling. In: Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization, June 2001, pp. 370\u2013382 (2001)","DOI":"10.1007\/3-540-45535-3_29"},{"key":"1_CR28","volume-title":"Stochastic Orders and Their Applications","author":"M. Shaked","year":"1994","unstructured":"Shaked, M., Shanthikumar, J.G.: Stochastic Orders and Their Applications. Academic Press, San Diego (1994)"},{"key":"1_CR29","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 IEEE Symposium on Foundations of Computer Science, October 2002, pp. 416\u2013425 (2002)","DOI":"10.1109\/SFCS.2002.1181966"}],"container-title":["Lecture Notes in Computer Science","Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45208-9_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T09:40:47Z","timestamp":1559209247000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45208-9_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540202165","9783540452089"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45208-9_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}