{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T07:48:38Z","timestamp":1764402518948,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642232169"},{"type":"electronic","value":"9783642232176"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23217-6_32","type":"book-chapter","created":{"date-parts":[[2011,8,25]],"date-time":"2011-08-25T09:14:02Z","timestamp":1314263642000},"page":"482-496","source":"Crossref","is-referenced-by-count":21,"title":["The Complexity of Nash Equilibria in Limit-Average Games"],"prefix":"10.1007","author":[{"given":"Michael","family":"Ummels","sequence":"first","affiliation":[]},{"given":"Dominik","family":"Wojtczak","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"5","key":"32_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 Journal on Computing\u00a038(5), 1987\u20132006 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"32_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/978-3-642-00596-1_24","volume-title":"Foundations of Software Science and Computational Structures","author":"R. Alur","year":"2009","unstructured":"Alur, R., Degorre, A., Maler, O., Weiss, G.: On omega-languages defined by mean-payoff conditions. In: de Alfaro, L. (ed.) FOSSACS 2009. LNCS, vol.\u00a05504, pp. 333\u2013347. Springer, Heidelberg (2009)"},{"key":"32_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/978-3-642-15375-4_14","volume-title":"CONCUR 2010 - Concurrency Theory","author":"P. Bouyer","year":"2010","unstructured":"Bouyer, P., Brenguier, R., Markey, N.: Nash equilibria for reachability objectives in multi-player timed games. In: Gastin, P., Laroussinie, F. (eds.) CONCUR 2010. LNCS, vol.\u00a06269, pp. 192\u2013206. Springer, Heidelberg (2010)"},{"key":"32_CR4","first-page":"460","volume-title":"STOC 1988","author":"J. Canny","year":"1988","unstructured":"Canny, J.: Some algebraic and geometric computations in PSPACE. In: STOC 1988, pp. 460\u2013469. ACM Press, New York (1988)"},{"key":"32_CR5","unstructured":"Chatterjee, K., Doyen, L., Henzinger, T.A., Raskin, J.-F.: Generalized mean-payoff and energy games. In: FSTTCS\u00a02010. LIPICS, vol.\u00a08. Schloss Dagstuhl (2010)"},{"key":"32_CR6","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player Nash equilibria. Journal of the ACM\u00a056(3) (2009)","DOI":"10.1145\/1516512.1516516"},{"key":"32_CR7","first-page":"765","volume-title":"IJCAI\u00a02003","author":"V. Conitzer","year":"2003","unstructured":"Conitzer, V., Sandholm, T.: Complexity results about Nash equilibria. In: IJCAI\u00a02003, pp. 765\u2013771. Morgan Kaufmann, San Francisco (2003)"},{"issue":"1","key":"32_CR8","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/070699652","volume":"39","author":"C. Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM Journal on Computing\u00a039(1), 195\u2013259 (2009)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"32_CR9","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1016\/j.tcs.2007.07.008","volume":"386","author":"L. de Alfaro","year":"2007","unstructured":"de Alfaro, L., Henzinger, T.A., Kupferman, O.: Concurrent reachability games. Theoretical Computer Science\u00a0386(3), 188\u2013217 (2007)","journal-title":"Theoretical Computer Science"},{"key":"32_CR10","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. International Journal of Game Theory\u00a08, 109\u2013113 (1979)","journal-title":"International Journal of Game Theory"},{"issue":"6","key":"32_CR11","doi-asserted-by":"publisher","first-page":"2531","DOI":"10.1137\/080720826","volume":"39","author":"K. Etessami","year":"2010","unstructured":"Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. SIAM Journal on Computing\u00a039(6), 2531\u20132597 (2010)","journal-title":"SIAM Journal on Computing"},{"key":"32_CR12","series-title":"Annals of Mathematical Studies","first-page":"47","volume-title":"Contributions to the Theory of Games III","author":"H. Everett","year":"1957","unstructured":"Everett, H.: Recursive games. In: Dresher, M., Tucker, A.W., Wolfe, P. (eds.) Contributions to the Theory of Games III. Annals of Mathematical Studies, vol.\u00a039, pp. 47\u201378. Princeton University Press, Princeton (1957)"},{"issue":"1","key":"32_CR13","first-page":"89","volume":"28","author":"A.M. Fink","year":"1964","unstructured":"Fink, A.M.: Equilibrium in a stochastic n-person game. Journal of Science in Hiroshima University\u00a028(1), 89\u201393 (1964)","journal-title":"Journal of Science in Hiroshima University"},{"key":"32_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/978-3-642-12002-2_16","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"D. Fisman","year":"2010","unstructured":"Fisman, D., Kupferman, O., Lustig, Y.: Rational synthesis. In: Esparza, J., Majumdar, R. (eds.) TACAS 2010. LNCS, vol.\u00a06015, pp. 190\u2013204. Springer, Heidelberg (2010)"},{"key":"32_CR15","first-page":"10","volume-title":"STOC 1976","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: Some NP-complete geometric problems. In: STOC 1976, pp. 10\u201322. ACM Press, New York (1976)"},{"key":"32_CR16","series-title":"Annals of Mathematical Studies","first-page":"179","volume-title":"Contributions to the Theory of Games III","author":"D. Gillette","year":"1957","unstructured":"Gillette, D.: Stochastic games with zero stop probabilities. In: Dresher, M., Tucker, A.W., Wolfe, P. (eds.) Contributions to the Theory of Games III. Annals of Mathematical Studies, vol.\u00a039, pp. 179\u2013187. Princeton University Press, Princeton (1957)"},{"key":"32_CR17","unstructured":"Henzinger, T.A.: Games in system design and verification. In: TARK\u00a02005, pp. 1\u20134. National University of Singapore (2005)"},{"issue":"3","key":"32_CR18","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","volume":"23","author":"R.M. Karp","year":"1978","unstructured":"Karp, R.M.: A characterization of the minimum cycle mean in a digraph. Discrete Mathematics\u00a023(3), 309\u2013311 (1978)","journal-title":"Discrete Mathematics"},{"issue":"2","key":"32_CR19","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01769259","volume":"10","author":"J.-F. Mertens","year":"1981","unstructured":"Mertens, J.-F., Neyman, A.: Stochastic games. International Journal of Game Theory\u00a010(2), 53\u201366 (1981)","journal-title":"International Journal of Game Theory"},{"key":"32_CR20","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"J.F. Nash Jr.","year":"1950","unstructured":"Nash Jr., J.F.: Equilibrium points in N-person games. Proceedings of the National Academy of Sciences of the USA\u00a036, 48\u201349 (1950)","journal-title":"Proceedings of the National Academy of Sciences of the USA"},{"key":"32_CR21","series-title":"NATO Science Series C","volume-title":"Stochastic Games and Applications","year":"2003","unstructured":"Neyman, A., Sorin, S. (eds.): Stochastic Games and Applications. NATO Science Series C, vol.\u00a0570. Springer, Heidelberg (2003)"},{"key":"32_CR22","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316887","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"M.L. Puterman","year":"1994","unstructured":"Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, Chichester (1994)"},{"key":"32_CR23","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. Proceedings of the National Academy of Sciences of the USA\u00a039, 1095\u20131100 (1953)","journal-title":"Proceedings of the National Academy of Sciences of the USA"},{"key":"32_CR24","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/BF01263280","volume":"26","author":"F. Thuijsman","year":"1997","unstructured":"Thuijsman, F., Raghavan, T.E.S.: Perfect-information stochastic games and related classes. International Journal of Game Theory\u00a026, 403\u2013408 (1997)","journal-title":"International Journal of Game Theory"},{"key":"32_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/978-3-540-78499-9_3","volume-title":"Foundations of Software Science and Computational Structures","author":"M. Ummels","year":"2008","unstructured":"Ummels, M.: The complexity of nash equilibria in infinite multiplayer games. In: Amadio, R.M. (ed.) FOSSACS 2008. LNCS, vol.\u00a04962, pp. 20\u201334. Springer, Heidelberg (2008)"},{"key":"32_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/978-3-642-02930-1_25","volume-title":"Automata, Languages and Programming","author":"M. Ummels","year":"2009","unstructured":"Ummels, M., Wojtczak, D.: The complexity of nash equilibria in simple stochastic multiplayer games. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05556, pp. 297\u2013308. Springer, Heidelberg (2009)"},{"key":"32_CR27","doi-asserted-by":"crossref","unstructured":"Ummels, M., Wojtczak, D.: The complexity of Nash equilibria in limit-average games. Tech. Rep. LSV-11-15, ENS Cachan (2011)","DOI":"10.2168\/LMCS-7(3:20)2011"},{"key":"32_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-642-19805-2_19","volume-title":"Foundations of Software Science and Computational Structures","author":"Y. Velner","year":"2011","unstructured":"Velner, Y., Rabinovich, A.: Church synthesis problem for noisy input. In: Hofmann, M. (ed.) FOSSACS 2011. LNCS, vol.\u00a06604, pp. 275\u2013289. Springer, Heidelberg (2011)"},{"issue":"1","key":"32_CR29","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF02810663","volume":"119","author":"N. Vielle","year":"2000","unstructured":"Vielle, N.: Two-player stochastic games I: A reduction. Israel Journal of Mathematics\u00a0119(1), 55\u201391 (2000)","journal-title":"Israel Journal of Mathematics"},{"issue":"1","key":"32_CR30","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BF02810664","volume":"119","author":"N. Vielle","year":"2000","unstructured":"Vielle, N.: Two-player stochastic games II: The case of recursive games. Israel Journal of Mathematics\u00a0119(1), 93\u2013126 (2000b)","journal-title":"Israel Journal of Mathematics"},{"key":"32_CR31","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/0022-247X(90)90267-J","volume":"153","author":"A.R. Washburn","year":"1990","unstructured":"Washburn, A.R.: Deterministic graphical games. Journal of Mathematical Analysis and Applications\u00a0153, 84\u201396 (1990)","journal-title":"Journal of Mathematical Analysis and Applications"},{"issue":"1-2","key":"32_CR32","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.: The complexity of mean payoff games on graphs. Theoretical Computer Science\u00a0158(1-2), 343\u2013359 (1996)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","CONCUR 2011 \u2013 Concurrency Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23217-6_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T20:17:08Z","timestamp":1558297028000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23217-6_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642232169","9783642232176"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23217-6_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}