A Compendium of PPAD-complete problems

(Under Construction)

For additions/corrections, please send me an email.

Please edit the Wikipedia entry.




Problem

Category
Reference
End Of The Line
Standard PPAD-complete problem Papadimitriou'94
3D Sperner
Fixed Point Theorems Papadimitriou'94
2D Sperner
Fixed Point Theorems Chen,Deng'06-sperner
Brouwer, Kakutani
Fixed Point Theorems Papadimitriou'94
Tucker, Borsuk-Ulam
Topology Papadimitriou'94
Exchange Economy
Economics Papadimitriou'94
Stylized 3Dimensional Brouwer
Fixed Point Theorems DGP'05
4-Nash
(r-Nash for r>=4)

Nash DGP'05
3-Graphical Nash
(d-Graphical Nash for d>=3)

Graphical Nash DGP'05
3-Nash
Nash [Daskalakis,Papadimitriou'05], [Chen,Deng'05]
2-Nash
Nash [Chen,Deng'06-2nash]
approximate-Nash
Nash [CDT'06]
2-Player win-lose games
Nash [AKV'05]
Leontief exchange economy
Market Equilibria [CSVY'05]
Arrow-Debreu Equilibria
Market Equilibria [CDDT'09]
Fractional Stable Paths Problem
Internet Routing [KPRST'09]
Core of Balanced Games
Cooperative Game Theory [KPRST'09]
Scarf's Lemma
Combinatorics [KPRST'09]
Hypergraph Matching
Social Choice [KPRST'09]
Fractional Bounded Budget Connection Games
Social Networks [KPRST'09]
Strong Fractional Kernel
Graph Theory [KPRST'09]
Preference Games
Social Choice [KPRST'09]
Personalized Equilibria
Game Theory [KPRST'09]
2D-Tucker
Topology Palvolgyi'09
Fisher's Equilibria
Market Equilibria Chen,Teng'09




References

  • [Daskalakis,Papadimitriou'05]
    Constantinos Daskalakis, Christos H. Papadimitriou
    Three-Player Games Are Hard
    Electronic Colloquium on Computational Complexity (ECCC)(139): (2005)
  • [Chen,Deng'05]
    Xi Chen, Xiaotie Deng
    3-NASH is PPAD-Complete
    Electronic Colloquium on Computational Complexity (ECCC)(134): (2005)