# 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

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]
}

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.

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

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)