*banner
 

Nash Equilibrium for Upward-Closed Objectives
Krishnendu Chatterjee

Citation
Krishnendu Chatterjee. "Nash Equilibrium for Upward-Closed Objectives". CSL 06, September, 2006.

Abstract
We study infinite stochastic games played by n-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 upward-closed objective, then there exists an epsilon-Nash equilibrium in memoryless strategies, for every epsilon>0; and exact Nash equilibria need not exist. Upward-closure of an objective means that if a set Z of infinitely repeating states is winning, then all supersets of Z of infinitely repeating states are also winning. Memoryless strategies are strategies that are independent of history of plays and depend only on the current state. We also 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 games with upward-closed objectives for all players can be computed by computing epsilon-Nash equilibrium values of nonzero-sum concurrent games with reachability objectives for all players and a polynomial procedure. 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

Citation formats  
  • HTML
    Krishnendu Chatterjee. <a
    href="http://chess.eecs.berkeley.edu/pubs/236.html"
    >Nash Equilibrium for Upward-Closed Objectives</a>,
    CSL 06, September, 2006.
  • Plain text
    Krishnendu Chatterjee. "Nash Equilibrium for
    Upward-Closed Objectives". CSL 06, September, 2006.
  • BibTeX
    @inproceedings{Chatterjee06_NashEquilibriumForUpwardClosedObjectives,
        author = {Krishnendu Chatterjee},
        title = {Nash Equilibrium for Upward-Closed Objectives},
        booktitle = {CSL 06},
        month = {September},
        year = {2006},
        abstract = {We study infinite stochastic games played by
                  n-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 upward-closed
                  objective, then there exists an epsilon-Nash
                  equilibrium in memoryless strategies, for every
                  epsilon>0; and exact Nash equilibria need not
                  exist. Upward-closure of an objective means that
                  if a set Z of infinitely repeating states is
                  winning, then all supersets of Z of infinitely
                  repeating states are also winning. Memoryless
                  strategies are strategies that are independent of
                  history of plays and depend only on the current
                  state. We also 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
                  games with upward-closed objectives for all
                  players can be computed by computing epsilon-Nash
                  equilibrium values of nonzero-sum concurrent games
                  with reachability objectives for all players and a
                  polynomial procedure. 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/236.html}
    }
    

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

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess