香港中文大学：A quantum protocol for sampling correlated equilibria unconditionally and without a mediator

A quantum protocol for sampling correlated equilibria unconditionally and without a mediator lordanis Kerenidis,LIAFA,Univ Paris 7,and CNRS Shengyu Zhang,The Chinese University of Hong Kong

A quantum protocol for sampling correlated equilibria unconditionally and without a mediator Iordanis Kerenidis, LIAFA, Univ Paris 7, and CNRS Shengyu Zhang, The Chinese University of Hong Kong

Normal-form games 。k players:P1y,Pk 。P,has a set S;of strategies 。P,has a utility SCISSORS function u:S→R -S=S1×S2×…×Sk strategic(normal)form

Normal-form games strategic (normal) form • k players: P1 , …, Pk • Pi has a set Si of strategies • Pi has a utility function ui : S→ℝ – S = S1  S2  ⋯  Sk

Representing a game Scissors 6eat竹pp 0,0 1,-1-1,1 Paper beats rock -1,1 0,0 1,-1 Rock beats scissors 1,1 -1,1 0,0

Representing a game 0, 0 1, -1 -1, 1 -1, 1 0, 0 1, -1 1, 1 -1, 1 0, 0

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,...,sk)s.t.Vi, u(sS)≥u(SS) -S.1=(S1,,S1-1S41,Si1】 Each Player i can also choose her strategy si randomly,say,from distribution pi. (Mixed)Nash equilibrium (NE): a product distribution p=p1×.×pks.t.i, E5←p[u(ss】≥Es←plu(s5] [VNM44,N51]Any game with a finite set of strategies has an NE

Nash equilibrium • Pure Nash equilibrium: a joint strategy s = (s1 , …, sk ) s.t. i, ui (si ,s-i ) ≥ ui (si ’,s-i ) – s-i = (s1 , …, si-1 , si+1, …, si-1 ) • Each Player i can also choose her strategy si randomly, say, from distribution pi . • (Mixed) Nash equilibrium (NE): a product distribution p = p1  …  pk s.t. i, Es←p [ui (si ,s-i )] ≥ Es←p [ui (si ’,s-i )] • [vNM44,N51] Any game with a finite set of strategies has an NE

W年E银MTW的 Torttado-2 Rock whip Death 0 6 Wha Camera-14 Sun-13 66中 Chainsaw-16 Fire-15 8833 School-17 98-pjoD S8up购d num Poison-1o Cage-20 E8-wover Au-21 28-unnes Peace.22 Death 6 24 Snake 25 Blood -26 RPS 27 Vulture- Monkey-29 King-30 Queen-31 Prince·32 73 Woman- 89W Baby-36 09 Man-37 L Home-38 Train-39 SCISSORS Car Co-oudnv D RPS-1O10K民 T'rce AVAILABLE! felsch herr!) CK

Algorithmic game theory • What if we have a large number of strategies? – Or large number of players?

intractability How computationally hard is it to find a Nash equilibrium(even in a two-player game)? -Optimal one:NP-hard.[Gilboa-Zemel'89] -Any one:PPAD-hard. [Daskalakis-Goldberg-Papadimitriou'06,Chen- Deng'06] 。Computationally Unfriendly！ Even worse,inefficient in game-theoretic sense!

intractability • How computationally hard is it to find a Nash equilibrium (even in a two-player game)? – Optimal one: NP-hard. [Gilboa-Zemel’89] – Any one: PPAD-hard. [Daskalakis-Goldberg-Papadimitriou’06, Chen￾Deng’06] • Computationally Unfriendly! • Even worse, inefficient in game-theoretic sense!

correlated equilibrium:game 2 pure NE:go to the same game. Payoff:(2,4)or (4,2) Battle of the Sexes -Bad:unfair. 1 mixed NE:each goes to city Baseball Softball preferred w.p.2/3. -Good:Fair -Bad:Low payoff:both 4/3 2 0 Baseball Worse:+ve chance of separate 0 CE:(Baseball,Softball)w.p., 0 4 Softball (Softball,Baseball)w.p. 0 2 Fair,high payoff,0 chance of separate

correlated equilibrium: game city Baseball Softball Baseball 2 4 0 0 Softball 0 0 4 2 • 2 pure NE: go to the same game. Payoff: (2,4) or (4,2) – Bad: unfair. • 1 mixed NE: each goes to preferred w.p. 2/3. – Good: Fair – Bad: Low payoff: both = 4/3 – Worse: +ve chance of separate • CE: (Baseball,Softball) w.p. ½ , (Softball,Baseball) w.p. ½ – Fair, high payoff, 0 chance of separate. Battle of the Sexes

Correlated equilibrium:definition Formally,CE is a joint distribution p on S1xS2 -A trusted mediator samples (s1,s2)-p, -and recommend Player i take strategy si. -Upon seeing only si,Player i doesn't deviate. Measure:Expected payoff,averaged over p(s) ·Es-plu(s)ls]≥Es-plu(s,'ss],i,S,S

Correlated equilibrium: definition • Formally, CE is a joint distribution p on S1S2 – A trusted mediator samples (s1 ,s2 )←p, – and recommend Player i take strategy si . – Upon seeing only si , Player i doesn’t deviate. • Measure: Expected payoff, averaged over p(∙|si ). • Es←p[ui (s)|si ] ≥ Es←p[ui (si ’s-i )|si ], i, si , si ’

Correlated equilibrium:math 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

Correlated equilibrium: math 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