The Complexity of Computing a Nash Equilibrium and Other Inefficient Proofs of Existence
Outline
- Introduction
- Proofs of Existence and Their Corresponding Computational Problems
- Nash Equilibria
- Brouwer's Fixed-Point Theorem
- Sperner's Lemma
- Function Problem
- Parity Argument
- Problems in PPAD-complete
- Other Inefficient Proofs of Existence
- Rogue Problems
- 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
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
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\).
- \(\text{Factoring}\)
The Complexity of Computing a Nash Equilibrium and Other Inefficient Proofs of Existence
{"metaMigratedAt":"2023-06-15T05:13:19.990Z","metaMigratedFrom":"Content","title":"The Complexity of Computing a Nash Equilibrium and Other Inefficient Proofs of Existence","breaks":true,"contributors":"[{\"id\":\"f9547eff-9cf4-46a1-8726-bc20b1554d01\",\"add\":16647,\"del\":5224}]"}