Krishnendu Chatterjee

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-05-1407
August 2005

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/CSD-05-1407.pdf

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.

BibTeX citation:

@techreport{Chatterjee:CSD-05-1407,
    Author = {Chatterjee, Krishnendu},
    Title = {Nash Equilibrium for Upward-Closed Objectives},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2005},
    Month = {Aug},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5249.html},
    Number = {UCB/CSD-05-1407},
    Abstract = {We study infinite stochastic games played by <i>n</i>-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 <i>Z</i> of infinitely repeating states is winning, then all supersets of <i>Z</i> 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.}
}

EndNote citation:

%0 Report
%A Chatterjee, Krishnendu
%T Nash Equilibrium for Upward-Closed Objectives
%I EECS Department, University of California, Berkeley
%D 2005
%@ UCB/CSD-05-1407
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5249.html
%F Chatterjee:CSD-05-1407