Citation
Krishnendu Chatterjee. "Two-player Nonzero-sum \omega-Regular Games". CONCUR, August, 2005.

Abstract
We study infinite stochastic games played by two-players on a finite graph with goals specified by sets of infinite traces. The games are concurrent (each player simultaneously and independently chooses an action at each round), stochastic (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 an \omega-regular objective expressed as a parity objective, then there exists an \epsilon-Nash equilibrium, for every \epsilon>0. However, exact Nash equilibria need not exist. We study the complexity of finding values (payoff profile) of an \epsilon-Nash equilibrium. We show that the values of an \epsilon-Nash equilibrium in nonzero-sum concurrent parity games can be computed by solving the following two simpler problems: computing the values of zero-sum (the goals of the players are strictly conflicting) concurrent parity games and computing \epsilon-Nash equilibrium values of nonzero-sum concurrent games with reachability objectives. As a consequence we establish that values of an \epsilon-Nash equilibrium can be computed in TFNP (total functional NP), and hence in EXPTIME.

Electronic downloads

• concur05.ps · application/postscript · 390 kbytes

• HTML

  Krishnendu Chatterjee. <a
  href="http://chess.eecs.berkeley.edu/pubs/76.html"
  >Two-player Nonzero-sum \omega-Regular Games</a>,
  CONCUR, August, 2005.

• Plain text

  Krishnendu Chatterjee. "Two-player Nonzero-sum
  \omega-Regular Games". CONCUR, August, 2005.

• BibTeX

  @inproceedings{Chatterjee05_TwoplayerNonzerosumomegaRegularGames,
      author = {Krishnendu Chatterjee},
      title = {Two-player Nonzero-sum \omega-Regular Games},
      booktitle = {CONCUR},
      month = {August},
      year = {2005},
      abstract = {We study infinite stochastic games played by
                two-players on a finite graph with goals specified
                by sets of infinite traces. The games are
                concurrent (each player simultaneously and
                independently chooses an action at each round),
                stochastic (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 an \omega-regular
                objective expressed as a parity objective, then
                there exists an \epsilon-Nash equilibrium, for
                every \epsilon>0. However, exact Nash equilibria
                need not exist. We study the complexity of finding
                values (payoff profile) of an \epsilon-Nash
                equilibrium. We show that the values of an
                \epsilon-Nash equilibrium in nonzero-sum
                concurrent parity games can be computed by solving
                the following two simpler problems: computing the
                values of zero-sum (the goals of the players are
                strictly conflicting) concurrent parity games and
                computing \epsilon-Nash equilibrium values of
                nonzero-sum concurrent games with reachability
                objectives. As a consequence we establish that
                values of an \epsilon-Nash equilibrium can be
                computed in TFNP (total functional NP), and hence
                in EXPTIME.},
      URL = {http://chess.eecs.berkeley.edu/pubs/76.html}
  }
  

Posted by Krishnendu Chatterjee, PhD on 9 May 2006.
Groups: chess
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.