---
res:
bibo_abstract:
- 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Krishnendu Chatterjee
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Ritankar
foaf_name: Majumdar, Ritankar S
foaf_surname: Majumdar
- foaf_Person:
foaf_givenName: Marcin
foaf_name: Jurdziński, Marcin
foaf_surname: Jurdziński
bibo_doi: 10.1007/978-3-540-30124-0_6
bibo_volume: 3210
dct_date: 2004^xs_gYear
dct_publisher: Springer@
dct_title: On Nash equilibria in stochastic games@
...