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

Yakov Babichenko, Christos Papadimitriou, Aviad Rubinstein

TL;DR

This paper proposes a bold new conjecture: that the complexity class PPAD (which contains problems like finding Nash equilibria) has its own version of the PCP Theorem. If true, this "PCP for PPAD" implies that the well-known quasipolynomial-time algorithm for finding approximate Nash equilibria is essentially the best we can do, settling a decade-old mystery in algorithmic game theory.

What Problem Does This Paper Address?

In the world of computational complexity, finding a Nash equilibrium—a state where no player has an incentive to change their strategy—is a landmark problem. We know it belongs to a class called PPAD, and while finding an exact equilibrium is likely hard, finding an approximate one ($\epsilon$-Nash) has occupied researchers for years.

There is a strange gap in our understanding:

  1. Finding an $\epsilon$-Nash equilibrium is PPAD-complete if the error $\epsilon$ is very small (inversely polynomial).
  2. However, for any fixed constant $\epsilon > 0$, there exists a quasipolynomial-time algorithm ($n^{O(\log n)}$) developed by Lipton, Markakis, and Mehta (LMM03).

The big question is: Can we do better? Is there a polynomial-time algorithm for constant $\epsilon$, or is the $n^{O(\log n)}$ bound fundamental? This paper argues for the latter by connecting the problem to the theory of Probabilistically Checkable Proofs (PCPs).

Methods

The authors bridge this gap by introducing Conjecture 2, which posits that a specific problem called $(\epsilon, \delta)$-GCIRCUIT is hard.

The $(\epsilon, \delta)$-GCIRCUIT Problem

A "Generalized Circuit" (GCIRCUIT) is a graph of arithmetic gates that can contain cycles, representing a system of constraints. The authors define a relaxed version where:

  • $\epsilon$ (Precision): Most gates only need to be satisfied approximately.
  • $\delta$ (Fraction): A small fraction of the gates can be completely violated.

This is the "almost everybody is almost happy" condition. The authors provide a detailed list of these gate constraints in the paper:

Table of gate types and their corresponding mathematical constraints for the $(\epsilon, \delta)$-GCIRCUIT problem.

Birthday Repetition

To prove their main result (Theorem 1), the authors use a technique called "birthday repetition." They start with a complex game involving many players and reduce it to a two-player game. They do this by partitioning the many players into blocks. The two players in the new game each "control" a side of a bipartite graph and choose strategies for an entire block of original players. This reduction is what leads to the $n^{\Omega(\log n)}$ lower bound, matching the LMM03 algorithm's performance.

Datasets

As a theoretical work in computational complexity, this paper does not use empirical datasets. It relies on mathematical proofs and reductions between abstract complexity problems like End of the Line, GCIRCUIT, and Nash Equilibrium.

Key Insights and Ideas

  • The PCP Analogy: In the class NP, the PCP Theorem shows that it's hard to even approximately satisfy constraint satisfaction problems. The authors conjecture that a similar phenomenon exists for PPAD. If you can't satisfy almost all constraints in a circuit, you can't find an equilibrium.
  • Settling the LMM03 Optimality: For years, researchers wondered if the $n^{O(\log n)}$ algorithm was just a stepping stone to a polynomial-time one. This paper provides a strong theoretical reason to believe that $n^{O(\log n)}$ is the actual speed limit.
  • Gadget-Based Reductions: The paper uses clever "game gadgets" to translate circuit gates into player payoffs. For example, they describe a gadget for multiplication gates ($G_{\times\zeta}$) that forces a player's strategy to reflect a specific mathematical relationship:
Payoff tables for a game gadget simulating a multiplication gate, showing how player $w$ acts as a verifier for players $v_1$ and $v_2$.

Key Results

  • Theorem 1: Assuming their PCP-like conjecture, finding an $\epsilon$-Nash equilibrium in a two-player game with $n$ strategies requires $n^{\Omega(\log n)}$ time. This effectively proves the LMM03 algorithm is optimal.
  • Relative Approximation: They show that finding a relative (multiplicative) $\epsilon$-approximate Nash equilibrium is PPAD-complete, even when payoffs are strictly positive or negative, resolving an open question from Daskalakis (2013).
  • Fairness Mechanisms: They apply their conjecture to the "Competitive Equilibrium from Equal Incomes" (CEEI) problem, showing that finding an allocation with low clearing error and a near-optimal Gini coefficient (a measure of inequality) is also PPAD-complete.

Limitations and Future Work

The primary limitation is that the results are conditional. They depend entirely on the validity of Conjecture 2 (the "PCP for PPAD" conjecture). While the authors provide compelling arguments for why this conjecture is plausible—drawing parallels to the established PCP Theorem for NP—it remains unproven.

The most significant direction for future work is, of course, proving this conjecture by showing a reduction from the iconic End of the Line problem to the $(\epsilon, \delta)$-GCIRCUIT problem. The authors suggest that while current PCP techniques for NP are discrete, PPAD's continuous nature might require new, combinatorial approaches to proof verification.

Summary updated

Abstract

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.
BibTeX
@inproceedings{babichenko2016can,
  author = {Yakov Babichenko and Christos Papadimitriou and Aviad Rubinstein},
  title = {{Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash}},
  booktitle = {ITCS},
  year = {2016},
  doi = {10.1145/2840728.2840731},
}
Figure