The Library
On Nash equilibria in stochastic games
Tools
UNSPECIFIED (2004) On Nash equilibria in stochastic games. In: 18th International Workshop on Computer Science Logic/13th Annual Conference of the EuropeanAssociationforComputerScienceLogic, Karpacz, POLAND, SEP 2024, 2004. Published in: COMPUTER SCIENCE LOGIC, PROCEEDINGS, 3210 pp. 2640. ISBN 3540230246. ISSN 03029743.
Full text not available from this repository, contact author.Abstract
We study infinite stochastic games played by nplayers 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 epsilonNash 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 epsilonNash equilibrium in memoryless strategies can be epsilonapproximated in NP.
We study the important subclass of nplayer turnbased probabilistic games, where at each state at most one player has a nontrivial choice of moves. For turnbased probabilistic games, we show the existence of epsilonNash equilibria in pure strategies for games where the objective of player i is a Borel set Bi of infinite traces. However, exact Nash equilibria may not exist. For the special case of omegaregular objectives, we show exact Nash equilibria exist, and can be computed in NP when the omegaregular objectives are expressed as parity objectives.
Item Type:  Conference Item (UNSPECIFIED)  

Subjects:  Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software  
Series Name:  LECTURE NOTES IN COMPUTER SCIENCE  
Journal or Publication Title:  COMPUTER SCIENCE LOGIC, PROCEEDINGS  
Publisher:  SPRINGERVERLAG BERLIN  
ISBN:  3540230246  
ISSN:  03029743  
Editor:  Marcinkowski, J and Tarlecki, A  
Official Date:  2004  
Dates: 


Volume:  3210  
Number of Pages:  15  
Page Range:  pp. 2640  
Publication Status:  Published  
Title of Event:  18th International Workshop on Computer Science Logic/13th Annual Conference of the EuropeanAssociationforComputerScienceLogic  
Location of Event:  Karpacz, POLAND  
Date(s) of Event:  SEP 2024, 2004 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 