All reports by Author Christos H. Papadimitriou:

__
TR07-082
| 27th July 2007
__

Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Kalai, Vahab Mirrokni, Christos H. Papadimitriou#### The Myth of the Folk Theorem

__
TR06-094
| 29th July 2006
__

Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, Christos H. Papadimitriou#### The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Revisions: 1

__
TR05-139
| 21st November 2005
__

Constantinos Daskalakis, Christos H. Papadimitriou#### Three-Player Games Are Hard

__
TR05-115
| 27th September 2005
__

Constantinos Daskalakis, Paul Goldberg, Christos H. Papadimitriou#### The complexity of computing a Nash equilibrium

__
TR05-090
| 17th August 2005
__

Paul Goldberg, Christos H. Papadimitriou#### Reducibility Among Equilibrium Problems

Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Kalai, Vahab Mirrokni, Christos H. Papadimitriou

The folk theorem suggests that finding Nash Equilibria

in repeated games should be easier than in one-shot games. In

contrast, we show that the problem of finding any (epsilon) Nash

equilibrium for a three-player infinitely-repeated game is

computationally intractable (even when all payoffs are in

{-1,0,-1}), unless all of PPAD ...
more >>>

Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, Christos H. Papadimitriou

Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions ... more >>>

Constantinos Daskalakis, Christos H. Papadimitriou

We prove that computing a Nash equilibrium in a 3-player

game is PPAD-complete, solving a problem left open in our recent result on the complexity of Nash equilibria.

Constantinos Daskalakis, Paul Goldberg, Christos H. Papadimitriou

We resolve the question of the complexity of Nash equilibrium by

showing that the problem of computing a Nash equilibrium in a game

with 4 or more players is complete for the complexity class PPAD.

Our proof uses ideas from the recently-established equivalence

between polynomial-time solvability of normal-form games and

more >>>

Paul Goldberg, Christos H. Papadimitriou

We address the fundamental question of whether the Nash equilibria of

a game can be computed in polynomial time. We describe certain

efficient reductions between this problem for

normal form games with a fixed number of players

and graphical games with fixed degree. Our main result is that ...
more >>>