Lecture 18

Total search and TFNP

Corollary L1.10 guarantees a Nash equilibrium, but its existence proof does not give a polynomial-time algorithm. We have already met a similar distinction in Sperner’s lemma (Theorem L2.1): a fully labeled simplex exists, yet the path certifying existence can be exponentially long. Today we formalize search problems whose solutions are guaranteed to exist, and isolate the directed parity argument underlying PPAD [Pap94[Pap94] Papadimitriou, C. H. (1994). On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. Journal of Computer and System Sciences, 48(3), 498–532. link].

L18.1 From decision to search

A decision problem asks for a yes/no answer. A search problem asks for a witness. For example, satisfiability asks whether a Boolean formula has a satisfying assignment; the corresponding search problem asks us to produce one when it exists.

The length bound is part of the definition: efficient verification alone would not ensure that a solution can even be written in polynomial time. Instances and witnesses here are finite binary strings. When a mathematical solution is a real vector, its required finite representation must be specified.

An existence theorem supplies the last condition. Polynomial balance and verification must still be established separately. Ill-formed encodings can be handled by a designated, efficiently recognizable witness; they should not silently become exceptions to totality.

For a rational finite game and rational \(\epsilon >0\), an \(\epsilon\)-Nash equilibrium can be represented by a rational profile of polynomial encoding length in the game description and \(\operatorname{log}(\frac{1}{\epsilon})\). To see the length bound, round an exact equilibrium to a sufficiently fine rational grid: multilinearity and bounded payoffs control the resulting change in every deviation gain. Payoffs and deviations can then be evaluated in polynomial time for an explicitly represented game.

L18.2 Reductions between search problems

The decoder may use both the original instance and the target witness. It must work for every target solution; it cannot rely on a solver returning a specially chosen one. This matters when a graph has many endpoints or a game has many equilibria.

Totality also explains why the usual SAT decision reduction is not an immediate model of hardness here. A total solver always returns something, including on instances constructed from unsatisfiable formulas. A reduction intended to decide SAT would need to specify how to interpret that answer.

L18.3 The End-of-Line problem

Consider a finite directed graph in which every vertex has at most one incoming edge and at most one outgoing edge. Its nontrivial components are directed paths or cycles. If one vertex has unequal in-degree and out-degree, some other vertex must also be unbalanced, because the sum of out-degree minus in-degree over all vertices is zero.

The graph we use is exponentially large but succinctly represented. Its vertices are the \(n\)-bit strings, and two Boolean circuits \(P,S : \{0,1\}^{n} \to \{0,1\}^{n}\) propose predecessors and successors. Define an edge \(v \to w\) precisely when

Requiring agreement between the two circuits ensures in-degree and out-degree at most one. Self-loops are treated as absent edges.

This convention handles every circuit pair. On the usual valid instances, \(0\) is a specified source with one outgoing edge and no incoming edge, and the task is to find another endpoint. An isolated vertex has both degrees zero and is not an endpoint.

Following the path from \(0\) will eventually find an endpoint, but can require exponentially many steps. The input contains circuits of polynomial size, not an explicit list of all \(2^{n}\) vertices. The gap between verification and search is therefore compatible with a very simple graph-theoretic existence proof.

L18.4 PPAD and other total-search classes

End-of-Line is complete by definition and transitivity of reductions. PPAD is a subclass of TFNP: composing a reduction with a locally verifiable endpoint certificate gives the requisite search relation, with the standard witness encoding that includes the target endpoint when necessary.

Other classes organize total search by different existence principles. PPA uses parity of odd-degree vertices in undirected graphs; PPP uses a pigeonhole principle; PLS uses the existence of a local optimum in a finite search space with efficiently computable improving moves. These names identify formal reduction classes. A proof that merely mentions parity or a potential function still needs an efficient encoding and a reduction before it establishes membership.

L18.5 Encoding a PPAD reduction

Lecture 2, “Brouwer and Sperner” established the geometric ingredients: the directed Sperner graph and the conversion from a trichromatic cell to an approximate fixed point. We now use those results to explain what a polynomial-time reduction must actually construct [Pap94].

Short cell encodings.   Consider the two-dimensional Sperner grid (Section L2.1) with \(2^{b}\) subdivisions per coordinate. Its interior colors are given by a Boolean circuit \(C\) on the binary coordinates; the standard boundary colors are imposed by a fixed rule. Thus validity of the boundary does not require checking exponentially many outputs of \(C\). Splitting each grid square along a fixed diagonal produces \(2^{2b+1}\) triangles, but a triangle is specified by only its two square indices and one bit selecting the half-square. The boundary padding (Section L2.2) adds only a constant number of bits to this \(O(b)\)-bit encoding.

Local predecessor and successor circuits.   Given a cell encoding, compute its three corners, evaluate their colors, and apply the orientation rule for the Sperner graph (Section L2.2.1) to identify its incoming and outgoing neighbors. This uses a constant number of calls to \(C\) and arithmetic on \(O(b)\)-bit coordinates. These local procedures therefore give polynomial-size circuits \(P,S\); constructing them never requires listing the grid. A missing neighbor is represented by the cell itself. Relabel the known boundary source as the all-zero vertex, and make unused bit strings isolated vertices by setting \(P(v)=S(v)=v\).

A decoder for every endpoint.   By these Sperner-graph properties, every unbalanced vertex other than the designated boundary source is a trichromatic cell. Decoding its coordinates takes polynomial time. Consequently, any valid End-of-Line answer solves the succinct Sperner instance, including an endpoint on a different path from the one that starts at zero. This is the search-reduction requirement from Section L18.2.

The reduction has polynomial cost in the circuit description and \(b\), even though the represented graph has exponentially many vertices. End-of-Line is asked to supply an endpoint; the reduction does not find one by tracing a potentially exponential path. This distinction is what makes the Sperner existence argument a PPAD membership argument.

For a fixed-point application, one must additionally derive a suitable polynomially bounded precision \(b\) and an efficiently computable coloring from the finite description of the function and the requested accuracy. The quantitative approximation bound (Theorem L2.4) supplies this accuracy control; continuity alone does not supply these computational guarantees [EY10]. The two-dimensional example explains the encoding step. Applications in variable dimension require the corresponding higher-dimensional construction.

L18.6 The connection to Nash computation

Membership reduces approximate Nash to End-of-Line via a fixed-point construction. Hardness reduces End-of-Line to a game whose every sufficiently accurate equilibrium decodes to a valid endpoint.

Lecture 19, “PPAD-hardness of Nash equilibrium” uses action probabilities as circuit variables and payoff incentives to enforce gate relations [DGP09[DGP09] Daskalakis, C., Goldberg, P. W., & Papadimitriou, C. H. (2009). The Complexity of Computing a Nash Equilibrium. SIAM Journal on Computing, 39(1), 195–259. link; CDT09[CDT09] Chen, X., Deng, X., & Teng, S.-H. (2009). Settling the complexity of computing two-player Nash equilibria. Journal of the ACM (JACM), 56(3), 1–57.]. The gates, payoff normalization, and approximation tolerance must be specified. PPAD-completeness concerns worst-case instances; a long path-following algorithm alone proves no lower bound on all algorithms.