Fetching the paper…
Reading the bibliography…
We study the complexity of computing stationary Nash equilibrium (NE) in n-player infinite-horizon general-sum stochastic games.
Non-cooperative games
John Nash · 1951
Earlier work this paper cites.
Stochastic games
Lloyd S Shapley · 1953
Earlier work this paper cites.
A note on two problems in connexion with graphs
Edsger W Dijkstra et al · 1959
Earlier work this paper cites.
Equilibrium in a stochastic n n -person game
Arlington M Fink · 1964
Earlier work this paper cites.
Equilibrium points of stochastic non-cooperative n n -person games
Masayuki Takahashi · 1964
Earlier work this paper cites.
Computers and intractability
Michael R Garey and David S Johnson · 1979
Earlier work this paper cites.
The great fish war: an example using a dynamic cournot-nash solution
David Levhari and Leonard J Mirman · 1980
Earlier work this paper cites.
The existence of equilibrium in discontinuous economic games, i: Theory
Partha Dasgupta and Eric Maskin · 1986
Earlier work this paper cites.
Cyclic games and an algorithm to find minimax cycle means in directed graphs
Vladimir A Gurvich, Alexander V Karzanov, and LG Khachivan · 1988
Earlier work this paper cites.
Tree automata, mu-calculus and determinacy
E Allen Emerson and Charanjit S Jutla · 1991
Earlier work this paper cites.
On total functions, existence theorems and computational complexity
Nimrod Megiddo and Christos H Papadimitriou · 1991
Earlier work this paper cites.
The complexity of stochastic games
Anne Condon · 1992
Earlier work this paper cites.
Flow control using the theory of zero sum markov games
Eitan Altman · 1994
Earlier work this paper cites.
On the complexity of the parity argument and other inefficient proofs of existence
Christos H Papadimitriou · 1994
Earlier work this paper cites.
Dynamic programming and optimal control
Dimitri P Bertsekas · 1995
Earlier work this paper cites.
Potential games
Dov Monderer and Lloyd S Shapley · 1996
Earlier work this paper cites.
The complexity of mean payoff games on graphs
Uri Zwick and Mike Paterson · 1996
Earlier work this paper cites.
A strategic market game with secured lending
Ioannis Karatzas, Martin Shubik, and William D Sudderth · 1997
Earlier work this paper cites.
Game theory: analysis of conflict
Roger B Myerson · 1997
Earlier work this paper cites.
Dynamic noncooperative game theory
Tamer Başar and Geert Jan Olsder · 1998
Earlier work this paper cites.
Actor-critic–type learning algorithms for markov decision processes
Vijaymohan R Konda and Vivek S Borkar · 1999
Earlier work this paper cites.
A discrete strategy improvement algorithm for solving parity games
Jens Vöge and Marcin Jurdziński · 2000
Earlier work this paper cites.
Friend-or-foe q-learning in general-sum games
Michael L Littman et al · 2001
Earlier work this paper cites.
Complexity results about nash equilibria
Vincent Conitzer and Tuomas Sandholm · 2002
Earlier work this paper cites.
Correlated q-learning
Amy Greenwald, Keith Hall, Roberto Serrano, et al · 2003
Earlier work this paper cites.
Nash q-learning for general-sum stochastic games
Junling Hu and Michael P Wellman · 2003
Earlier work this paper cites.
Stationary equilibria in stochastic games: structure, selection, and computation
P Jean-Jacques Herings and Ronald JAP Peeters · 2004
Cited alongside, same era.
Settling the complexity of two-player nash equilibrium
Xi Chen and Xiaotie Deng · 2006
Cited alongside, same era.
Cyclic equilibria in markov games
Martin Zinkevich, Amy Greenwald, and Michael Littman · 2006
Cited alongside, same era.
Graphical games
Michael Kearns · 2007
Cited alongside, same era.
A deterministic subexponential algorithm for solving parity games
Marcin Jurdziński, Mike Paterson, and Uri Zwick · 2008
Cited alongside, same era.
Computing correlated equilibria in multi-player games
Christos H Papadimitriou and Tim Roughgarden · 2008
Cited alongside, same era.
Mastering the game of go with deep neural networks and tree search
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al · 2016
Later among the works it cites.
The complexity of non-monotone markets
Xi Chen, Dimitris Paparas, and Mihalis Yannakakis · 2017
Later among the works it cites.
Settling the complexity of leontief and plc exchange markets under exact and approximate equilibria
Jugal Garg, Ruta Mehta, Vijay V Vazirani, and Sadra Yazdanbod · 2017
Later among the works it cites.
Learning nash equilibrium for general-sum markov games from batch data
Julien Pérolat, Florian Strub, Bilal Piot, and Olivier Pietquin · 2017
Later among the works it cites.
Mastering the game of go without human knowledge
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
The complexity of solving stochastic games on graphs
Daniel Andersson and Peter Bro Miltersen · 2009
Cited alongside, same era.
Settling the complexity of arrow-debreu equilibria in markets with additively separable utilities
Xi Chen, Decheng Dai, Ye Du, and Shang-Hua Teng · 2009
Cited alongside, same era.
The complexity of computing a nash equilibrium
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou · 2009
Cited alongside, same era.
Solving stochastic games
Liam Dermed and Charles Isbell · 2009
Cited alongside, same era.
A user’s guide to solving dynamic stochastic games using the homotopy method
Ron N Borkovsky, Ulrich Doraszelski, and Yaroslav Kryukov · 2010
Cited alongside, same era.
On the complexity of nash equilibria and other fixed points
Kousha Etessami and Mihalis Yannakakis · 2010
Cited alongside, same era.
Stationary nash equilibria for average stochastic positional games
Dmitrii Lozovanu · 2018
Later among the works it cites.
On the approximation of nash equilibria in sparse win-lose games
Zhengyang Liu and Ying Sheng · 2018
Later among the works it cites.
Inapproximability of nash equilibrium
Aviad Rubinstein · 2018
Later among the works it cites.
Reinforcement learning: An introduction
Richard S Sutton and Andrew G Barto · 2018
Later among the works it cites.
Smoothed complexity of 2-player nash equilibria
Shant Boodaghians, Joshua Brakensiek, Samuel B Hopkins, and Aviad Rubinstein · 2020
Later among the works it cites.
Near-optimal reinforcement learning with self-play
Yu Bai, Chi Jin, and Tiancheng Yu · 2020
Later among the works it cites.
Tree polymatrix games are ppad-hard
Argyrios Deligkas, John Fearnley, and Rahul Savani · 2020
Later among the works it cites.
Solving discounted stochastic two-player games with near-optimal time and sample complexity
Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye · 2020
Later among the works it cites.
On the complexity of computing markov perfect equilibrium in general-sum stochastic games
Xiaotie Deng, Yuhao Li, David Henry Mguni, Jun Wang, and Yaodong Yang · 2021
Later among the works it cites.
The complexity of constrained min-max optimization
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis · 2021
Later among the works it cites.
Independent natural policy gradient always converges in markov potential games
Roy Fox, Stephen McAleer, Will Overman, and Ioannis Panageas · 2021
Later among the works it cites.
On the complexity of equilibrium computation in first-price auctions
Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender, Philip Lazos, and Diogo Poças · 2021
Later among the works it cites.
V-learning–a simple, efficient, decentralized algorithm for multiagent rl
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu · 2021
Later among the works it cites.
Towards tight bounds on the sample complexity of average-reward mdps
Yujia Jin and Aaron Sidford · 2021
Later among the works it cites.
Public goods games in directed networks
Christos Papadimitriou and Binghui Peng · 2021
Later among the works it cites.
When can we learn general-sum markov games with a large number of players sample-efficiently?
Ziang Song, Song Mei, and Yu Bai · 2021
Later among the works it cites.
Multi-agent reinforcement learning: A selective overview of theories and algorithms
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar · 2021
Later among the works it cites.
The complexity of markov equilibrium in stochastic games
Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang · 2022
Closest in time.
Fixp-membership via convex optimization: Games, cakes, and markets
Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh, and Alexandros Hollender · 2022
Closest in time.
Provably efficient reinforcement learning in decentralized general-sum markov games
Weichao Mao and Tamer Başar · 2022
Closest in time.