6.896 Topics in Algorithmic Game Theory March 1, 2010Lecture 8Lecturer: Constantinos Daskalakis Scribe: Alan Deckelbaum, Anthony KimNOTE: The content of these notes has not been formally reviewed by thelecturer. It is recommended that they are read critically.1 IntroductionWe begin by developing a complexity theory of total search problems in FNP, by defining a few complexityclasses and discussing relationships between them. We then proceed to lay down the foundations towardsshowing that NASH is complete for the complexity class PPAD.2 Complexity Theory of Total Search ProblemsWe describe several complexity classes inside FNP. We define these classes by taking a combinatorialargument of existence (such as the parity argument or the pigeonhole principle) and defining a totalproblem that amounts to searching for the object whose existence is guaranteed.2.1 PPADThe complexity class PPAD (“Polynomial Parity Argument on Directed Graphs”) was proposed byChristos Papadimitriou in 1994 [6]. Its goal is to capture the complexity of searching for an objectwhose existence is guaranteed by the principle that, “A directed graph with an unbalanced node (indegree6= outdegree) must have another unbalanced node.”Suppose that we describe an exponentially large graph with vertex set {0, 1}n, where each vertex hasin-degree and out-degree at most 1 by providing two circuits, P and N . Each circuit takes as input anode id (a string in {0, 1}n) and outputs a node id (another string in {0, 1}n). We interpret our graphas having a directed edge from v1to v2iff the following two properties hold:• P (v2) = v1• N(v1) = v2We can think of the circuit P as returning a “possible previous” node, and the circuit N as returninga “possible next” node. If these circuits agree (that is, if P says that v1is previous to v2, and if N saysthat v2is next after v1), then we interpret our graph as having a directed edge from v1to v2. Noticethat, by this formalization, any two circuits P and N mapping {0, 1}n→ {0, 1}nwill define some graph.Furthermore, it is important to notice that, with our characterization, we can efficiently determine boththe in-neighbor and the out-neighbor (if they exist) of a given vertex v. This was the case in our proofof Sperner’s lemma, where we could use local information to efficiently determine the in-neighbor andout-neighbor of a given simplex.Inspired by the above discussion, we define the problem END OF THE LINE as follows:Definition 1. The problem END OF THE LINE is defined as follows: Given two circuits P andN as above, if 0nis an unbalanced node in the graph, find another unbalanced node; otherwise, return“yes.”Given this definition we can define the class PPAD as the class of all search problems that arepolynomial-time reducible to END OF THE LINE:8-1Definition 2. The complexity class PPAD is the set {search problems in FNP poly-time reducible toEND OF THE LINE }.Remark 1. Note that we defined PPAD in terms of its complete problem. This is in the same spirit asdefining FNP as all problems poly-time reducible to SAT. There is an alternative definition of PPAD interms of Turing Machines, but it’s more cumbersome to work with and we won’t present it.Remark 2 (Syntactic vs Semantic Classes). Note that the END OF THE LINE problem is well-definedand guaranteed to possess a solution for all input circuits P and N that map {0, 1}nto {0, 1}n. This isa very important property of PPAD in that it allows us to enumerate all search problems in the class.(To justify this rigorously we need to look at the Turing machine definition of the class. ) The existenceof such an enumeration makes our class “syntactic” allowing hardness results to be obtained.From our arguments from last lecture, it follows that the following reductions are possibleNASH → BROU W ER → SP ERNER ∈ P P AD ⊂ F NP.where the symbol “→” represents polynomial-time reducibility.2.2 Other “Arguments of Existence”The complexity class PPAD is based on the principle that “A directed graph with an unbiased node musthave another unbalanced node”. We can define other complexity classes based on different arguments ofexistence. Examples of other such classes are the following:• PPA: “If an undirected graph has a node of odd degree, it must have another.”• PLS: “Every directed acyclic graph must have a sink.”• PPP: “If a function maps n elements to n − 1 elements, it must have a collision.”We now define each of the above classes formally, in a similar manner to our definition of PPAD.2.2.1 PPAThe class PPA (polynomial-time parity arguments) is an undirected analogue of PPAD, based on theprinciple that “If an undirected graph has a node of odd degree, it must have another.” We start bydefining a problem called ODD-DEGREE-NODE. In this problem, we are given a circuit C which takesas input a node id (a string in {0, 1}n) and as output returns a set of at most d node id’s. The circuitC can be thought of as outputting “possible neighbors” of the input node. We interpret two verticesv1and v2as being connected in the graph iff v1∈ C(v2) and v2∈ C(v1). The ODD-DEGREE-NODEproblem is defined as follows:Definition 3. ODD-DEGREE-NODE: Given a circuit C as above, if 0nhas odd degree, find anothervertex with odd degree. Otherwise, say “yes.”The class PPA consists of problems which are reducible to ODD-DEGREE-NODE:Definition 4. The complexity class PPA is the set {search problems in FNP poly-time reducible toODD DEGREE NODE }.2.2.2 PLS (Johnson-Papadimitriou-Yannakakis ’88 [5])The class PLS (polynomial local search) is based on the existence argument that, “Every directed acyclicgraph has a sink.” We define a problem FIND SINK in a manner analogous to the above. In our problem,we will have two input circuits. The circuit C takes as input a node id and returns as output a set of atmost d node id’s. We also have another circuit F (the “potential function”) which maps a node id to areal number.8-2The circuits C and F together define a directed acyclic graph, where we put a directed edge from v1to v2iff both v2∈ C(v1) and F (v2) > F (v1). (Note that, as before, we make no real restrictions on thecircuit C: it is allowed for example to have v1∈ C(v2) but v26∈ C(v1)). The directed graph resultingfrom C and F is clearly acyclic, since F increases along directed edges.We now define the problem FIND SINK:Definition 5. FIND SINK: Given circuits C and F as