{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T12:18:37Z","timestamp":1725538717609},"publisher-location":"Berlin, Heidelberg","reference-count":54,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642046445"},{"type":"electronic","value":"9783642046452"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04645-2_2","type":"book-chapter","created":{"date-parts":[[2009,10,7]],"date-time":"2009-10-07T11:14:23Z","timestamp":1254914063000},"page":"2-13","source":"Crossref","is-referenced-by-count":4,"title":["Computational Aspects of Equilibria"],"prefix":"10.1007","author":[{"given":"Mihalis","family":"Yannakakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"2_CR1","doi-asserted-by":"publisher","first-page":"1987","DOI":"10.1137\/070697926","volume":"38","author":"E. Allender","year":"2009","unstructured":"Allender, E., B\u00fcrgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P.B.: On the complexity of numerical analysis. SIAM J. Computing\u00a038(5), 1987\u20132006 (2009); Preliminary version in Proc. 21st IEEE Comp. Compl. Conf. (2006)","journal-title":"SIAM J. Computing"},{"key":"2_CR2","doi-asserted-by":"publisher","first-page":"265","DOI":"10.2307\/1907353","volume":"22","author":"K.J. Arrow","year":"1954","unstructured":"Arrow, K.J., Debreu, G.: Existence of an equilibrium for a competitive economy. Econometrica\u00a022, 265\u2013290 (1954)","journal-title":"Econometrica"},{"key":"2_CR3","doi-asserted-by":"publisher","first-page":"229","DOI":"10.2307\/2000571","volume":"296","author":"R.M. Anderson","year":"1986","unstructured":"Anderson, R.M.: \u201cAlmost\u201d implies \u201cNear\u201d. Trans. Am. Math. Soc.\u00a0296, 229\u2013237 (1986)","journal-title":"Trans. Am. Math. Soc."},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Bertoni, A., Mauri, G., Sabadini, N.: A characterization of the class of functions computable in polynomial time on random access machines. Proc. ACM Symp. Th. of Comp., 168\u2013176 (1981)","DOI":"10.1145\/800076.802470"},{"key":"2_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and Real Computation","author":"L. Blum","year":"1998","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, Heidelberg (1998)"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Chaterjee, K., Doyen, L., Henzinger, T.: A survey of stochastic games with limsup and liminf objectives. In: Proc. 36th ICALP, Part II, pp. 1\u201315 (2009)","DOI":"10.1007\/978-3-642-02930-1_1"},{"key":"#cr-split#-2_CR7.1","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.H.: Settling the complexity of computing two-player Nash equilibria. J. of ACM??56(3) (2009);","DOI":"10.1145\/1516512.1516516"},{"key":"#cr-split#-2_CR7.2","unstructured":"Preliminary version in FOCS 2006"},{"key":"2_CR8","unstructured":"Chen, X., Teng, S.H., Valiant, P.: The approximation complexity of win-lose games. In: Proc. 18th ACM SODA (2007)"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Cole, R., Fleischer, L.: Fast-converging tatonnement algorithms for one-time and ongoing market problems. In: Proc. 40th ACM STOC (2008)","DOI":"10.1145\/1374376.1374422"},{"issue":"2","key":"2_CR10","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0890-5401(92)90048-K","volume":"96","author":"A. Condon","year":"1992","unstructured":"Condon, A.: The complexity of stochastic games. Inf. & Comp.\u00a096(2), 203\u2013224 (1992)","journal-title":"Inf. & Comp."},{"key":"#cr-split#-2_CR11.1","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Goldberg, P., Papadimitriou, C.: The complexity of computing a Nash equilibrium. SIAM J. on Computing (2009);","DOI":"10.1137\/070699652"},{"key":"#cr-split#-2_CR11.2","unstructured":"Preliminary version in STOC 2006"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"de Alfaro, L., Henzinger, T.A., Kupferman, O.: Concurrent reachability games. In: Proc. IEEE FOCS, pp. 564\u2013575 (1998)","DOI":"10.1109\/SFCS.1998.743507"},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01768705","volume":"8","author":"A. Ehrenfeucht","year":"1979","unstructured":"Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. Intl. J. Game Theory\u00a08, 109\u2013113 (1979)","journal-title":"Intl. J. Game Theory"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Emerson, E.A., Jutla, C.: Tree automata, \u03bc-calculus and determinacy. In: Proc. IEEE FOCS, pp. 368\u2013377 (1991)","DOI":"10.1109\/SFCS.1991.185392"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. Proc. IEEE FOCS (2007)","DOI":"10.1109\/FOCS.2007.39"},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"891","DOI":"10.1007\/11523468_72","volume-title":"Automata, Languages and Programming","author":"K. Etessami","year":"2005","unstructured":"Etessami, K., Yannakakis, M.: Recursive Markov decision processes and recursive stochastic games. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 891\u2013903. Springer, Heidelberg (2005)"},{"key":"2_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1007\/11672142_52","volume-title":"STACS 2006","author":"K. Etessami","year":"2006","unstructured":"Etessami, K., Yannakakis, M.: Efficient qualitative analysis of classes of recursive Markov decision processes and simple stochastic games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 634\u2013645. Springer, Heidelberg (2006)"},{"key":"2_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/11787006_28","volume-title":"Automata, Languages and Programming","author":"K. Etessami","year":"2006","unstructured":"Etessami, K., Yannakakis, M.: Recursive concurrent stochastic games. Logical Methods in Computer Science\u00a04(4:7), 1\u201321 (2008); Preliminary version in: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04052, pp. 324\u2013335. Springer, Heidelberg (2006)"},{"key":"2_CR19","unstructured":"Etessami, K., Yannakakis, M.: Manuscript (2009)"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The complexity of pure Nash equilibria. In: Proc. ACM STOC, pp. 604\u2013612 (2004)","DOI":"10.1145\/1007352.1007445"},{"key":"2_CR21","volume-title":"Competitive Markov Decision Processes","author":"J. Filar","year":"1997","unstructured":"Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer, Heidelberg (1997)"},{"key":"2_CR22","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0899-8256(89)90006-7","volume":"1","author":"I. Gilboa","year":"1989","unstructured":"Gilboa, I., Zemel, E.: Nash and correlated equilibria: some complexity considerations. Games and Economic Behavior\u00a01, 80\u201393 (1989)","journal-title":"Games and Economic Behavior"},{"key":"2_CR23","volume-title":"A General Theory of Equilibrium Selection in Games","author":"J.C. Harsanyi","year":"1988","unstructured":"Harsanyi, J.C., Selten, R.: A General Theory of Equilibrium Selection in Games. MIT Press, Cambridge (1988)"},{"issue":"2","key":"2_CR24","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0304-4068(96)00770-7","volume":"27","author":"P.J.-J. Herings","year":"1997","unstructured":"Herings, P.J.-J.: A globally and universally stable price adjustment process. J. of Mathematical Economics\u00a027(2), 163\u2013193 (1997)","journal-title":"J. of Mathematical Economics"},{"key":"2_CR25","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/S0304-4068(02)00060-5","volume":"38","author":"P.J.-J. Herings","year":"2002","unstructured":"Herings, P.J.-J.: Universally converging adjustment processes - a unifying approach. J. of Mathematical Economics\u00a038, 341\u2013370 (2002)","journal-title":"J. of Mathematical Economics"},{"key":"2_CR26","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/0885-064X(89)90017-4","volume":"5","author":"M.D. Hirsch","year":"1989","unstructured":"Hirsch, M.D., Papadimitriou, C.H., Vavasis, S.A.: Exponential lower bounds for finding Brower fixed points. J. Complexity\u00a05, 379\u2013416 (1989)","journal-title":"J. Complexity"},{"key":"2_CR27","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comp. Sys. Sci.\u00a037, 79\u2013100 (1988)","journal-title":"J. Comp. Sys. Sci."},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0020-0190(98)00150-1","volume":"68","author":"M. Jurdzinski","year":"1998","unstructured":"Jurdzinski, M.: Deciding the winner in parity games is in UP\u2229coUP. Inf. Proc. Let.\u00a068, 119\u2013124 (1998)","journal-title":"Inf. Proc. Let."},{"key":"2_CR29","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/BF00933874","volume":"17","author":"H.W. Kuhn","year":"1975","unstructured":"Kuhn, H.W., MacKinnon, J.G.: Sandwich methods for finding fixed points. J. Opt. Th. Appl.\u00a017, 189\u2013204 (1975)","journal-title":"J. Opt. Th. Appl."},{"key":"2_CR30","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0165-1765(87)90023-1","volume":"23","author":"G. Laan van der","year":"1987","unstructured":"van der Laan, G., Talman, A.J.J.: A convergent price adjustment process. Economics Letters\u00a023, 119\u2013123 (1987)","journal-title":"Economics Letters"},{"key":"2_CR31","doi-asserted-by":"crossref","unstructured":"Lemke, C., Howson, J.: Equilibrium points of bimatrix games. J. SIAM, 413\u2013423 (1964)","DOI":"10.1137\/0112033"},{"key":"2_CR32","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: Proc. ACM Conf. Elec. Comm, pp. 36\u201341 (2003)","DOI":"10.1145\/779928.779933"},{"key":"2_CR33","volume-title":"Microeconomic Theory","author":"A. Mas-Colell","year":"1995","unstructured":"Mas-Colell, A., Whinston, M.D., Green, J.R.: Microeconomic Theory. Oxford Univ. Press, Oxford (1995)"},{"key":"2_CR34","doi-asserted-by":"publisher","first-page":"289","DOI":"10.2307\/1969529","volume":"54","author":"J. Nash","year":"1951","unstructured":"Nash, J.: Non-cooperative games. Annals of Mathematics\u00a054, 289\u2013295 (1951)","journal-title":"Annals of Mathematics"},{"volume-title":"Stochastic Games and Applications","year":"2003","key":"2_CR35","unstructured":"Neyman, A., Sorin, S. (eds.): Stochastic Games and Applications. Kluwer, Dordrecht (2003)"},{"key":"2_CR36","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic Game Theory","author":"N. Nisan","year":"2007","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.: Algorithmic Game Theory. Cambridge Univ. Press, Cambridge (2007)"},{"issue":"3","key":"2_CR37","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci.\u00a048(3), 498\u2013532 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR38","unstructured":"Papadimitriou, C., Yannakakis, M.: An impossibility theorem for price adjustment mechanisms, manuscript (2009)"},{"key":"2_CR39","unstructured":"Puri, A.: Theory of hybrid systems and discrete event systems. PhD Thesis, UC Berkeley (1995)"},{"key":"2_CR40","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1111\/j.1468-0262.2006.00667.x","volume":"74","author":"R. Savani","year":"2006","unstructured":"Savani, R., von Stengel, B.: Hard to solve bimatrix games. Econometrica\u00a074, 397\u2013429 (2006)","journal-title":"Econometrica"},{"key":"2_CR41","doi-asserted-by":"publisher","first-page":"1328","DOI":"10.1137\/0115116","volume":"15","author":"H. Scarf","year":"1967","unstructured":"Scarf, H.: The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math.\u00a015, 1328\u20131343 (1967)","journal-title":"SIAM J. Appl. Math."},{"key":"2_CR42","doi-asserted-by":"crossref","unstructured":"Scarf, H.: The Computation of Economic Equilibria. Yale University Press (1973)","DOI":"10.1057\/978-1-349-95189-5_451"},{"key":"2_CR43","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1073\/pnas.39.10.1095","volume":"39","author":"L.S. Shapley","year":"1953","unstructured":"Shapley, L.S.: Stochastic games. Proc. Nat. Acad. Sci.\u00a039, 1095\u20131100 (1953)","journal-title":"Proc. Nat. Acad. Sci."},{"key":"2_CR44","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195106909.001.0001","volume-title":"Optimal solution of nonlinear equations","author":"K. Sikorski","year":"2001","unstructured":"Sikorski, K.: Optimal solution of nonlinear equations. Oxford Univ. Press, Oxford (2001)"},{"issue":"2","key":"2_CR45","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0304-4068(76)90019-7","volume":"3","author":"S. Smale","year":"1976","unstructured":"Smale, S.: A convergent process of price adjustment and global Newton methods. J.\u00a0of Mathematical Economics\u00a03(2), 107\u2013120 (1976)","journal-title":"J.\u00a0of Mathematical Economics"},{"key":"2_CR46","doi-asserted-by":"crossref","unstructured":"Spirakis, P.: Approximate equilibria for strategic two-person games. In: Proc. 1st Symp. Alg. Game Theory, pp. 5\u201321 (2008)","DOI":"10.1007\/978-3-540-79309-0_3"},{"key":"2_CR47","doi-asserted-by":"crossref","unstructured":"Tiwari, P.: A problem that is easier to solve on the unit-cost algebraic RAM. J. of Complexity, 393\u2013397 (1992)","DOI":"10.1016\/0885-064X(92)90003-T"},{"key":"2_CR48","first-page":"59","volume":"13","author":"H. Uzawa","year":"1962","unstructured":"Uzawa, H.: Walras\u2019 existence theorem and Brower\u2019s fixpoint theorem. Econ. Stud. Quart.\u00a013, 59\u201362 (1962)","journal-title":"Econ. Stud. Quart."},{"key":"2_CR49","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: The analysis of local search problems and their heuristics. In: Proc. STACS, pp. 298\u2013311 (1990)","DOI":"10.1007\/3-540-52282-4_52"},{"key":"2_CR50","volume-title":"Local Search in Combinatorial Optimization","author":"M. Yannakakis","year":"1997","unstructured":"Yannakakis, M.: Computational complexity of local search. In: Aarts, E.H.L., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization. John Wiley, Chichester (1997)"},{"issue":"2","key":"2_CR51","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.cosrev.2009.03.004","volume":"3","author":"M. Yannakakis","year":"2009","unstructured":"Yannakakis, M.: Equilibria, fixed points, and complexity classes. Computeer Science Review\u00a03(2), 71\u201386 (2009); Preliminary version in STACS 2008","journal-title":"Computeer Science Review"},{"key":"2_CR52","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0304-3975(95)00188-3","volume":"158","author":"U. Zwick","year":"1996","unstructured":"Zwick, U., Paterson, M.S.: The complexity of mean payoff games on graphs. Theoretical Computer Science\u00a0158, 343\u2013359 (1996)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04645-2_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,11]],"date-time":"2021-10-11T23:27:00Z","timestamp":1633994820000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04645-2_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642046445","9783642046452"],"references-count":54,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04645-2_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}