Concepedia

3 { Nash is PPAD { Complete

Xi Chen, Xiaotie Deng

2005 · 102 citations · 9 references

Abstract

In this paper, we improve a recent result of Daskalakis, Goldberg and Papadimitriou on PPAD-completeness of 4-Nash, showing that 3-Nash is PPAD-complete. 1

References

9

On the complexity of the parity argument and other inefficient proofs of existence

Christos H. Papadimitriou · Journal of Computer and System Sciences · 1994 · 791 citations

Engineering, Automated Reasoning, Parity Argument +9

Graphical Models for Game Theory

Michael Kearns, Michael L. Littman, Satinder Singh · arXiv (Cornell University) · 2013 · 563 citations · Full text

Mathematical Programming, Engineering, Combinatorial Game +18

Nash and correlated equilibria: Some complexity considerations

Itzhak Gilboa, Eitan Zemel · Games and Economic Behavior · 1989 · 409 citations

Non-cooperative Game Theory, Equilibrium Problem, Game Theory +4

On total functions, existence theorems and computational complexity

Nimrod Megiddo, Christos H. Papadimitriou · Theoretical Computer Science · 1991 · 300 citations

Computational Complexity Theory, Computational Complexity, Time Complexity +2

Complexity Results about Nash Equilibria

Vincent Conitzer, Tüomas Sandholm · ArXiv.org · 2002 · 217 citations · Full text

Mathematical Programming, Engineering, Game Theory +16