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 >>>

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 >>>

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.

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 >>>

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 >>>