Mixed-Strategy
Randomization
- Not a good idea to play deterministic game
- so another player will always want to choose better results
- Idea: confuse them by playing randomly
- Consider the matching pennies: randomly picking actions is better
Pure vs mixed
- Pure strategy: only one action is played with positive probability
- Mixed strategy: more than one action is player with positive probability
- these actions are called the support of the mixed strategy
Expected payoff
- [math]u_i(s) = \sum_{a \in A} u_i(a) Pr(a | s)[/math] - sum over all cells of the game with each payoff multiplied by probability it happens
- [math]Pr(a | s) = \prod_{j \in N} s_j(a_j)[/math]: probability it happens - product of each player's probability to select this cell
Best Response
- [math]s^*_i \in BR(s_{-i}) \iff \forall s_i \in S_i, u_i(s^*_i, s_{-i}) \geqslant u_i(s_i, s_{-i})[/math]: [math]s^*_i[/math] is a BR if it's as good as others or better
- [math]s = \{s_1, ..., s_n\}[/math] is a Nash Equilibrium if [math]\forall i, s_i \in BR(s_{-i})[/math]
Theorem (Nash)
- Every finite gave has a Hash Equilibrium
- Matching pennies - NE is to play randomly 50/50
- Coordinating game - NE is to play randomly 50/50
- Prisoners' dilemma - only a pure strategy NE, no mixed one
Computing
- hard to compute
- easier when you can guess the support (pure strategies with positive probability)
- Indifference
- if P1 best-responds with a mixed strategy
- P2 must make him indifferent
- He himself plays mixed strategy, so it's the best response
- if he's not indifferent, he will play the same strategy, and over time his opponent will use it
- [math]u_1(A) = u_1(B)[/math]
utility when P1 plays A = P1 plays B
- Battle of the Sexes
- [math]2p+0(1-p) = 0p + 1(1-p)[/math]; [math]p = 1/3[/math]
- [math]q+0(1-q) = 0q+2(1-q)[/math]; [math]q = 2/3[/math]
- Thus, the mixed strategies [math](2/3, 1/3)[/math] and [math](1/3, 2/3)[/math] are NE
Interpreting
- What does it mean to play a mixed strategy?
- Randomize to confuse your opponent
- consider the matching pennies
- Randomize what uncertain about the others' actions
- consider the battle of the sexes
Examples
- Predator vs Prey
- a competition between 2 animals
- possible strategies for each: be active or passive
- predator\prey
- what p and q are the mixed strategy equilibrium?
- predator plays active with q (rows, 1rd),
prey plays active with p (cols, 2nd)
predator:
{when plays active}
p {prey is active} * 2 {possible payoff}
+
(1 - p) {prey is passive} * 3 {possible payoff}
=
{when plays passive}
p {prey is active} * 3 {possible payoff}
+
(1 - p) {prey is passive} * (-1) {possible payoff}
=>
prey plays active with p = 4/5
- prey: [math]-5q-2(1-q) = -6q [/math]=> [math]q = 2/3[/math]
- Kicker vs Goalie
- Soccer penalty kicks
- usual
- kicker\goalie
- equlibrium is to play 1/2
- kicker is weak on right
- a kicker misses right every 4th time
- kicker\goalie
- K plays L with q, G plays L with p
- {L} [math]G: 0p+1(1-p) = 0.75p+0(1-p)[/math] {R}, [math]p = 4/7[/math]
- {L} [math]K: q+0.25(1-q) = 1-q;[/math] {R}, [math]q = 3/7[/math]
- result: Kicker kicks more to the Right!
- because G has adjusted
Sources