A notion of being stable:equilibrium Some combination of strategies is stable:No player wants to change his/her current strategy,provided that others don't change. --Nash Equilibrium. (Pure)Nash Equilibrium:A joint strategy s s.t. u(S)≥u('s),i. In other words,s;achieves maxs ;u(s's)
A notion of being stable: equilibrium ◼ Some combination of strategies is stable: No player wants to change his/her current strategy, provided that others don’t change. --- Nash Equilibrium. ◼ (Pure) Nash Equilibrium: A joint strategy s s.t. ui (s) ≥ ui (si ’s-i ), ∀i. ◼ In other words, si achieves maxs_i’ui (si ’s-i )
■Prisoners'dilemma ISP routing Confess Silent 4 5 Confess 4 1 1 2 Silent 5 2
◼ Prisoners’ dilemma ◼ ISP routing Confess Silent Confess 4 4 5 1 Silent 1 5 2 2
Prisoners'dilemma ISP routing Pollution game:All B S countries don't control the pollution. 6 1 B Battle of sexes:both 5 1 are stable. 2 5 S 2 6
◼ Prisoners’ dilemma ◼ ISP routing ◼ Pollution game: All countries don’t control the pollution. ◼ Battle of sexes: both are stable. B S B 6 5 1 1 S 2 2 5 6
Example 5:Penny matching. Two players,each can exhibit one bit. 0 1 If the two bits match,then red player wins and gets payoff 1. Otherwise,the blue player 0 wins and get payoff 1. 0 ■Find a pure NE? Conclusion:There may not exist Nash Equilibrium in a game. 1 7 0
Example 5: Penny matching. ◼ Two players, each can exhibit one bit. ◼ If the two bits match, then red player wins and gets payoff 1. ◼ Otherwise, the blue player wins and get payoff 1. ◼ Find a pure NE? ◼ Conclusion: There may not exist Nash Equilibrium in a game. 0 1 0 1 0 0 1 1 0 1 1 0
Mixed strategies Consider the case that players pick their strategies randomly. Player i picks s according to a distribution pi. o Let p=p1×…×pn: os←-p:draw s from p. Care about:the expected payoff Es.p[u(s)] Mixed Nash Equilibrium:A distribution p s.t. Es-plu (s)]2Esp[ui(s)], V p'different from p only at p(and same at other distributions p)
Mixed strategies ◼ Consider the case that players pick their strategies randomly. ◼ Player i picks si according to a distribution pi . ❑ Let p = p1 ⋯ pn . ❑ s←p: draw s from p. ◼ Care about: the expected payoff Es←p [ui (s)] ◼ Mixed Nash Equilibrium: A distribution p s.t. Es←p [ui (s)] ≥ Es←p’[ui (s)], ∀ p’ different from p only at pi (and same at other distributions p-i )