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
Y
Pareto efficiency
A
B
P
Y
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 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 – 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
Extensive form games
Extensive form games
• Visualized as a game (decision) tree
• Players move sequentially
• Captures time in game
• Captures knowledge of agents – sometimes agents do not have
information where they are located in game
U
D
d
d
u
u
A
B
B
(2 , 4)
(1 , -5)
(-2 , 6)
(4 , 4)
Basic terminology
• Each square is called node
• Each line represents an action an owner of the node has at his disposal
• Nodes might either trigger other action or end
• Every circle is an end of the tree – it’s called terminal node
• Every circle must yield payoffs for all the actors
• Each moment actor has information about all previous moves called
information set
Backwards induction
U
D
d
d
u
u
A
B
B
(2 , 4)
(1 , -5)
(-2 , 6)
(4 , 4)
Backwards induction
• Moves player make at nodes reached in an equilibrium are called
behavior on the equilibrium path
• Moves player make at nodes that are not reached in an equilibrium
are behavior off the equilibrium path
Backwards induction
• Begin with decisions that lead only to terminal nodes
• Compare payoffs for decisions in each node leading to terminal node
• Find best reply to alternatives of player playing at the current node
• Work through nodes backwards and solve the outcomes of all nodes
comparing payoffs for respective players
U
D
d
d
u
u
A
B
B
(2 , 4)
(1 , -5)
(-2 , 6)
(4 , 4)
U
D
d
d
u
u
A
B
B
(2 , 4)
(1 , -5)
(-2 , 6)
(4 , 4)
U
D
d
d
u
u
A
B
B
(2, 4)
(1 , -5)
(-2 , 6)
(4 , 4)
Equilibrium of sequential game
• One Nash equilibrium in pure strategies on the equilibrium path
• ( U ; u , u )
• There may be more NE in pure strategies
• B decides – if A goes U than u yields better payoff in the upper node,
if A goes D than u yields better payoff in the lower node
• A knows that B will choose u in both nodes, therefore compares
payoffs in u for going U or D – U yields better payoff
Backwards induction
• Works in games of perfect information
• All actors are aware of all previous actions and can also anticipate,
what actors will do based on their expected utilities over outcomes at
subsequent nodes – actors have a perfect recall
• However, backwards induction assesses only rationality on the
equilibrium path. NE found off the equilibrium path will not be
found through backwards induction
U
D
d
u
A
B
(1 , 1)
(-1 , -1)
(2 , 0)
Selten’s game
U
D
d
u
A
B
(1 , 1)
(-1 , -1)
(2 , 0)
Selten’s game
U
D
d
u
A
B
(1 , 1)
(-1 , -1)
(2, 0)
Selten’s game
Rewrite Selten’s game into matrix
• Player A has 2 moves
• U, D
• Represented as 2 rows in a matrix
• Player B has also 2 moves
• u, d
• Represented as 2 columns in a matrix
• We have 2x2 game in normal form
U
D
d
u
A
B
(1 , 1)
(-1 , -1)
(2 , 0)
Selten’s game
B
u d
A
U
D
Strategic form of Selten’s game
U
D
d
u
A
B
(1 , 1)
(-1 , -1)
(2 , 0)
Selten’s game
B
u d
A
U
D -1 , -1 2 , 0
Strategic form of Selten’s game
U
D
d
u
A
B
(1 , 1)
(-1 , -1)
(2 , 0)
Selten’s game
B
u d
A
U 1 , 1
D -1 , -1 2 , 0
Strategic form of Selten’s game
B
u d
A
U 1 , 1 1 , 1
D -1 , -1 2 , 0
Strategic form of Selten’s game
Rewriting extensive form into normal form
• If we rewrite extensive form game into normal form, only one matrix
will emerge as a representation
• This does not work the other way around
• Since matrixes do not hold information about sequence of actions,
one normal-form game might have multiple extensive-form
representations that would completely alter outcomes of the game
Selten’s game from matrix
U
D
d
d
u
u
A
B
(1 , 1)
(1 , 1)
(-1 , -1)
(2 , 0)
Selten’s game from matrix
u
d
D
D
U
U
B
A
(1 , 1)
(1 , 1)
(-1 , -1)
(0 , 2)
B
u d
A
U 1 , 1 1 , 1
D -1 , -1 2 , 0
Selten’s game – Nash equilibrium
B
u d
A
U 1, 1 1 , 1
D -1 , -1 2, 0
Selten’s game – Nash equilibrium
B
u d
A
U 1, 1 1 , 1
D -1 , -1 2, 0
Selten’s game – Nash equilibrium
U
D
d
u
A
B
(1 , 1)
(-1 , -1)
(2, 0)
Selten’s game
NE off the equilibrium path
• This game has another NE which is represented by action U which is
not revealed in extensive form
• This equilibrium (U, u) is called a non-credible threat
• B is willing to get its largest payoff, which will result from A playing U
(deciding not to play the game)
• B can change its payoff from A’s decision about U and D only by threatening
that it will play u if A plays D
• But B will never play u, since it brings lower payoff than playing d
U
D
d
u
A
B
(1 , 1)
(-1 , -1)
(2 , 0)
Selten’s game and non-credible threat