Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash

Yakov Babichenko, Christos Papadimitriou, Aviad Rubinstein

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