[{"date_published":"2004-09-09T00:00:00Z","fulldoi":"https://doi.org/10.1007/978-3-540-30124-0_6","publication_identifier":{"isbn":["9783540230243"],"eissn":["1611-3349"],"issn":["0302-9743"],"eisbn":["9783540301240"]},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","page":"26 - 40","corr_author":"1","publication":"18th International Workshop, Computer Science Logic 2004, 13th Annual Conference of the EACSL","title":"On Nash equilibria in stochastic games","alternative_title":["LNCS "],"day":"09","publist_id":"2264","language":[{"iso":"eng"}],"acknowledgement":"This research was supported in part by the AFOSR MURI grant F49620-00-1-0327, ONR grant N00014-02-1-0671, NSF grants CCR-9988172 and CCR-0225610","volume":3210,"type":"conference","year":"2004","oa_version":"None","_id":"3894","date_updated":"2026-09-11T09:11:09Z","publication_status":"published","month":"09","conference":{"location":"Karpacz, Poland","start_date":"2004-09-20","name":"CSL: Computer Science Logic","end_date":"2004-09-24"},"status":"public","OA_type":"closed access","date_created":"2018-12-11T12:05:45Z","citation":{"ieee":"K. Chatterjee, R. Majumdar, and M. Jurdziński, “On Nash equilibria in stochastic games,” in <i>18th International Workshop, Computer Science Logic 2004, 13th Annual Conference of the EACSL</i>, Karpacz, Poland, 2004, vol. 3210, pp. 26–40.","apa":"Chatterjee, K., Majumdar, R., &#38; Jurdziński, M. (2004). On Nash equilibria in stochastic games. In <i>18th International Workshop, Computer Science Logic 2004, 13th Annual Conference of the EACSL</i> (Vol. 3210, pp. 26–40). Karpacz, Poland: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-540-30124-0_6\">https://doi.org/10.1007/978-3-540-30124-0_6</a>","ama":"Chatterjee K, Majumdar R, Jurdziński M. On Nash equilibria in stochastic games. In: <i>18th International Workshop, Computer Science Logic 2004, 13th Annual Conference of the EACSL</i>. Vol 3210. Springer Nature; 2004:26-40. doi:<a href=\"https://doi.org/10.1007/978-3-540-30124-0_6\">10.1007/978-3-540-30124-0_6</a>","chicago":"Chatterjee, Krishnendu, Ritankar Majumdar, and Marcin Jurdziński. “On Nash Equilibria in Stochastic Games.” In <i>18th International Workshop, Computer Science Logic 2004, 13th Annual Conference of the EACSL</i>, 3210:26–40. Springer Nature, 2004. <a href=\"https://doi.org/10.1007/978-3-540-30124-0_6\">https://doi.org/10.1007/978-3-540-30124-0_6</a>.","mla":"Chatterjee, Krishnendu, et al. “On Nash Equilibria in Stochastic Games.” <i>18th International Workshop, Computer Science Logic 2004, 13th Annual Conference of the EACSL</i>, vol. 3210, Springer Nature, 2004, pp. 26–40, doi:<a href=\"https://doi.org/10.1007/978-3-540-30124-0_6\">10.1007/978-3-540-30124-0_6</a>.","ista":"Chatterjee K, Majumdar R, Jurdziński M. 2004. On Nash equilibria in stochastic games. 18th International Workshop, Computer Science Logic 2004, 13th Annual Conference of the EACSL. CSL: Computer Science Logic, LNCS , vol. 3210, 26–40.","short":"K. Chatterjee, R. Majumdar, M. Jurdziński, in:, 18th International Workshop, Computer Science Logic 2004, 13th Annual Conference of the EACSL, Springer Nature, 2004, pp. 26–40."},"doi":"10.1007/978-3-540-30124-0_6","intvolume":"      3210","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"last_name":"Majumdar","first_name":"Ritankar","full_name":"Majumdar, Ritankar"},{"last_name":"Jurdziński","first_name":"Marcin","full_name":"Jurdziński, Marcin"}],"publisher":"Springer Nature","extern":"1","article_processing_charge":"No","abstract":[{"lang":"eng","text":"We study infinite stochastic games played by n-players on a finite graph with goals given by sets of infinite traces. The games are stochastic (each player simultaneously and independently chooses an action at each round, and the next state is determined by a probability distribution depending on the current state and the chosen actions), infinite (the game continues for an infinite number of rounds), nonzero sum (the players' goals are not necessarily conflicting), and undiscounted. We show that if each player has a reachability objective, that is, if the goal for each player i is to visit some subset R-i of the states, then there exists an epsilon-Nash equilibrium in memoryless strategies, for every epsilon &gt; 0. However, exact Nash equilibria need not exist. We study the complexity of finding such Nash equilibria, and show that the payoff of some epsilon-Nash equilibrium in memoryless strategies can be epsilon-approximated in NP. We study the important subclass of n-player turn-based probabilistic games, where at each state at most one player has a nontrivial choice of moves. For turn-based probabilistic games, we show the existence of epsilon-Nash equilibria in pure strategies for games where the objective of player i is a Borel set B-i of infinite traces. However, exact Nash equilibria may not exist. For the special case of omega-regular objectives, we show exact Nash equilibria exist, and can be computed in NP when the omega-regular objectives are expressed as parity objectives."}]}]