---
OA_type: closed access
_id: '3894'
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
    > 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.
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
alternative_title:
- 'LNCS '
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Ritankar
  full_name: Majumdar, Ritankar
  last_name: Majumdar
- first_name: Marcin
  full_name: Jurdziński, Marcin
  last_name: Jurdziński
citation:
  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>'
  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>'
  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>.
  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.
  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.'
  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>.
  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.
conference:
  end_date: 2004-09-24
  location: Karpacz, Poland
  name: 'CSL: Computer Science Logic'
  start_date: 2004-09-20
corr_author: '1'
date_created: 2018-12-11T12:05:45Z
date_published: 2004-09-09T00:00:00Z
date_updated: 2026-09-11T09:11:09Z
day: '09'
doi: 10.1007/978-3-540-30124-0_6
extern: '1'
fulldoi: https://doi.org/10.1007/978-3-540-30124-0_6
intvolume: '      3210'
language:
- iso: eng
month: '09'
oa_version: None
page: 26 - 40
publication: 18th International Workshop, Computer Science Logic 2004, 13th Annual
  Conference of the EACSL
publication_identifier:
  eisbn:
  - '9783540301240'
  eissn:
  - 1611-3349
  isbn:
  - '9783540230243'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '2264'
status: public
title: On Nash equilibria in stochastic games
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 3210
year: '2004'
...