when we say that x and y are Δ-close (or Δ-far), we mean Δ-close in normalized 2-norm. Similarly, for a binary string π ∈ {0, 1}n, we denote
For a graph G = (V, E) and S ⊆ V, we use den(S) ∈ [0, 1] to denote the density of subgraph S,
2.1 Nash Equilibrium and Relaxations
A mixed strategy of player i is a distribution xi over i’s set of actions, Ai. We say that a vector of mixed strategies x ∈ × j∆Aj is a Nash equilibrium if every strategy ai in the support of every xi is a best response to the actions of the mixed strategies of the rest of the players, x−i. Formally, for every ai ∈ supp(xi),
Equivalently, x is a Nash equilibrium if each mixed strategy xi is a best response to x−i:
Each of those equivalent definitions can be generalized to include approximation in a different way.
Definition 2.1
ϵ-approximate Nash Equilibrium. We say that x is an ϵ-Approximate Nash Equilibrium (ϵ-ANE) if each xi is an ϵ-best response to x−i:
On the other hand, we generalize the first definition of Nash equilibrium in the following stricter definition:
Definition 2.2
ϵ-well-supported Nash Equilibrium. x is an ϵ-Well-Supported Nash Equilibrium (ϵ-WSNE) if every ai in the support of xi is an ϵ-best response to x−i: for every ai ∈ supp(xi),
WeakNash
We can further relax the (already more lenient) notion of ϵ-ANE by requiring that the ϵ-best response condition only hold for most of the players (rather than all of them).
Definition 2.3
(ϵ, δ)-WeakNash [Babichenko et al. 2016]. We say that x isan (∈, δ)-WeakNash if for a (1 − δ)-fraction of i’s, xi is an ϵ-best mixed response to x−i:
Definition 2.4
(∈, δ)-well-supported WeakNash. x is an (∈, δ)-well-supported WeakNash if for a (1 − δ)-fraction of i’s, every ai in the support of xi is an ϵ-best response to x−i:
2.2 PPAD and END-OF-A-LINE
The END-OF-A-LINE of a problem considers an implicitly represented, exponential-size, directed graph whose vertices have in- and out-degree at most 1 (this is without loss of generality). The special vertex 0n has in-degree 0, and the goal is to find another odd-degree vertex. The graph is a union of lines and cycles, so in particular the line starting at 0n ends with another odd-degree vertex.
The graph is implicitly defined with functions S, P that, for each vertex, give its Successor (outgoing neighbor) and Predecessor (incoming neighbor). In the computational variant of END-OF-A-LINE, S, P are given as explicit circuits, whereas in the query complexity variant they are given as oracles. There is also a communication complexity variant, whose definition is more involved and is deferred to Section 3.4.
In the formal definition of the computational variant, we also have to consider the case that S, P are inconsistent, i.e., for some u ≠ v we have S(u) = v, but P(v) ≠ u; we also allow the algorithm to succeed by finding such an inconsistency. (In the oracle model we can explicitly require that there are no inconsistencies.)
Definition 2.5
END-OF-A-LINE. The input to the problem is functions S, P : {0, 1}n → {0, 1}n, such that S(0n) = 0n ≠ P(0n). The output is another odd-degree vertex 0n ≠ v ∈ {0, 1}n such that P(S(v)) ≠ S(P(v)).
The computational complexity class PPAD is defined as the class of all total search problems reducible to END-OF-A-LINE.
MEMBERSHIP END-OF-A-LINE
The following variant of END-OF-A-LINE is equivalent and more convenient for some of our reductions. In particular, the problem is restricted to a subset of the vertices. The restricted vertex-set is defined implicitly via a membership function T : {0, 1}n → {0, 1}. Abusing notation, let T also denote the restricted set of vertices whose T-value is 1. We think of S and P as only applying to vertices in T, and connecting them to other vertices in T. Formally, we also allow the algorithm to return any violations.
Definition 2.6
MEMBERSHIP END-OF-A-LINE. The input to the problem is functions S, P : {0, 1}n → {0, 1}n and T : {0, 1}n → {0, 1}, such that S(0n) = 0n ≠ P(0n) and T(0n), T(S(0n)) = 1. The output is another odd-degree vertex 0n ≠ v ∈ {0, 1}n such that T(v) = 1 and v satisfies at least one of the following:
End-of-a-line. P(S(v)) = S(P(v));or
Boundary condition. T(S(v)) = 0 or T(P(v)) = 0.
Lemma 2.1
END-OF-A-LINE is equivalent to MEMBERSHIP END-OF-A-LINE.
Proof
Given an instance of END-OF-A-LINE, we can construct an equivalent instance of MEMBERSHIP END-OF-A-LINE by setting T ≡ 1. In the other direction, we can add self-loops to every vertex
