A Compendium of PPAD-complete problems

(Under Constriction)

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)