香港中文大学：Quantum strategic game theory

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