The complexity of computing a Nash equilibrium

How long does it take until economic agents converge to an equilibrium? By studying the complexity of the problem of computing a mixed Nash equilibrium in a game, we provide evidence that there are games in which convergence to such an equilibrium takes prohibitively long. Traditionally, computational problems fall into two classes: those that have a polynomial-time algorithm and those that are nP-hard. However, the concept of NP-hardness cannot be applied to the rare problems where “every instance has a solution”—for example, in the case of games Nash’s theorem asserts that every game has a mixed equilibrium (now known as the Nash equilibrium, in honor of that result). We show that finding a Nash equilibrium is com-plete for a class of problems called PPaD, containing several other known hard problems; all problems in PPaD share the same style of proof that every instance has a solution