Sequential Games in Game Theory
Introduction to Game Theory
For Ansal University PGT students, September 2019
Abhinay Muthoo
University of Warwick
Slides #2: Sequential Games and Applications
Sequential Games
•
Players make choices sequentially - so they decide which action to
take
after
observing the choices made by others.
•
Most real-life games are ones in which players move sequentially
but also at various points in time choose actions simultaneously.
•
The difficulty of making
credible
commitments regarding one’s
future action is a central issue/problem that players face.
10/10/2024
2
Abhinay Muthoo, University of Warwick
.
Entry Deterrence Game
•
Two Players: Incumbent Monopolist (
M
) and a Potential Entrant (
E
)
•
E
has to first decide between staying out of
M
’s market or to enter and
compete with
M
.
•
If
E
stay outs, game ends, and
E
earns a profit of
3
and
M
continues to enjoy
monopoly profits of
10
. [Units can be millions of pounds]
•
But if
E
enters, then
M
has to act and decide between fighting entry or to
acquiesce and share the market. In the former case, the profits to
E
and
M
are respectively,
1
and
2
. In the latter case, when they share the market
equally, each gets the same profit of
5
.
10/10/2024
3
Abhinay Muthoo, University of Warwick
.
Entry Deterrence Game:
The game tree
[S.O. = stay out.]
S.O.
Enter
(3, 10)
Fight Acquiesce
(1, 2) (5, 5)
10/10/2024
4
Abhinay Muthoo, University of Warwick
E
M
.
Entry Deterrence Game:
A Nash Equilibrium
[S.O. = stay out.]
S.O.
Enter
(3, 10)
Fight Acquiesce
(1, 2) (5, 5)
10/10/2024
5
Abhinay Muthoo, University of Warwick
E
M
.
Entry Deterrence Game:
This Nash Equilibrium is
not
plausible - it is based on
M
making a
non-credible
threat, and for
E
to believe it.
[S.O. = stay out.]
S.O.
Enter
(3, 10)
Fight Acquiesce
(1, 2) (5, 5)
10/10/2024
6
Abhinay Muthoo, University of Warwick
E
M
.
Entry Deterrence Game:
A
plausible
Nash Equilibrium – premised on
credible future behaviour
.
[S.O. = stay out.]
S.O.
Enter
(3, 10)
Fight Acquiesce
(1, 2) (5, 5)
10/10/2024
7
Abhinay Muthoo, University of Warwick
E
M
.
Entry Deterrence Game
“Backward Induction” Logic:
Look Forward and Reason Backward
S.O.
Enter
(3, 10)
Fight Acquiesce
(1, 2) (5, 5)
10/10/2024
8
Abhinay Muthoo, University of Warwick
E
M
.
Backward Induction Logic
•
Ensures that
future
actions are
credible
•
Ex-post Optimality
versus
Ex-Ante Optimality
•
Credibility
or otherwise is central notion.
•
A plausible Nash Equilibrium is called a
Subgame Perfect Equilibrium.
10/10/2024
9
Abhinay Muthoo, University of Warwick
.
Ultimatum Game
“Take-it-or-leave-it” Offer
•
A simple (negotiation/bargaining) game over the division of some “surplus”.
•
Two players, Adam and Eve.
•
Eve – the “proposer” - makes an offer to Adam on how to divide £100.
•
Adam - the “responder” – then decides either to accept the offer or to
reject it.
•
Payoffs
: If Adam rejects the offer, then each of them gets nothing (£0). But
if Adam accepts the offer, then a deal is reached, and they respectively get
what was offered and accepted.
10/10/2024
10
Abhinay Muthoo, University of Warwick
.
Ultimatum Game – The Solution
•
Many Nash Equilibria – such as: Eve offers £40 to Adam, keeping £60 for
herself; and
Adam’s strategy is to reject offers that give him less that £40 -
and Eve believes that to be the case.
•
But such a Nash equilibrium is not plausible - it is premised on
an
empty
threat by Adam. It is not Credible. It is not ex-post optimal. Adam would
be willing, ex-post, to accept offers less than £40 than get nothing.
•
Applying Backward Induction logic
, it is clear there is a unique sensible
solution:
Adam’s (ex-post optimal) strategy is to accept (almost) any offer,
and thus, Eve –
anticipating that
- offers Adam a tiny amount (say £5) and
keeps the lion’s share (£95) for herself.
10/10/2024
11
Abhinay Muthoo, University of Warwick
.
Repeated Games – Main Ideas
•
Repeated Interaction.
•
Main aim: Explore when and if players can cooperate for mutually benefit
across time -
intertemporal cooperation
.
•
Central Idea:
”Carrots and Sticks”
- Attempt to cooperate (the “carrot”) with
deviations (cheating) by others from that met with punishment (the “stick”).
•
Dealing with the problem of
short-run temptation to cheat.
•
Key Trade-off: Benefit from cheating
today
versus costs from doing so, which
come from the loss of the benefits from
future
cooperation.
10/10/2024
12
Abhinay Muthoo, University of Warwick
.
Repeated Games - An Example
•
Repeated Prisoners’ Dilemma (PD) game - two players play the PD game
repeatedly.
•
Key Feature
: Each time they play the PD game, they
know the history of
past plays
(except the first time they play as there is no history).
•
Objective for each player: To maximise the present discounted value of their
payoffs.
•
Let each player
discount future payoffs
at some rate, which we denote by
δ
,
which is a number between 0 and 1.
So £1 secured tomorrow is worth £
δ
today – which is less than 1.
•
The more a player cares about
future
payoffs the
higher
is the value of
δ
.
10/10/2024
13
Abhinay Muthoo, University of Warwick
.
Prisoners’ Dilemma
C
= Cooperate
D
= Don’t Cooperate
Bob:
C
D
C
Alice:
D
10/10/2024
14
Abhinay Muthoo, University of Warwick
.
Repeated PD – Sustaining Cooperation
The Grim-Trigger Strategy
•
Eve adopts the
“
grim-trigger
”
strategy:
First time they play the PD game, she chooses
C
(to cooperate).
Thereafter, she plays as follows: Play
C if
both players (Adam and she) played
C
throughout the past. Otherwise, play
D
.
•
Adam also adopts the same grim-trigger strategy.
•
Note therefore that the outcome each time they play will be that both of
them will cooperate, choose
C
, and thus each obtains a payoff of 5 each
time they play
.
10/10/2024
15
Abhinay Muthoo, University of Warwick
10/10/2024
16
Abhinay Muthoo, University of Warwick
10/10/2024
17
Abhinay Muthoo, University of Warwick
Explore the concept of sequential games in game theory through an entry deterrence game involving an incumbent monopolist and a potential entrant. The game tree depicts various outcomes based on choices made by players, leading to discussions on Nash Equilibrium, credible commitments, and backward induction logic. Delve into the dynamics of decision-making in strategic interactions within the framework of game theory.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Introduction to Game Theory For Ansal University PGT students, September 2019 Abhinay Muthoo University of Warwick Slides #2: Sequential Games and Applications
Sequential Games Players make choices sequentially - so they decide which action to take after observing the choices made by others. Most real-life games are ones in which players move sequentially but also at various points in time choose actions simultaneously. The difficulty of making credible commitments regarding one s future action is a central issue/problem that players face. 10/10/2024 Abhinay Muthoo, University of Warwick 2
. Entry Deterrence Game Two Players: Incumbent Monopolist (M) and a Potential Entrant (E) E has to first decide between staying out of M s market or to enter and compete with M. If E stay outs, game ends, and E earns a profit of 3 and M continues to enjoy monopoly profits of 10. [Units can be millions of pounds] But if E enters, then M has to act and decide between fighting entry or to acquiesce and share the market. In the former case, the profits to E and M are respectively, 1 and 2. In the latter case, when they share the market equally, each gets the same profit of 5. 10/10/2024 Abhinay Muthoo, University of Warwick 3
. Entry Deterrence Game: The game tree [S.O. = stay out.] S.O.Enter E (3, 10) Fight Acquiesce M (1, 2) (5, 5) 10/10/2024 Abhinay Muthoo, University of Warwick 4
. Entry Deterrence Game: A Nash Equilibrium [S.O. = stay out.] S.O.Enter E (3, 10) Fight Acquiesce M (1, 2) (5, 5) 10/10/2024 Abhinay Muthoo, University of Warwick 5
. Entry Deterrence Game: This Nash Equilibrium is not plausible - it is based on M making a non-credible threat, and for E to believe it. [S.O. = stay out.] S.O.Enter E M (3, 10) Fight Acquiesce (1, 2) (5, 5) 10/10/2024 Abhinay Muthoo, University of Warwick 6
. Entry Deterrence Game: A plausible Nash Equilibrium premised on credible future behaviour. [S.O. = stay out.] S.O.Enter E (3, 10) Fight Acquiesce M (1, 2) (5, 5) 10/10/2024 Abhinay Muthoo, University of Warwick 7
. Entry Deterrence Game Backward Induction Logic: Look Forward and Reason Backward E S.O.Enter (3, 10) Fight Acquiesce M (1, 2) (5, 5) 10/10/2024 Abhinay Muthoo, University of Warwick 8
. Backward Induction Logic Ensures that future actions are credible Ex-post Optimality versus Ex-Ante Optimality Credibility or otherwise is central notion. A plausible Nash Equilibrium is called a Subgame Perfect Equilibrium. 10/10/2024 Abhinay Muthoo, University of Warwick 9
. Ultimatum Game Take-it-or-leave-it Offer A simple (negotiation/bargaining) game over the division of some surplus . Two players, Adam and Eve. Eve the proposer - makes an offer to Adam on how to divide 100. Adam - the responder then decides either to accept the offer or to reject it. Payoffs: If Adam rejects the offer, then each of them gets nothing ( 0). But if Adam accepts the offer, then a deal is reached, and they respectively get what was offered and accepted. 10/10/2024 Abhinay Muthoo, University of Warwick 10
. Ultimatum Game The Solution Many Nash Equilibria such as: Eve offers 40 to Adam, keeping 60 for herself; and Adam s strategy is to reject offers that give him less that 40 - and Eve believes that to be the case. But such a Nash equilibrium is not plausible - it is premised on an empty threat by Adam. It is not Credible. It is not ex-post optimal. Adam would be willing, ex-post, to accept offers less than 40 than get nothing. Applying Backward Induction logic, it is clear there is a unique sensible solution: Adam s (ex-post optimal) strategy is to accept (almost) any offer, and thus, Eve anticipating that - offers Adam a tiny amount (say 5) and keeps the lion s share ( 95) for herself. 10/10/2024 Abhinay Muthoo, University of Warwick 11
. Repeated Games Main Ideas Repeated Interaction. Main aim: Explore when and if players can cooperate for mutually benefit across time - intertemporal cooperation. Central Idea: Carrots and Sticks - Attempt to cooperate (the carrot ) with deviations (cheating) by others from that met with punishment (the stick ). Dealing with the problem of short-run temptation to cheat. Key Trade-off: Benefit from cheating today versus costs from doing so, which come from the loss of the benefits from future cooperation. 10/10/2024 Abhinay Muthoo, University of Warwick 12
. Repeated Games - An Example Repeated Prisoners Dilemma (PD) game - two players play the PD game repeatedly. Key Feature: Each time they play the PD game, they know the history of past plays (except the first time they play as there is no history). Objective for each player: To maximise the present discounted value of their payoffs. Let each player discount future payoffs at some rate, which we denote by , which is a number between 0 and 1. So 1 secured tomorrow is worth today which is less than 1. The more a player cares about future payoffs the higher is the value of . 10/10/2024 Abhinay Muthoo, University of Warwick 13
. Prisoners Dilemma C = Cooperate D= Don t Cooperate Bob: C D 5, 5 0, 8 C Alice: D 8, 0 1, 1 10/10/2024 Abhinay Muthoo, University of Warwick 14
. Repeated PD Sustaining Cooperation The Grim-Trigger Strategy Eve adopts the grim-trigger strategy: First time they play the PD game, she chooses C (to cooperate). Thereafter, she plays as follows: Play C if both players (Adam and she) played C throughout the past. Otherwise, play D. Adam also adopts the same grim-trigger strategy. Note therefore that the outcome each time they play will be that both of them will cooperate, choose C, and thus each obtains a payoff of 5 each time they play. 10/10/2024 Abhinay Muthoo, University of Warwick 15
. Repeated PD Sustaining Cooperation Costs and Benefits of Cheating. Benefit from cheating today the temptation: Getting an 8 rather than a 5. Hence the short-run benefit from cheating is: 8 - 5 = 3. Cost from cheating today are the losses from tomorrow onwards of benefits from cooperation. Hence the long-run cost from cheating is: loss of 5 - 1 = 4 each period from tomorrow onwards. The present discounted value of these losses are: 4 + 4 2 + 4 3 + 4 4 + 4 5+ .. = ? ? Notice that when = 0, these losses are also zero. Indeed, when is small, these losses will be small and close to zero - and so well below 3, which is the temptation from cheating. 10/10/2024 Abhinay Muthoo, University of Warwick 16
. Repeated PD Sustaining Cooperation Incentive-Compatibility Condition for Not Cheating: The Future needs to matter sufficiently Each player will not cheat provided the benefit from cheating is less than or equal to the cost from cheating. That is the following holds: 3 ?? ? ? This will not hold if the discount factor is sufficiently small. This means that when a player does not care much about future payoffs then s/he will cheat and thus cooperation will not be sustained. But if the discount factor is sufficiently large, them the above inequality will hold. This means that when both players care sufficiently about their respective future payoffs, then neither of them has as an incentive to cheat and thus cooperation is sustained. 10/10/2024 Abhinay Muthoo, University of Warwick 17
