Quantum stratenic game theory Shengyu Zhang The Chinese University of Hong Kong
Shengyu Zhang The Chinese University of Hong Kong
Why we are here? Understanding the power of quantum Computation:quantum algorithms/complexity Communication:quantum info.theory This work:game theory
Why we are here? ◼ Understanding the power of quantum ❑ Computation: quantum algorithms/complexity ❑ Communication: quantum info. theory ❑ … ◼ This work: game theory
Game:Two basic forms SCISSORS strategic (normal)form extensive form
Game: Two basic forms strategic (normal) form extensive form
Game:Two basic forms n players:P1,...,P Pi has a set Si of strategies ■P,has a utility function u:S→R SCISSORS ▣S=S1×S2×…×Sn strategic (normal)form
Game: Two basic forms strategic (normal) form ◼ n players: P1 , …, Pn ◼ Pi has a set Si of strategies ◼ Pi has a utility function ui : S→ℝ ❑ S = S1 S2 ⋯ Sn
Nash equilibrium Nash equilibrium:each player has adopted an optimal strategy,provided that others keep their strategies unchanged
Nash equilibrium ◼ Nash equilibrium: each player has adopted an optimal strategy, provided that others keep their strategies unchanged
Nash equilibrium Pure Nash equilibrium: a joint strategy s=(s1,...,s)s.t.Vi, u(S,S)≥u(S,S) (Mixed)Nash equilibrium (NE): a product distribution p=p1×..×Pst.i,s,' Es-plu(s,s】≥Es-puS,sl
Nash equilibrium ◼ Pure Nash equilibrium: a joint strategy s = (s1 , …, sn ) s.t. i, ui (si ,s-i ) ≥ ui (si ’,s-i ) ◼ (Mixed) Nash equilibrium (NE): a product distribution p = p1 … pn s.t. i,si ’ Es←p [ui (si ,s-i )] ≥ Es←p [ui (si ’,s-i )]
Correlated equilibrium Correlated equilibrium (CE):p s.t.Vi,si,si EsA p(gs)[ui(si;sii)].Es p(gs:)[ui(s;Sii)] CE NE n {product distributions} Nash and Aumann:two Laureate ofNobel Prize in Economic Sciences
Correlated equilibrium ◼ Correlated equilibrium (CE): p s.t. i, si , si ’ ◼ CE = NE ∩ {product distributions} E s ¡ i à p( ¢jsi ) [ui (si ;s¡ i )] ¸ E s ¡ i à p(¢jsi ) [ui (s 0 i ;s¡ i )] Nash and Aumann: two Laureate of Nobel Prize in Economic Sciences
Why correlated equilibrium? Traffic Light Game theory Cross natural Stop -100 0 Cross -100 1 0 Stop 0 0 ■ 2 pure NE:one crosses and one stops.Payoff:(0,1)or(1,0) Bad:unfair. 1 mixed NE:both cross w.p.1/101. Good:Fair 口 Bad:Low payoff:both ~0.0001 Worse:Positive chance of crash CE:(Cross,Stop)w.p.1,(Stop,Cross)w.p.V Fair,high payoff,0 chance of crash
Why correlated equilibrium? Cross Stop Cross -100 -100 0 1 Stop 1 0 0 0 Game theory natural ◼ 2 pure NE: one crosses and one stops. Payoff: (0,1) or (1,0) ❑ Bad: unfair. ◼ 1 mixed NE: both cross w.p. 1/101. ❑ Good: Fair ❑ Bad: Low payoff: both ≃ 0.0001 ❑ Worse: Positive chance of crash ◼ CE: (Cross,Stop) w.p. ½, (Stop,Cross) w.p. ½ ❑ Fair, high payoff, 0 chance of crash. Traffic Light
Why correlated equilibrium? Game theory Math natural nice Set of correlated equilibria is convex. The NE are vertices of the CE polytope (in any non- degenerate 2-player game) All CE in graphical games can be represented by ones as product functions of each neighborhood
Why correlated equilibrium? Game theory natural Math nice ◼ Set of correlated equilibria is convex. ◼ The NE are vertices of the CE polytope (in any nondegenerate 2-player game) ◼ All CE in graphical games can be represented by ones as product functions of each neighborhood
Why correlated equilibrium? Game theory Math natural nice CS feasible [Obs]A CE can found in poly.time by LP. natural dynamics-approximate CE. A CE in graphical games can be found in poly.time
Why correlated equilibrium? Game theory natural Math nice ◼ [Obs] A CE can found in poly. time by LP. ◼ natural dynamics → approximate CE. ◼ A CE in graphical games can be found in poly. time. CS feasible