Game theory 2
Lukáš Lehotský
llehotsky@mail.muni.cz
Sum-up of the previous lecture
Opponent
s1 s3
Me
S2 0 , 3 6 , 4
S3 1 , 5 5 , 2
Social welfare
Social welfare
• Situation where sum of all payoffs of an outcome is at its maximum
• Might lead to rationally unstable solutions
• Does not provide a solid analytical tool
Game M
B
Right Left
A
Right 2 , 2 0 , 0
Left 0 , 0 1 , 1
Game M – Social welfare
B
Right Left
A
Right 4 0
Left 0 2
Game N
B
l r
A
L 2 , 2 4 , 0
R 2 , 3 8 , -1
Game N – Social welfare
B
l r
A
L 4 4
R 5 7
Prisoner’s dilemma – Social welfare
B
c d
A
C 5 , 5 0 , 7
D 7, 0 3, 3
Prisoner’s dilemma – Social welfare
B
c d
A
C 10 7
D 7 6
Prisoner’s dilemma – Social welfare
B
c d
A
C 5 , 50 0 , 70
D 7, 0 3, 30
Prisoner’s dilemma – Social welfare
B
c d
A
C 55 70
D 70 33
Prisoner’s dilemma – Social welfare
B
C d
A
C 50 , 5 0 , 7
D 70, 0 30, 3
Prisoner’s dilemma – Social welfare
B
c D
A
C 55 7
D 70 33
Pareto efficiency
Game M
B
Right Left
A
Right 2 , 2 0 , 0
Left 0 , 0 1 , 1
Game M
B
Right Left
A
Right 2, 2 0 , 0
Left 0 , 0 1, 1
Game M – pure strategy equilibriums
B
Right Left
A
Right 2, 2 0 , 0
Left 0 , 0 1, 1
Pareto efficiency
• Outcome is Pareto efficient (Pareto optimal), if there is no other
outcome which is better or equal for all players and strictly better
for some player
• Conversely, outcome A is Pareto dominated, if there is outcome B
that makes all players as good (weakly better) and one player strictly
better compared to outcome A
• Pareto dominated outcome is not Pareto efficient
• Might lead to rationally unstable solutions
Game M – Pareto efficiency
B
Right Left
A
Right 2, 2 0 , 0
Left 0 , 0 1, 1
Pareto efficiency
A
B
Pareto efficiency
A
B
P
Pareto efficiency
A
B
P
X
Pareto efficiency
A
B
P
X
Pareto efficiency
A
B
P
Pareto efficiency
A
B
P
Y
Pareto efficiency
A
B
P
Y
Search for Pareto-dominated
outcomes
Prisoner’s dilemma – Pareto efficiency
B
c d
A
C 5 , 5 0 , 7
D 7, 0 3, 3
Prisoner’s dilemma – Pareto efficiency
B
c d
A
C 5 , 5 0 , 7
D 7, 0 3, 3
Prisoner’s dilemma – Pareto efficiency
B
c d
A
C 5 , 5 0 , 7
D 7, 0 3, 3
Game N
B
l r
A
L 2, 2 4 , 0
R 2, 3 8, -1
Game N – Pareto efficiency
B
l r
A
L 2, 2 4 , 0
R 2, 3 8, -1
Game N – Pareto efficiency
B
l r
A
L 2, 2 4 , 0
R 2, 3 8, -1
Pareto optimality a solid tool for
comparing equilibriums
Mixed-strategy
Nash equilibrium
Matching pennies
• Two players
• Players choose heads or tails
• If players match heads/tails, I (Player 1) win both coins
• If players don’t match heads/tails, opponent (Player 2) wins both
coins
Matching pennies
My pair
Heads Tails
Me
Heads 1 , -1 -1 , 1
Tails -1 , 1 1 , -1
Matching pennies – Pareto efficiency
My pair
Heads Tails
Me
Heads 1 , -1 -1 , 1
Tails -1 , 1 1 , -1
Matching pennies
My pair
Heads Tails
Me
Heads 1 , -1 -1 , 1
Tails -1 , 1 1 , -1
Matching pennies – mixed strategy
My pair
Heads (0.5) Tails (0.5)
Me
Heads
(0.5)
1 , -1 -1 , 1
Tails
(0.5)
-1 , 1 1 , -1
Calculation
of mixed-strategy NE
Game Y
B
L R
A
U 3 , -3 -2 , 2
D -1 , 1 0 , 0
Game Y – Pareto efficiency
B
L R
A
U 3 , -3 -2 , 2
D -1 , 1 0 , 0
Game Y – Pareto efficiency?
-4
-3
-2
-1
0
1
2
3
4
-4 -3 -2 -1 0 1 2 3 4
A
B
Game Y
B
L (q) R (1 - q)
A
U
(p)
3 , -3 -2 , 2
D
(1 - p)
-1 , 1 0 , 0
Game Y – Player A
• Player A plans to mix Up and Down strategy at a certain ratio p
• Player B might play Left or Right
• Player A must find such a probability of playing U and D that makes
Player B indifferent to selecting L or R
• Player B has to gain same utility from B’s choice Left and Right
• EUL = EUR
• Expected utility of Player B chosing Left:
• EUL = f(p)
• Expected utility of Player B chosing Right:
• EUR = f(p)
Game Y
B
L R
A
U
(p)
3 , -3 -2 , 2
D
(1 - p)
-1 , 1 0 , 0
Game Y
B
L R
A
U
(p)
3 , -3 -2 , 2
D
(1 - p)
-1 , 1 0 , 0
Game Y - Player A’s strategy
• EUL:
• Some % of time (p) gets B utility -3
• Rest of the time (1 - p) gets B utility 1
• EUL = (p)*(-3) + (1 - p)*(1)
• EUL = -3p + 1 - p
• EUL = 1 - 4p
B
L (q) R (1 - q)
A
U
(p)
3 , -3 -2 , 2
D
(1 - p)
-1 , 1 0 , 0
Game Y - Player A’s strategy
• EUR:
• Some % of time (p) gets B utility 2
• Rest of the time (1 - p) gets B utility 0
• EUR = (p)*(2) + (1 - p)*(0)
• EUR = 2p + 0 - 0p
• EUR = 2p
B
L (q) R (1 - q)
A
U
(p)
3 , -3 -2 , 2
D
(1 - p)
-1 , 1 0 , 0
Player A’s strategy – making B indifferent
Comparison of EUL with EUR
• EUL = 1 - 4p
• EUR = 2p
• EUL = EUR
• 1 - 4p = 2p +4p
• 1 = 6p /6
• p = 1/6
• 1 - p = 1 - 1/6 = 5/6
• We’ve found the ideal mixed
strategy for Player A
• If Player A plays Up 1/6 of time
and Down 5/6 of time, Player B
is indifferent to choosing Left or
Right
• We need to do the same for
player B
Game Y
B
L (q) R (1 - q)
A
U 3 , -3 -2 , 2
D -1 , 1 0 , 0
Game Y - Player B’s strategy
• EUU:
• Some % of time (q) gets A utility 3
• Rest of the time (1 - q) gets A utility -2
• EUU = (q)*(3) + (1 - q)*(-2)
• EUU = 3q - 2 + 2q
• EUU = 5q - 2
B
L (q) R (1 - q)
A
U
(p)
3 , -3 -2 , 2
D
(1 - p)
-1 , 1 0 , 0
Game Y - Player B’s strategy
• EUD:
• Some % of time (q) gets A utility -1
• Rest of the time (1 - q) gets A utility 0
• EUD = (q)*(-1) + (1 - q)*(0)
• EUD = -1q + 0 - 0q
• EUD = -q
B
L (q) R (1 - q)
A
U
(p)
3 , -3 -2 , 2
D
(1 - p)
-1 , 1 0 , 0
Player B’s strategy – making A indifferent
Comparison of EUU with EUD
• EUU = 5q - 2
• EUD = -q
• EUU = EUD
• 5q - 2 = -q -5q
• -2 = -6q /-6
• q = 1/3
• 1 - q = 1 - 1/3 = 2/3
• We’ve found the ideal mixed
strategy for Player B
• If Player B plays Left 1/3 of time
and Down 2/3 of time, Player A
is indifferent to choosing Up or
Down
Mixed strategy NE
( 1/6 U , 1/3 L )
Game Y - MSNE
B
L (1/3) R (2/3)
A
U
(1/6)
3 , -3 -2 , 2
D
(5/6)
-1 , 1 0 , 0
Battle of sexes
• Want to go out together but have no means of communication
• Have 2 choices – ballet or car show
• Player A prefers car show (C)
• Player B prefers ballet (B)
• Both prefer being together than being alone (A)
• Preferences for player A: C > B > A
• Preferences for player B: B > C > A
Battle of sexes
B
b c
A
B 1 , 2 0 , 0
C 0 , 0 2 , 1
B
b c
A
B 1 , 2 0 , 0
C 0 , 0 2 , 1
Battle of sexes – PS Nash equilibriums
Equilibriums
• 2 pure-strategies equilibriums
• How would they coordinate?
• Apart from pure strategies equilibriums there is one mixed strategy
equilibrium for this game
• ( 1/3 B, 2/3 b )
B
b 2/3 c 1/3
A
B
1/3
1 , 2 0 , 0
C
2/3
0 , 0 2 , 1
Battle of sexes – mixed strategy equilibrium
Calculation of MS NE payoffs
Battle of sexes – mixed-strategy NE payoffs
B
b 2/3 c 1/3
A
B
1/3
1 , 2
1/3 * 2/3
0 , 0
1/3 * 1/3
C
2/3
0 , 0
2/3 * 2/3
2 , 1
2/3 * 1/3
Battle of sexes – mixed-strategy NE payoffs
B
b 2/3 c 1/3
A
B
1/3
1 , 2
2/9
0 , 0
1/9
C
2/3
0 , 0
4/9
2 , 1
2/9
BoS – Payoffs for player A
• We simply multiply payoffs for player A and probabilities for each
outcome and then sum them together
• Player A’s payoffs:
• u(B, b) = 1 * 2/9 = 2/9
• u(B, c) = 0 * 1/9 = 0
• u(C, b) = 0 * 4/9 = 0
• u(C, c) = 2 * 2/9 = 4/9
• EU(A) = 2/9 + 0 + 0 + 4/9
• EU(A) = 6/9
• EU(A) = 2/3
B
b 2/3 c 1/3
A
B
1/3
1 , 2
2/9
0 , 0
1/9
C
2/3
0 , 0
4/9
2 , 1
2/9
BoS – Payoffs for player B
• We simply multiply payoffs of player B and probabilities for each
outcome and then sum them together
• Player A’s payoffs:
• u(B, b) = 2 * 2/9 = 4/9
• u(B, c) = 0 * 1/9 = 0
• u(C, b) = 0 * 4/9 = 0
• u(C, c) = 1 * 2/9 = 2/9
• EU(B) = 4/9 + 0 + 0 + 2/9
• EU(B) = 6/9
• EU(B) = 2/3
B
b 2/3 c 1/3
A
B
1/3
1 , 2
2/9
0 , 0
1/9
C
2/3
0 , 0
4/9
2 , 1
2/9
Battle of sexes NE
• Pure strategies NE
• ( B , b )
• EU(A) = 1
• EU(B) = 2
• ( C , c )
• EU(A) = 2
• EU(B) = 1
• Mixed strategies NE
• ( 1/3 B , 2/3 b )
• EU(A) = 2/3
• EU(B) = 2/3
B
b c
A
B 1 , 2 0 , 0
C 0 , 0 2 , 1
FSS entrance game
• Two students meet at the main faculty entrance
• Both simultaneously decide whether to walk or stop
• If both walk, they collide and both get a bruise (payoff -5)
• If one stops and other walks
• Student who stopped gets good karma for letting the other pass with payoff
1, but at the same time gets delayed, which is completely offsetting the
value of the good karma
• Student who walked gets to pass quickly and thus gets payoff 1
• If both stop, each would get good karma for letting the other pass,
but botch will get delayed
B
W s
A
W -5 , -5 1 , 0
S 0 , 1 0 , 0
FSS entrance game
B
w
1/6
s
5/6
A
W
1/6
-5 , -5 1 , 0
S
5/6
0 , 1 0 , 0
FSS entrance game NE
Stag hunt
B
s r
A
S 5 , 5 0 , 3
R 3 , 0 3 , 3
Stag hunt NE
• Pure strategies NE
• ( S , s )
• EU(A) = 5
• EU(B) = 5
• ( R , r )
• EU(A) = 3
• EU(B) = 3
• Mixed strategies NE
• ( 3/5 S , 3/5 s )
• EU(A) = 3
• EU(B) = 3
B
s R
A
S 5 , 5 0 , 3
R 3 , 0 3 , 3
Prisoners’ dilemma
B
c d
A
C 5 , 5 0 , 7
D 7 , 0 3 , 3
Prisoners’ dilemma NE
• Pure strategies NE
• ( D , d )
• EU(A) = 3
• EU(B) = 3
• Mixed strategies NE
• None
B
c d
A
C 5 , 5 0 , 7
D 7 , 0 3 , 3