[{"date_updated":"2023-02-23T10:30:55Z","dini_type":"doc-type:other","date_created":"2018-12-12T11:39:08Z","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"2162"}]},"publication_status":"published","department":[{"_id":"KrCh","tree":[{"_id":"ResearchGroups"},{"_id":"IST"}]}],"creator":{"id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","login":"dernst"},"file_date_updated":"2020-07-14T12:46:45Z","language":[{}],"oa":1,"month":"07","publication_identifier":{"issn":[]},"oa_version":"Published Version","file":[{"date_created":"2018-12-12T11:53:35Z","date_updated":"2020-07-14T12:46:45Z","checksum":"79ee5e677a82611ce06e0360c69d494a","relation":"main_file","file_id":"5496","content_type":"application/pdf","file_size":517275,"creator":"system","file_name":"IST-2013-127-v1+1_ergodic.pdf","access_level":"open_access"}],"pubrep_id":"127","ddc":[],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"5404","abstract":[{"lang":"eng"}],"alternative_title":[],"type":"technical_report","date_published":"2013-07-03T00:00:00Z","page":"29","citation":{"short":"K. Chatterjee, R. Ibsen-Jensen, The Complexity of Ergodic Games, IST Austria, 2013.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Complexity of Ergodic Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-127-v1-1.","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Complexity of Ergodic Games. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-127-v1-1.","apa":"Chatterjee, K., & Ibsen-Jensen, R. (2013). The complexity of ergodic games. IST Austria. https://doi.org/10.15479/AT:IST-2013-127-v1-1","ieee":"K. Chatterjee and R. Ibsen-Jensen, The complexity of ergodic games. IST Austria, 2013.","ista":"Chatterjee K, Ibsen-Jensen R. 2013. The complexity of ergodic games, IST Austria, 29p."},"day":"03","has_accepted_license":"1","uri_base":"https://research-explorer.ista.ac.at","dc":{"creator":["Chatterjee, Krishnendu","Ibsen-Jensen, Rasmus"],"identifier":["https://research-explorer.ista.ac.at/record/5404","https://research-explorer.ista.ac.at/download/5404/5496"],"type":["info:eu-repo/semantics/other","doc-type:other","text","http://purl.org/coar/resource_type/c_1843"],"description":["We study finite-state two-player (zero-sum) concurrent mean-payoff games played on a graph. We focus on the important sub-class of ergodic games where all states are visited infinitely often with probability 1. The algorithmic study of ergodic games was initiated in a seminal work of Hoffman and Karp in 1966, but all basic complexity questions have remained unresolved. Our main results for ergodic games are as follows: We establish (1) an optimal exponential bound on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy); (2) the approximation problem lie in FNP; (3) the approximation problem is at least as hard as the decision problem for simple stochastic games (for which NP and coNP is the long-standing best known bound). We show that the exact value can be expressed in the existential theory of the reals, and also establish square-root sum hardness for a related class of games."],"date":["2013"],"language":["eng"],"source":["Chatterjee K, Ibsen-Jensen R. The Complexity of Ergodic Games. IST Austria; 2013. doi:10.15479/AT:IST-2013-127-v1-1"],"rights":["info:eu-repo/semantics/openAccess"],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.15479/AT:IST-2013-127-v1-1","info:eu-repo/semantics/altIdentifier/issn/2664-1690"],"subject":["ddc:000","ddc:005"],"publisher":["IST Austria"],"title":["The complexity of ergodic games","IST Austria Technical Report"]}}]