Fetching the paper…
Reading the bibliography…
PPAD refers to a class of computational problems for which solutions are guaranteed to exist due to a specific combinatorial principle.
E. Sperner, Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes, Abhandlungen aus dem Mathematischen Seminar Universität Hamburg
1928
Earlier work this paper cites.
J. von Neumann and O. Morgenstern, The Theory of Games and Economic Behavior, second ed
1947
Earlier work this paper cites.
J. Nash, Noncooperative Games, Annals of Mathematics
1951
Earlier work this paper cites.
K.J. Arrow and G. Debreu, Existence of an Equilibrium for a Competitive Economy, Econometrica
1954
Earlier work this paper cites.
F.E. Browder, On continuity of fixed points under deformations of continuous mappings, Summa Brasiliensis Math
1960
Earlier work this paper cites.
D. Gale, Theory of Linear Economic Models
1960
Earlier work this paper cites.
C.E. Lemke and J.T. Howson, Jr., Equilibrium points of bimatrix games, SIAM J. Appl. Math
1964
Earlier work this paper cites.
H. Scarf, The approximation of fixed points of a continuous mapping, SIAM J. Appl. Math
1967
Earlier work this paper cites.
R.W. Rosenthal, A Class of Games Possessing Pure-Strategy Nash Equilibria, International Journal of Game Theory
1973
Earlier work this paper cites.
J.C. Harsanyi, The tracing procedure: a Bayesian approach to deÞning a solution for n-person noncooperative games, International Journal of Game Theory
1975
Earlier work this paper cites.
V. Bubelis, On equilibria in finite games, International Journal of Game Theory
1979
Earlier work this paper cites.
N. Megiddo, A note on the complexity of P P -matrix LCP and computing an equilibrium, Res. Rep. RJ6439, IBM Almaden Research Center, San Jose
1988
Earlier work this paper cites.
J. Renegar, A faster PSPACE algorithm for deciding the existential theory of the reals, in 29th Symposium on Foundations of Computer Science
1988
Earlier work this paper cites.
I. Gilboa and E. Zemel, Nash and correlated equilibria: Some complexity considerations, Games and Economic Behavior
1989
Earlier work this paper cites.
M.D. Hirsch, C.H. Papadimitriou and S. Vavasis, Exponential Lower Bounds for Finding Brouwer Fixed Points, Journal of Complexity
1989
Earlier work this paper cites.
M.J. Osborne and A. Rubinstein, A Course in Game Theory
1994
Earlier work this paper cites.
C.H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, J. Comput. System Sci
1994
Earlier work this paper cites.
P. Beame, S. Cook, J. Edmonds, R. Impagliazzo and T. Pitassi, The relative complexity of NP search problems, in 27th ACM Symposium on Theory of Computing
1995
Earlier work this paper cites.
P. Crescenzi and C.H. Papadimitriou, Reversible Simulation of Space-Bounded Computations, Theoretical Computer Science
1995
Earlier work this paper cites.
D. Monderer and L. Shapley, Potential Games, Games and Economic Behavior
1996
Earlier work this paper cites.
P.J-J. Herings, Two simple proofs of the feasibility of the linear tracing procedure, Economic Theory
2000
Earlier work this paper cites.
P.J-J Herings and R.J.A.P. Peeters, A differentiable homotopy to compute Nash equilibria of n-person games, Economic Theory
2001
Earlier work this paper cites.
M. Kearns, M.L. Littman and S. Singh, Graphical models for game theory, in 17th Conference on Uncertainty in Artificial Intelligence
2001
Cited alongside, same era.
M. Littman, M. Kearns and S. Singh, An efficient, exact algorithm for single connected graphical games, in 15th Annual Conference on Neural Information Processing Systems
2001
Cited alongside, same era.
P.J-J. Herings and A. van den Elzen, Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games, Games and Economic Behavior
2002
Cited alongside, same era.
B. von Stengel, Computing equilibria for two-person games. Chapter 45, Handbook of Game Theory, Vol 3
2002
Cited alongside, same era.
V. Conitzer and T. Sandholm, Complexity results about Nash equilibria, in 18th International Joint Conference on ArtiÞcial Intelligence
2003
Cited alongside, same era.
G. Schoenebeck and S. Vadhan, The Computational Complexity of Nash Equilibria in Concisely Represented Games, in 7th ACM Conference on Electronic Commerce
2006
Later among the works it cites.
L. Addario-Berry, N. Olver and A. Vetta, A polynomial time algorithm for finding Nash equilibria in planar win-lose games, J. Graph Algorithms Appl
2007
Later among the works it cites.
N. Nisan, T. Roughgarden, E. Tardos and V.V. Vazirani, Algorithmic Game Theory
2007
Later among the works it cites.
2008
Later among the works it cites.
C. Daskalakis and C.H. Papadimitriou, Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games, in 49th Symposium on Foundations of Computer Science
2008
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
N.R. Devanur and V.V. Vazirani, An improved approximation scheme for computing Arrow-Debreu prices for the linear case, in 23rd Conference, Foundations of Software Technology and Theoretical Computer Science
2003
Cited alongside, same era.
R. Lipton, V. Markakis and A. Mehta, Playing Large Games using Simple Strategies, in 4th ACM Conference on Electronic Commerce
2003
Cited alongside, same era.
K. Jain, A polynomial-time algorithm for computing the Arrow-Debreu market equilibrium for linear utilities, in 45th Symposium on Foundations of Computer Science
2004
Cited alongside, same era.
T.G. Abbott, D.M. Kane and P. Valiant, On the complexity of two-player win-lose games, in 46th Symposium on Foundations of Computer Science
2005
Cited alongside, same era.
X. Chen and X. Deng, 3-NASH is PPAD-Complete, Technical report TR05-134, Electronic Colloquium on Computational Complexity
2005
Cited alongside, same era.
C. Daskalakis and C.H. Papadimitriou, Three-player games are hard, Technical Report TR05-139, Electronic Colloquium on Computational Complexity
2005
Cited alongside, same era.
L. Fortnow, R, Impagliazzo, V. Kabinets and C. Umans, On the Complexity of Succinct Zero-Sum Games, in 20th IEEE Conference on Computational Complexity
2005
Cited alongside, same era.
Later among the works it cites.
N. Devanur, C.H. Papadimitriou, A. Saberi and V.V. Vazirani, Market Equilibrium via a Primal-Dual-Type Algorithm for a Convex Program, Journal of the ACM
2008
Later among the works it cites.
S. Hémon, M. de Rougemont and M. Santha, Approximate Nash Equilibria for Multi-player Games, in 1st Symposium on Algorithmic Game Theory
2008
Later among the works it cites.
F. Brandt, F. Fischer, P. Harrenstein and Y. Shoham, Ranking Games, Artificial Intelligence
2009
Later among the works it cites.
X. Chen, D. Dai, Y. Du and S.-H. Teng, Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities, in 50th Symposium on Foundations of Computer Science
2009
Later among the works it cites.
X. Chen, X. Deng and S.-H. Teng, Settling the complexity of computing two-player Nash equilibria, Journal of the ACM
2009
Later among the works it cites.
X. Chen and S.-H. Teng, Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria, in 20th International Symposium on Algorithms and Computation
2009
Later among the works it cites.
C. Daskalakis, P.W. Goldberg and C.H. Papadimitriou, The Complexity of Computing a Nash Equilibrium, SIAM Journal on Computing
2009
Later among the works it cites.
C. Daskalakis, P.W. Goldberg and C.H. Papadimitriou, The Complexity of Computing a Nash Equilibrium, Communications of the ACM
2009
Later among the works it cites.
C. Daskalakis, A. Mehta and C.H. Papadimitriou, A Note on Approximate Nash Equilibria, Theoretical Computer Science
2009
Later among the works it cites.
C. Daskalakis and C.H. Papadimitriou, On a Network Generalization of the Minmax Theorem, in 36th International Colloquium on Automata, Languages and Programming
2009
Later among the works it cites.
K. Etessami and M. Yannakakis, On the Complexity of Nash Equilibria and Other Fixed Points, SIAM Journal on Computing
2010
Later among the works it cites.
U. Feige and I. Talgam-Cohen, A Direct Reduction from k k -Player to 2-Player Approximate Nash, in 3rd Symposium on Algorithmic Game Theory
2010
Later among the works it cites.
L.A. Goldberg, P.W. Goldberg, P. Krysta and C. Ventre, Ranking Games that have Competitiveness-based Strategies, in 11th ACM Conference on Electronic Commerce
2010
Later among the works it cites.
P.W. Goldberg, C.H. Papadimitriou and R. Savani, The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions, Arxiv technical report 1006.5352
2010
Later among the works it cites.
P.J-J. Herings and R. Peeters, Homotopy methods to compute equilibria in game theory, Economic Theory
2010
Later among the works it cites.
V.V. Vazirani and M. Yannakakis, Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities, in 1st Symposium on Innovations in Computer Science
2010
Later among the works it cites.