Complexity of Nash
Lecturer: Constantinos Daskalakis
Function NP(FNP)
The complexity class FNP is the function problem(output is more complex) extension of the decision problem (output Yes or No) class NP.
Search problem L:
Def. Relation RL⊆ {0,1}* × {0,1}* : (x,y)∈RL iff y is a solution to x
A search problem is a total iff:
∀x,∃y : (x,y)∈R
L∈FNP :
∃AL(.,.) which is a p-time algorithm, and polynnomial function pL(.) :
(1) ∀x,y : AL(x,y)=1⇔(x,y)∈RL
(2) ∀x: ∃y s.t. (x,y)∈RL⇒∃z with |z|≤pL(|x|) s.t. (x,z)∈R
TFNP = { L∈FNP|L is total }
FNP-completeness
Poly-time (karp) reducible
A search problem L∈FNP is poly-time (karp) reducible to another L′∈FNP , associated with AL and pL iff exist efficiently computable function f,g :
(1) f : {0,1}* → {0,1}* maps inputs x to L into inputs f(x) to L’
(2) ∀x,y:AL(f(x),y)=1⇒AL(x,g(y))=1
∀x:AL(f(x),y)=0⇒AL(x,g(y))=0,∀y
FNP-complete
L∈FNPL′is p−time reducible to L,∀L′∈FNP
Proof of Sperner’s Lemma
- Introduce an outer boundary, that does not create new tri-chromatic triangles.
- Introduce an artificial tri-chromatic triangle (left-bottom corner).
- Define a directed walk starting from the artificial tri-chromatic triangle:
If exist red - yellow door, cross it with red on your left hand.
- Then it must stop somewhere inside. This can only happen at tri-chromatic triangle.
完成以上步驟，我們構造一幅圖(Generic PPAD)，圖的頂點由三角形組成，所有的頂點的出入度都小于等于1，圖的邊由以上路徑組成。在這樣的情況下，度數為0的點表示都是其他三角形，為1的是三色三角形，為2的是沒有藍色頂點的三角形。
下證：至少存在一個人工（起點）三色三角形則必存在另一個三色三角形。
Lemma: A directed graph with an unbalanced node (in≠out) must have another.
End of The Line: If 0n is an unbalanced node, find another unbalanced node. Otherwise output 0n .
PPAD: (“Polynomial Parity Arguments on Directed graphs”) = { Search problems in FNP reducible to END OF THE LINE }
PPAD-Completeness of NASH
- Generic PPAD → Embed PPAD → Sperner (幫助上色的三維坐标) → Brouwer → ArithmcircuitSAT → PolymatrixNash → Nash
Graphical Game: player 是圖中的節點，player的payoff隻和它們自己的側露額以及指向它的節點決定。
Polymatrix Games [Janovskaya ‘68’]
Graphical games with edge-wise separable utility functions:
uv(x1,...,xn)=∑(w,v)∈Euw,v(xw,xv)=∑(w,v)∈ExTvA(v,w)xw
ArthmCircultSAT → PolyMatrixNash
我們可以構造addition gadget, subtraction gadget 等
- copy: z=x
- addition: z=min{1,x+y}
- substraction: z=max{0,x-y}
- set equal to a constant: z=max{0,min{1, α }}
- multiply by a constant: z = max{0,mnin{1, αx }}
- comparison: z = 1 if (x>y) 0 if x
Escape 1: Approximation
[Daskalakis’11, Rubinstein’15]:
For some ϵ>0 , in 2-player games, computing a pair of mixed strategies s.t. no player can improve his current payoff by more than ϵ -fraction is PPAD-complete.
- Absolute error
-
- Is unlikely PPAD-hard nlog(n/ϵ2)
- P algorithm is missing despite a long line of research
- LMM’03 cannot be improved unless PPAD⊆Time(2n√)
Escape 2: Games w/ Special Structure
- Arbitrary normal form are hard but 2-player zero-sum aren’t
- Identify even broader families of games are tractable
Multiplayer zero-sum game
Take anyarbitrary two-player game, between Alice and Bob
Add Samwho does not affect Alice or Bob’s payoffs but receives:
PAlice(σ)+PBob(σ),∀outcome σ
In zero-sum polymatrix games:
- Found with LP
- Convex set
- If every node uses no-regret learning algorithm (will be defined soon),
Anonymous Games
Anonymous Games : Every player might have a different payoff function, which only depends symmetrically on the otherplayers’ actions
E.g.Auction, traffic, social phenomena
Arbitrarily good approximations are intractable if # strategies does not scale to infinity (Exact eq. is intractable)
Interesting relation to limit theorems in probability:
∀ϵ,n , X1+…Xn of any independent Bernolli 0/1 random variables is ϵ -close in L1 -distance to
the sum of i.i.d. Bernoullis, or
c+∑1/ϵ3i=1Yi , for some constant x & independent Berno Yi
Implies:
In every n-players 2-strategy anonymous game, there exists ϵ -Nash equilibrum in which at most 1/ϵ3 players randomize all players
Escape 3:Alternative solution concepts
Correlated vs Nash
Correlatedequilibrium
- Similar to Nash, except players’ randomization can be correlated
- No player has incentive to deviate given own sampled pure action from the joint distribution
Equilibrium condition expressive as linear constraints on the joint action distribution
- Solvable by LP
In normalform games, LP has polynomial size in game description:
- LP maintains a variable for every pure strategy profile
- Same #variables as title # payoff…
Correlatedeq in P while Nash is PPAD-completed