  We conjecture that PPAD has a PCP-like complete problem, seeking a near
equilibrium in which all but very few players have very little incentive to
deviate. We show that, if one assumes that this problem requires exponential
time, several open problems in this area are settled. The most important
implication, proved via a "birthday repetition" reduction, is that the n^O(log
n) approximation scheme of [LMM03] for the Nash equilibrium of two-player games
is essentially optimum. Two other open problems in the area are resolved once
one assumes this conjecture, establishing that certain approximate equilibria
are PPAD-complete: Finding a relative approximation of two-player Nash
equilibria (without the well-supported restriction of [Das13]), and an
approximate competitive equilibrium with equal incomes [Bud11] with small
clearing error and near-optimal Gini coefficient.

Computational Complexity;Computer Science and Game Theory