# The Complexity of Computing a Nash Equilibrium and Other Inefficient Proofs of Existence <style> .reveal { font-size: 26px; } </style> --- ## Outline 1. Introduction 2. Proofs of Existence and Their Corresponding Computational Problems - Nash Equilibria - Brouwer's Fixed-Point Theorem - Sperner's Lemma 3. Function Problem 4. Parity Argument 5. Problems in **PPAD**-complete 6. Other Inefficient Proofs of Existence 7. Rogue Problems 8. References --- ## Introduction ---- ### Nash Equilibria *prisoner’s dilemma* game | | cooperate | defect | |:-:|:-:|:-:| | **cooperate** | 0, 0 | -5, 1 | | **defect** | 1, -5 | -4, -4 | ---- <!-- .slide: data-auto-animate="true" --> ### Nash Equilibria *penalty shot* game | | kick left | kick right | |:-:|:-:|:-:| | **dive left** | 1, -1 | -1, 1 | | **dive right** | -1, 1 | 1, -1 | ---- <!-- .slide: data-auto-animate="true" --> ### Nash Equilibria a mixed strategy Nash equilibrium of *penalty shot* game | | kick left ($\cfrac{1}{2}$) | kick right ($\cfrac{1}{2}$) | |:-:|:-:|:-:| | **dive left** ($\cfrac{1}{2}$) | 1, -1 | -1, 1 | | **dive right** ($\cfrac{1}{2}$) | -1, 1 | 1, -1 | ---- ### Nash Equilibria - Nash showed that every game has an equilibrium in mixed strategies. - If your laptop can’t find it, then, probably, neither can the market. ---- ### Algorithms for Computing Equilibria - A celebrated algorithm for computing equilibria in 2-player games, which appears to be efficient in practice, is the Lemke-Howson algorithm. - It can be generalized to multi-player games with some loss of efficiency. - Some algorithms are based on computing approximate fixed points, e.g., Scarf's algorithm. - Lipton and Markakis point out that standard quantifier elimination algorithms can be used to solve them. - None of these algorithms is known to be polynomial-time. ---- ### Properties for Computing Equilibria - Lipton, Markakis and Mehta showed that, If we only require an $\epsilon$-approximate Nash equilibrium, then a subexponential algorithm is possible. - If the Nash equilibria sought are required to have any special properties, for example optimize total utility, the problem typically becomes NP-complete. - Bebelis established that the Nash equilibrium problem for 3 players captures the computational complexity of the same problem with any number of players. --- ## Proofs of Existence and Their Corresponding Computational Problems ---- ### Nash Equilibria a mixed strategy Nash equilibrium of *penalty shot* game | | kick left ($\cfrac{1}{2}$) | kick right ($\cfrac{1}{2}$) | |:-:|:-:|:-:| | **dive left** ($\cfrac{1}{2}$) | 1, -1 | -1, 1 | | **dive right** ($\cfrac{1}{2}$) | -1, 1 | 1, -1 | ---- #### NASH - Given - the number of players - a strategy set for each player - an utility function for each player - Find an $\epsilon$-Nash equilibrum - No player can improve his expected payoff more than ε by switching to another strategy. ---- ### Brouwer's Fixed-Point Theorem > Any continuous map from a compact (closed and bounded) and convex subset of the Euclidean space into itself always has a fixed point. ---- ### Brouwer's Fixed-Point Theorem  ---- ### Brouwer's Fixed-Point Theorem  ---- ### Brouwer's Fixed-Point Theorem  ---- #### Nash's Proof of Existence | | kick left | kick right | |:-:|:-:|:-:| | **dive left** | 1, -1 | -1, 1 | | **dive right** | -1, 1 | 1, -1 |  ---- #### BROUWER - Given a function $F : [0, 1]^m \rightarrow [0, 1]^m$ that satisfies a Lipschitz condition - for all $x_1, x_2 \in [0, 1]^m : d(F(x_1), F(x_2)) \leq K \cdot d(x_1, x_2)$ - Find a point $x$ such that $d(F(x), x) \leq \epsilon$ ---- ### Sperner's Lemma  > Any coloring whose sides satisfying the property has odd number of tri-chromatic triangle. ---- ### Sperner's Lemma  ---- #### Proof of Brouwer's Fixed-Point Theorem   ---- ### k-D SPERNER - Given a k-dimensional cube by - the number of points on one side - a coloring function that colors each point one of the $k + 1$ colors - Find a k-simplex that contains all $k + 1$ colors --- ## Function Problem - problems in which an output more elaborate than "yes" or "no" is sought - e.g. **FSAT** is a function problem that asks an assignment if the given formula is satisfiable. - Also called search problem. ---- ## Function Problem - **FP**: the function problem version of **P** - **FNP**: the function problem version of **NP** - **TFNP**: the subclass of **FNP** that are guaranteed to have an answer - e.g. **NASH**, **MINKOWSKI**, **NECKLACE-SPLITTING** and **FACTORING** - **FP** $\subseteq$ **TFNP** $\subseteq$ **FNP** ---- ### TFNP - Any **TFNP** problem cannot be **FNP**-complete<br>unless **NP** $=$ co-**NP** - **TFNP** is a *semantic* class - *Semantic* classes seem to have no complete problems. - Are there important, syntactically definable, subclasses of **TFNP**? --- ## Parity Argument > Any finite graph has an even number of odd-degree nodes. ---- ### Chessplayer algorithm - $2n$-degree node $\Rightarrow$ $n$ $2$-degree nodes - $(2n + 1)$-degree node $\Rightarrow$ $n$ $2$-degree nodes and a leaf ```graphviz digraph { compound = true rankdir = LR subgraph cluster_left { edge [dir = none] node [shape = none, label = ""] 1 -> n [taillabel = "...", labeldistance = 2] 2 -> n n -> 3 n -> 4 [taillabel = "...", labeldistance = 2] n [shape = circle] } subgraph cluster_right { edge [dir = none] node [shape = none, label = ""] 5 -> n1 6 -> n2 n1 -> 7 n2 -> 8 n1 -> n2 [constraint = false, style = dotted] n1 [shape = circle] n2 [shape = circle] } 4 -> 5 [style = bold, ltail = cluster_left, lhead = cluster_right] } ``` ```graphviz digraph { compound = true rankdir = LR subgraph cluster_left { edge [dir = none] node [shape = none, label = ""] 1 -> n [constraint = false] 2 -> n [taillabel = "...", labeldistance = 4] 3 -> n [style = invis] 4 -> n n -> 5 n -> 6 [style = invis] n -> 7 [taillabel = "...", labeldistance = 2, labelangle=-45] n [shape = circle] {1; n; rank = same} } subgraph cluster_right { edge [dir = none] node [shape = none, label = ""] 8 -> n1 9 -> n2 10 -> n3 n2 -> 11 n3 -> 12 n2 -> n3 [constraint = false, style = dotted] n1 [shape = circle] n2 [shape = circle] n3 [shape = circle] } 6 -> 9 [style = bold, ltail = cluster_left, lhead = cluster_right] } ``` ---- ## Parity Argument > All graphs of degree of two or less have an even number of leaves. ```graphviz graph { dim = 4 layout = neato node [shape = circle, label = ""] 1 -- 2 2 -- 3 3 -- 4 5 -- 6 6 -- 7 7 -- 5 8 -- 9 9 -- 10 } ``` ---- ### Parity Argument for Directed Graph > All directed graphs where every vertex has both in-degree and out-degree at most one have sources and sinks coming in pairs. > If a directed graph has an unbalanced node (a vertex with different in-degree and out-degree), then it must have another. ---- ### Another Definition of **NP** > A decision problem **L** is in **NP** if and only if it is reducible to **SAT** in polynomial time. ---- ### **PPA** > A search problem is in **PPA** (Polynomial Parity Argument) if and only if it can be reduced to the following problem. - Given - a possibly exponentially large graph with vertex set $\{0, 1\}^n$ - a polynomial-time computable neighboring funciton - an odd-degree node $x$ - Find another odd-degree node. ---- ### **PPAD** > A search problem is in **PPAD** (Polynomial Parity Argument for Directed Graph) if and only if it can be reduced to the following problem. - Given - a possibly exponentially large directed graph with vertex set $\{0, 1\}^n$ - polynomial-time predecessor and successor funcitons - Both output at most one node. - a source $x$ - Find another source or a sink. ---- ## Parity Argument - **FP** $\subseteq$ **PPAD** $\subseteq$ **PPA** $\subseteq$ **TFNP** $\subseteq$ **FNP** - Let **PPA**' and **PPAD**' be the classes of problems that ask the particular leaf (or sink) that is connected to $x$. - **PPA**' = **PPAD**' = **FPSPACE** --- ## Problems in **PPAD**-complete ---- ### **SPERNER**  ---- ### **SPERNER**  ---- ### **SPERNER**  ---- ### **BROUWER**   ---- ### **NASH**  --- ## Other Inefficient Proofs of Existence - **PPP** - polynomial pigeonhole principle - If a function maps $n$ elements to $n − 1$ elements, then there is a collision. - **PPADS** - same as **PPAD**, except we are looking for an oppositely unbalanced node - **PLS** - polynomial local search - Every dag has a sink. - **PTFNP** - Provable **TFNP** - We have a consistent deductive system, and a concisely-represented proof having exponentially many steps, that leads to a contradiction. There must be an error somewhere in the proof. ---- ## Other Inefficient Proofs of Existence ```graphviz digraph { node [shape = none, fontsize = 24] rankdir = BT size = 5 FP -> UEOPL UEOPL -> EOPL EOPL -> CLS FP -> PWPP CLS -> PLS CLS -> PPAD PPAD -> PPA PPAD -> PPAQ PPAD -> PPADS PPADS -> PPP PWPP -> PPP PLS -> PTFNP PPA -> PTFNP PPAQ -> PTFNP PPP -> PTFNP PTFNP -> TFNP TFNP -> FNP PPAQ [label = <PPA<sub>q</sub>>] { PLS PPA PPAQ PPP rank = same} { PPAD PWPP rank = same } } ``` --- ## Rogue Problems - These problems belong to **TFNP**, but are not yet classified to its subclasses. - $\text{Factoring}$ - $\text{Factoring}$ is reducible in randomized polynomial time to a **PPA** problem and a **PWPP** problem. - Both reductions can be derandomized under the assumption of the generalized Riemann hypothesis. - $\text{Ramsey}$ - Given a circuit generated graph with $4^n$ node, find $n$ nodes that are either a clique or an independent set. - A variation of $\text{Ramsey}$ called $\text{colorful-Ramsey}$ is **PWPP**-hard. - $\text{Bertrand-Chebyshev}$ - Find a prime between $n$ and $2n$. --- ## References - [The Complexity of Computing a Nash Equilibrium](https://people.csail.mit.edu/costis/journal_ver10.pdf) - [Simplified](https://people.csail.mit.edu/costis/simplified.pdf) - [On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence](https://www.sciencedirect.com/science/article/pii/S0022000005800637) - [TFNP: An Update](https://link.springer.com/chapter/10.1007/978-3-319-57586-5_1)