# The Complexity of Computing a Nash Equilibrium and Other Inefficient Proofs of Existence
> 0756127 陳達仁
<style>
.reveal {
font-size: 32px;
}
</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. Open Problems
8. References
---
## Introduction
----
### Nash Equilibria
*prisoner’s dilemma* game
| | cooperate | defect |
|:-:|:-:|:-:|
| **cooperate** | 0, 0 | -5, 1 |
| **defect** | 1, -5 | -4, -4 |
----
### Nash Equilibria
*penalty shot* game
| | kick left | kick right |
|:-:|:-:|:-:|
| **dive left** | 1, -1 | -1, 1 |
| **dive right** | -1, 1 | 1, -1 |
----
### 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
![](https://i.imgur.com/QkQvVXr.png =x400)
----
### Brouwer's Fixed-Point Theorem
![](https://i.imgur.com/E4R4YWx.png =x400)
----
### Brouwer's Fixed-Point Theorem
![](https://i.imgur.com/sWRKBO2.png =x400)
----
#### Nash's Proof of Existence
| | kick left | kick right |
|:-:|:-:|:-:|
| **dive left** | 1, -1 | -1, 1 |
| **dive right** | -1, 1 | 1, -1 |
![](https://i.imgur.com/LIIsLC8.png =x400)
----
#### 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
![](https://i.imgur.com/aUsPPpD.png =x400)
> Any coloring whose sides satisfying the property has odd number of tri-chromatic triangle.
----
### Sperner's Lemma
![](https://i.imgur.com/qsIFLdy.png =x400)
----
#### Proof of Brouwer's Fixed-Point Theorem
![](https://i.imgur.com/6TQKda7.png =x400)
![](https://i.imgur.com/VJYdzsa.png =x150)
----
### 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**, **BROUWER**, **SPERNER** 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 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**
![](https://i.imgur.com/gmzZEvO.png =x500)
----
### **SPERNER**
![](https://i.imgur.com/bU58SFJ.png =x500)
----
### **SPERNER**
![](https://i.imgur.com/ExlcifF.png =x500)
----
### **BROUWER**
![](https://i.imgur.com/6TQKda7.png =x400)
![](https://i.imgur.com/VJYdzsa.png =x150)
----
### **NASH**
![](https://i.imgur.com/LIIsLC8.png =x400)
---
## 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 -> CLS
FP -> PWPP
CLS -> PLS
CLS -> PPAD
PPAD -> PPA
PPAD -> PPADS
PPADS -> PPP
PWPP -> PPP
PLS -> PTFNP
PPA -> PTFNP
PPP -> PTFNP
PTFNP -> TFNP
TFNP -> FNP
}
```
---
## Open Problems
- Define other complexity classes that are syntactic subclasses of **TFNP** and containing natural, important problems, by isolating other styles of "inefficiently constructive proofs of existence.
----
## Open Problems
- Is **FACTORING** in one of these classes?
- It is reducible in randomized polynomial time to a **PPA** problem and to a **PPP** problem. Both can be derandomized under the assumption of the generalized Riemann hypothesis. https://doi.org/10.1016/j.jcss.2015.08.001
- How about the remaining "rogue problems" **BERTRAND-CHEBYSHEV** and **RAMSEY**?
- They are both conjectured to be in **PPP**.
----
## Open Problems
- Are there natural complete problems for **PPA**?
- https://doi.org/10.1145/3313276.3316334 show that **NECKLACE-SPLITTING** and **DISCRETE-HAM-SANDWICH** are **PPA**-complete.
- How about **PPP**?
- https://doi.org/10.1109/FOCS.2018.00023 show that constrained-**SIS** is **PPP**-complete.
----
## Open Problems
- Prove that one of the problems known to be in **CLS** is **CLS**-complete. Alternatively, show that **CLS** is in **P**.
---
## 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)

{}