Krishnendu Chatterjee, Marcin Jurdzinski and Rupak Majumdar

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-03-1281
October 2003

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1281.pdf

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 Ri of the states, then there exists an epsilon-Nash equilibrium in memoryless strategies. We study the complexity of finding such Nash equilibria. Given an n-player reachability game, and a vector of values ( v1 ... vn), we show it is NP-hard to determine if there exists a memoryless epsilon-Nash equilibrium where each player gets payoff at least vi. On the other hand, for every fixed epsilon, the value can be epsilon-approximated in FNP.

We study two important special cases of the general problem. First, we study n-player turn-based probabilistic games, where at each state atmost 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 all games where the goal of each player is a Borel set of infinite traces. We also derive the existence of pure exact Nash equilibria for n-player turn-based games where each player has an omega-regular objective.

Then we study the two player case and show that already for two-player games exact Nash equilibria may not exist. Our techniques for the general case also yield NP coNP epsilon-approximation algorithms for zero-sum reachability games, improving the previously known EXPTIME bound.

BibTeX citation:

@techreport{Chatterjee:CSD-03-1281,
    Author = {Chatterjee, Krishnendu and Jurdzinski, Marcin and Majumdar, Rupak},
    Title = {On Nash Equilibria in Stochastic Games},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2003},
    Month = {Oct},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5773.html},
    Number = {UCB/CSD-03-1281},
    Abstract = {We study infinite stochastic games played by <i>n</i>-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>i</i> is to visit some subset <i>Ri</i> of the states, then there exists an epsilon-Nash equilibrium in memoryless strategies. We study the complexity of finding such Nash equilibria. Given an <i>n</i>-player reachability game, and a vector of values (<i>v1</i> ... <i>vn</i>), we show it is NP-hard to determine if there exists a memoryless epsilon-Nash equilibrium where each player gets payoff at least <i>vi</i>. On the other hand, for every fixed epsilon, the value can be epsilon-approximated in FNP. <p>We study two important special cases of the general problem. First, we study <i>n</i>-player turn-based probabilistic games, where at each state atmost 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 all games where the goal of each player is a Borel set of infinite traces. We also derive the existence of pure exact Nash equilibria for <i>n</i>-player turn-based games where each player has an omega-regular objective. <p>Then we study the two player case and show that already for two-player games exact Nash equilibria may not exist. Our techniques for the general case also yield NP coNP epsilon-approximation algorithms for zero-sum reachability games, improving the previously known EXPTIME bound.}
}

EndNote citation:

%0 Report
%A Chatterjee, Krishnendu
%A Jurdzinski, Marcin
%A Majumdar, Rupak
%T On Nash Equilibria in Stochastic Games
%I EECS Department, University of California, Berkeley
%D 2003
%@ UCB/CSD-03-1281
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5773.html
%F Chatterjee:CSD-03-1281