Universidad Carlos III de Madrid
GAME THEORY
Exercises on dynamic games
1. Consider the game in transparency 11 in “Dynamic Games 3. Credibility”, where the
four-period centipede game is illustrated, and that we reproduce here for convenience.
1 p 2 p 1 p 2 s
32,32
t t t t
1,0 0,4 16,0 0,64
(a) How many strategies does each player have?
(b) How many subgames are there? Identify them.
(c) Find the set of all strategies for each player.
(d) What strategy profiles result in the payoffs (16, 0)?
(e) Calculate the backward induction equilibria.
2. Consider the game in transparency 19 from “Dynamic Games 3. Credibility”, which
illustrates the extensive form of the example of strategy elimination, and that we
reproduce here for convenience.
Hernán Cortés.1
Do not scuttle the ships Scuttle the ships
Moctezuma.1 Moctezuma.2
Hostile Hostile No hostile
No hostile
Hernán Cortés.2 Hernán Cortés.3
-10 -10
Fight Flee Fight 10
10
-15 0 -15
-15 0 -15
(a) How many strategies does each player have?
(b) How many subgames are there? Identify them.
(c) Find the set of all strategies for each player.
(d) What strategy profiles result in the payoffs (0, 0)?
(e) Calculate the backward induction equilibria.
3. In Freedonia, a typical consumer values her health at 100. There is ¼ probability that
her health deteriorates to a value level of 0. Thus, at the present time, her expected
health value is 75. She can buy full insurance at the price of 20, which means that the
policy will cover all the costs to recover her health completely. The government is
considering offering help to individuals in need, but this is a basic service that will
recover the consumer’s health only to a level of 40. The government’s service will be
offered for free to the consumer, but it has an estimated cost of 5 per consumer for the
government. The government’s goal is to maximize the health of the typical consumer
minus the cost to the government. If the consumer does not buy private insurance, she
will make use of the government service if necessary. The government chooses first
whether to go ahead with the health service or not. Then, the consumer chooses whether
to buy private insurance after observing the government’s choice.
(a) Draw the extensive form of the game. Remember to carefully label all nodes and
actions.
(b) Find the subgame perfect Nash equilibria.
(c) Find the associated normal form and the Nash equilibria. Compare with (b).
4. Repeat Problem 3 for the case where the consumer chooses first. Compare the
equilibria between the two problems.
5. Merche and Antonio have to decide where to go on vacation. They have three
options: Alicante (A), Barcelona (B) and Córdoba (C), but they do not reach an
agreement where to go. In order to decide, they use the following mechanism. First,
Merche vetoes one of the three places. Then, Antonio, after observing Merche’s veto,
vetoes another place. They go to the place that has not been vetoed. Merche prefers A to
B and B to C, while Antonio prefers C to B and B to A. Assuming that each player
assigns a utility of 3 to the favored place, a utility of 2 to the second best alternative and
an utility of 1 to remaining city, and that both players want to go together on vacation,
answer to the following questions:
(a) Represent the game in extensive and normal form.
(b) Find the Nash equilibrium/a in pure strategies.
(c) Which of the Nash equilibria previously found are subgame perfect Nash
equilibria? Explain your answer. Where do Merche and Antonio go on vacation?
6. Consider the game in transparency 15 from “Dynamic Games 3. Credibility”, which
illustrates the extensive form of the example of a “costly commitment”, and that we
reproduce here for convenience.
1.1
𝐼=3 𝐼=0
1.2 1.3
E NE E NE
2.1 2.2
E NE E NE E NE E NE
-2 3 -3 -3 -2 3 0 0
-2 0 3 0 -2 0 3 0
(a) How many information sets does each player have? Find them.
(b) How many strategies does each player have? List them.
(c) How many subgames are there? Identify them.
(d) Find the sugbame perfect Nash equilibria.
7. Among the many adventures that Odysseus (Ulysses) endured during the ten years
that took him to sail back to Ithaca after the Trojan War, his encounter with the sirens
stands out (Homer, 8th century B.C.). Circe, a goddess seeking to protect Odysseus,
warns him that he will be passing near the place inhabited by the Sirens, monsters that
pretend to be beautiful women, and whose beguiling songs lure any man into jumping
overboard to be killed by them. Odysseus wants to sail towards this place to hear the
songs, but not to throw himself into the sea. He is also aware that his mad self would be
willing to do just that.
(a) Represent this episode as a game between Odysseus-sane and Odysseus-insane.
Use numbers -1,0 and 1 for payoffs after the outcomes. Note: If Odysseus does
not listen to the Sirens, you may assume that the hypothetical payoffs for
Odysseus-insane are the same as for Odysseus-sane.
(b) Find the subgame perfect Nash equilibria.
Knowing the above, Odysseus is still considering to listen to the Sirens. To this end he
orders his men to tie him to the mast and put wax in their ears. Now he cannot jump
over the board.
(c) Draw the game after being tied to the mast.
(d) Draw the subgame perfect Nash equilibria.
(e) Draw the whole game, that includes the decision to be tied to the mast or not,
and find the subgame perfect Nash equilibria.
8. Anna and Bob want to meet next Saturday. They can either meet in a park, or in a
coffee shop. Anna loves nature, while Bob prefers coffee. Anna receives a payoff of 3 if
they meet in a park, and 1 if they meet in a coffee shop. Bob receives a payoff of 3 if
they meet in a coffee shop, and 1 if they meet in a park. If they end up in different
places, each receives a payoff of zero. At the beginning of the game, Anna chooses
whether to call Bob to tell him about her plans. If she does, she can choose where to go
(to the park, or to the coffee shop), and Bob chooses where to go (to the park, or to the
coffee shop) after knowing her choice. If she does not call Bob, they choose where to go
simultaneously. If Anna calls Bob, she has to pay an additional cost of 1 (hence, her
payoffs are reduced by 1).
(a) Draw the game tree.
(b) How many subgames does the game have?
(c) How many strategies does each player have?
(d) Find the subgame perfect Nash equilibria in the subgames that begin after each
of Anna’s initial choices (to call Bob, or to not call Bob).
(e) Find all subgame-perfect Nash equilibria of the entire game.
9. Carlos and Natalia face the following situation. Natalia has to choose between two
actions: S to stop playing with Carlos, or C to continue playing with him. In case she
chooses S, she gets a payoff equal to y. In case she chooses C, they will have to play a
simultaneous game where Natalia chooses between U and D while Carlos chooses
between L and R. The payoff matrix for the simultaneous game is:
L R
U 3, 1 2, -1
D 1, 0 4, 5
(a) Find all the Nash equilibria for the simultaneous game that starts after Natalia
chooses C.
(b) Find Natalia’s payoffs in each of the Nash equilibria from part (a).
(c) Find all possible values for y such that Natalia’s first action is always C in all and
each of the subgame perfect Nash equilibria.
(d) List all the subgame perfect Nash equilibria for such values of y.
10. Three countries (A, B and C) must decide whether to declare war on D. If two or
three do, they will win without any problem and will be rid of a common enemy,
something that they each value at 100. Winning the war costs 120, a quantity that will
be divided equally among the countries that declare war. If only one declares war,
nothing will happen.
(a) Find the Nash equilibria in pure strategies if countries decide simultaneously.
(b) Find the subgame perfect Nash equilibria if the decision is sequential, first A,
then B and C, in that order, and if each one knows what the previous country has
decided.
(c) Find the equilibrium paths for each of the subgame perfect Nash equilibria.
11. Two firms compete in prices in a market with the demand detailed below. Firm 1
decides first announcing a price, and then Firm 2 decides on a price also, having
observed Firm 2’s decision. Prices can only be integer numbers between 1 and 10.
Consumers will buy from the firm that puts the lowest price according to the demand. If
both firms put the same price, they will share the market equally. Both firms incur a
unitary production cost of 3.
P 1 2 3 4 5 6 7 8 9 10
Q 90 80 70 60 50 40 30 20 10 0
(a) Find the subgame perfect Nash equilibria. Note: no need to draw the game. For
each of the different prices Firm 1 can set, just find which is the best reply by
Firm 2 and work with that.
A CEO in Firm 1 proposes a new marketing strategy. In addition to putting its price,
Firm 1 will publish a compromise by which it will match the rival’s price in case this
one puts a lower price. According to the country’s law, this kind of public compromise
is binding, so if the firm does not honor its compromise, it will pay a penalty of 100.
The consumers’ association states that this strategy is contrary to competition. The firm
argues that it guarantees a low price and therefore favors competition.
(b) Who is right? To answer this question, find the new subgame perfect Nash
equilibria and compare the result with the subgame perfect Nash equilibria in
(a). Note: as before, no need to draw the game. Just find the new best replies.
12. Two fishing boats work in a lake. Each one of them can be greedy or conscious. If
both are conscious, each can capture fish worth 500. If both are greedy, they will
exhaust the resource and captures will be worth 100 for each ship. If one is greedy and
the other one is conscious, their captures will be worth 600 and 50, respectively. The
decision about how much to fish is done simultaneously and independently.
(a) Find the Nash equilibria. Are they efficient?
Being aware of the bad results in the equilibrium, they resolve to sign a contract
stipulating that the greedy ship will pay a penalty of 300. Thus, in a first moment, the
owners of the ships must simultaneously decide between signing the contract or not. If
they both sign, the contract is valid and can be lawfully enforced. If either of them does
not sign, the contract is not valid and the game will be as in (a).
(b) Find the subgame perfect Nash equilibria in pure strategies.
(c) Repeat the exercise in case they make the decision about signing the contract
sequentially, with the second ship knowing what the first one did.
13. In Problem 17 in static games, consider now that Firm 1 plays first and that, then,
firms 2 and 3 play simultaneously after observing Firm 1’s choice. Find the subgame
perfect Nash in the same both cases as in the original exercise.
14. Suppose that Extra and Ultra are the only car-producers that compete in the Spanish
car market. The demand for cars in Spain is given by 𝑝(𝑄) = 10 − 𝑄, where Q is the
total quantity produced by the two car-producers, Q = 𝑞! +𝑞" . The total costs faced by
Extra and Ultra are given respectively by 𝐶! (𝑞! ) = 3𝑞! and 𝐶" (𝑞" ) = 2𝑞" .
(a) Assume that Extra and Ultra choose simultaneously the quantities that they will
produce, 𝑞! and 𝑞" respectively. Determine the reaction function of each car-
producer and the Nash Equilibrium of this game. Compare the equilibrium profits
of the two car-producers.
(b) Assume now that the game changes. In the new game, Extra chooses its quantity
𝑞! first. Ultra chooses its own quantity 𝑞" after observing the decision of Extra.
Represent this game in extensive form. Find the Subgame Perfect Nash
Equilibrium (SPNE) of this game.
(c) What is the amount of money that Ultra would have to pay to Extra in order to
make Extra agree to choose its quantity simultaneously with Ultra? Is Ultra
willing to pay this amount of money?
15. Two firms, Peurot and Fol, compete in the market for cars, where demand is 𝑃(𝑄) =
2 − 𝑄 and the state of technology is such that marginal cost is 𝑐 = 1. In this market,
Peurot is the leader (chooses first) and Fol is the follower (chooses its quantity knowing
the leader’s chosen quantity). Fol cares not only about its own profit but also the volume
of sales, since it must capture some market share, as long as it does not lose money.
Specifically, the utility function for Fol is given by
𝑈# (𝑞$ , 𝑞# ) = 𝛼Π# (𝑞$ , 𝑞# ) + (1 − 𝛼)𝑞# if Π# (𝑞$ , 𝑞# ) ≥ 0
(and Π# (𝑞$ , 𝑞# ) otherwise)
whereas the leading firm only cares about own profit, i.e.,
𝑈$ (𝑞$ , 𝑞# ) = Π$ (𝑞$ , 𝑞# ).
(a) If 𝛼 > 1/2, calculate the subgame perfect Nash equilibria of this game.
Determine for what values of α the leader produces more than the follower in the
equilibrium.
(b) Now suppose that 𝛼 = 0. Calculate the subgame perfect Nash equilibria.
16. Three neighbors {𝐴, 𝐵, 𝐶 } must agree to repair a common zone. The best budget
implies a cost of 210 and each neighbor values the project at 100.
(a) Assume that each neighbor decides voluntarily how much to pay and that the
decisions are made sequentially (first A decides, then B and, finally, C) so that
when a neighbor makes her decision she is aware of the decisions made by those
before her. The project is undertaken if the voluntary contributions are enough to
pay for the project. Which are the subgame Nash equilibria?
(b) Now assume that the neighbors simply vote either Yes or No. The project goes
ahead only if all say Yes. Also, they know that if they go forth with the project
they will pay the cost in equal shares. Find the subgame perfect Nash equilibria
if the vote is sequential as in (a).
17. In the agenda manipulation game (class notes in the course web page, slide #22 in
Dynamic applications), show which voting ordering the president of the committee will
decide if she wants alternative C to win.
18. In the following bargaining game, a firm (F) and a workers’ union (U) have to share
the benefits generated by their economic activity. Assume that the benefits are equal to 2
million euros. The game has three stages, and the players alternate making offers, starting
with the firm. Once an offer is accepted, the game ends. If the players do not reach any
agreement, after the third proposal, both of them get a zero payoff.
(a) What will be agreement reached in equilibrium and in which time period will the
agreement be reach if the discount factor of both players is 𝛿 = 1⁄4?
(b) What will be agreement reached in equilibrium and in which time period will the
agreement be reach if F has a discount factor 𝛿# = 1⁄4 and S has 𝛿% = 1⁄2?
(c) Compare the two agreements and try to provide an intuitive argument to support
the results you have found.
19. A conservative country has to decide whether or not to pass a legislation to legalize
some social rights. To clarify ideas, think of the decision to be made following
negotiations by the two main groups in the country, the NO group and the YES group.
Say that the NO group feels very strongly about its cause and has preferences
represented by the utility function 𝑢&' (𝑥) = (1 − 𝑥)( , where 𝑥 ∈ [0,1] measures the
permissibility of the legislation (𝑥 = 1 means equal rights for all, 𝑥 = 0 is the status
quo, and intermediate values mean different degrees of equality). The utility of the YES
group is 𝑢)!% (𝑥) = 𝑥. Negotiations are conducted as follows: first, the NO group makes
an offer (a value of 𝑥 ∈ [0,1]), and then the YES group either accepts (A) or rejects (R).
If the offer is accepted, then it becomes the law. If it is rejected there will be social
turmoil and confrontation that will end with an equal probability of victory for either of
the two groups. In this case, the winner imposes its preferred legislation. The NO group
does not care for social confrontation, while the YES group would see its utility reduced
by 𝐶 if it were to happen. Thus, its utility will be 𝑢)!% (𝑥) = 𝑥 if there is no
confrontation, and 𝑢)!% (𝑥) = 𝑥 − 𝐶 if there is.
(a) Draw the extensive form game in the usual way for bargaining problems.
(b) Find the subgame perfect Nash equilibria if 𝐶 = 0.2.
(c) Find the maximum value of 𝐶 for an agreement to be the outcome of a subgame
perfect Nash equilibrium.
20. In the example for the Coase theorem (class notes in the course web page, slides
#12, 13 and 14, Dynamic Negotiation), consider the case where the physician has the
right to ask the baker to leave, but not until they finish the negotiations, that last two
periods of alternating offers, where the baker makes the first offer and the discount
factor for both is 𝛿 = 0.6.
(a) Draw the extensive form game.
(b) Find the subgame perfect Nash equilibria.
Extra Exercises
21. Three neighbors (Ana, Bea, Cruz) have to choose one among three projects (a, b, c).
Preferences are represented in the following table. Each column represents the order of
preferences of the corresponding neighbor, the preferred project being located above in
each column.
Ana Bea Cruz
a b c
b a a
c c b
The choice is realized using a simple majority rule in a two step vote. In the first step,
the neighbors choose between a and b, and the winner of this step competes against c.
From this second step is selected the project that will be implemented.
(a) What would be the result if, in each step, preferences are truly revealed? (i.e.,
they vote for the project they prefer).
We analyze now this election mechanism as a game (the neighbors can vote
strategically)
(b) Assume that a has been chosen in the first step. Explain why the fact that all
neighbors vote for c in the second stage is a Nash equilibrium.
(c) Why isn’t this equilibrium very plausible? Which refinement (or selection
criterion) would eliminate this equilibrium?
(d) Which subgame perfect Nash equilibrium would satisfy this refinement in both
steps?
22. Two partners A and B are trying to finish a project. Each of them will receive 25
million euros when the project is completed, but nothing before its completion. The
project needs 7 millions in order to be complete. None of the partners can commit in a
credible way to pay such a sum in the future, so they decide the following: In a first
stage, Partner A chooses to contribute with 𝑐* . If this quantity is enough to complete the
project, the game is over and each partner receives the 25 millions. In case it is not
enough (𝑐* is less than 7 millions), Partner B chooses its contribution 𝑐+ . If the sum of
both contributions allows completing the project, each of them receives the 25 millions,
if not, they do not receive anything. The only way to get the money and contribute to
the project is to remove it from the other activities of both partners. We assume that
from these activities, each partner can obtain 𝑐,- , (i = A,B).
(a) Find the subgame perfect Nash equilibrium.
(b) Assume now that the sum that is missing in order to complete the project is 12
millions. Find the new subgame perfect Nash equilibrium.
23. Two firms, Peurot and Fol, compete in the market for cars, where demand is
𝑃(𝑄) = 2 − 𝑄 and the state of technology is such that marginal cost is c = 1. In this
market, Peurot is the leader (chooses first) and Fol is the follower (chooses its quantity
knowing the leader’s chosen quantity). Fol cares not only about its own profit but also
the volume of sales, since it must capture some market share. Specifically, the utility
function for Fol is given by
𝑈# (𝑞$ , 𝑞# ) = 𝛼Π# (𝑞$ , 𝑞# ) + (1 − 𝛼)𝑞# ,
whereas the leading firm only cares about own profit, i.e.,
𝑈$ (𝑞$ , 𝑞# ) = Π$ (𝑞$ , 𝑞# ).
(a) If 𝛼 > 1/2, calculate the subgame perfect Nash equilibrium of this game.
Determine for what values of α the leader produces more than the follower in the
subgame perfect Nash equilibrium.
(b) Now suppose that 𝛼 = 0. Calculate the subgame perfect Nash equilibrium.
24. Two firms produce differentiated goods, for example, Dell and Acer. Each of them
chooses its price in order to maximize its own profits. Let 𝑝. be the price of Firm 1 and
𝑝- be the price of Firm 2. Given prices 𝑝. and 𝑝- , Firm 1 will be able to sell 𝑞. =
100 − 𝑝. + 0,5𝑝- and Firm 2 will be able to sell 𝑞- = 100 − 𝑝- + 0,5𝑝. . Both firms
have marginal costs of 50.
(a) Suppose the two firms move simultaneously. Find their best response functions.
Find out the Nash equilibrium of this game. Also find each firm’s profits at the
equilibrium prices.
(b) Suppose now Firm 1 moves first, and Firm 2 observes Firm 1’s choice of 𝑝.
before choosing 𝑝- . Find the prices, quantities and profits in the subgame perfect
Nash equilibrium.
(c) Is there an advantage of moving first in this game?
25. Ester and Fernando play a game where each of them has to choose a number from
the interval [0, 1]. First Ester writes a number x, x ∈ [0, 1]. Then, after observing x,
Fernando chooses a number y, y ∈ [0, 1]. Ester’s and Fernando’s utility functions are
𝑈! (𝑥, 𝑦) = min (𝑥, 𝑦) and 𝑈# (𝑥, 𝑦) = (2𝑥 − 𝑦)- respectively.
(a) Represent this game in the extensive form, indicating if it is a perfect or
imperfect information game, how many information sets each player has, and
how many subgames the game has.
(a) What are Fernando’s best responses for each of the following Ester’s choices:
𝑥 = 0, 𝑥 = 1/4, 𝑥 = 1/2 and 𝑥 = 1?
(b) Find the subgame perfect Nash equilibrium for the game. Suppose that, in case
of being indifferent between two numbers, Fernando always chooses the greater
one.
(c) Find the utilities obtained by Ester and Fernando in the subgame perfect Nash
equilibrium.
26. Consider the following game, where Jorge chooses between the actions A and B,
while Alicia chooses between C and D:
C D
A 2, 1 0, 0
B 0, 0 1, 2
(a) Find all the Nash equilibria in pure and mixed strategies for this game. Indicate
the utility each of the players gets in each of the equilibria.
(b) Suppose now that Jorge and Alicia choose their actions sequentially, with Jorge
choosing first, and Alicia being able to observe Jorge’s action before choosing
her own action. Find ALL the subgame perfect Nash equilibria for this new
game. How much gets each of the players in these equilibria?
27. Consider a firm (F) that selects the number of workers 𝐿 ≥ 0 and a union (U) that
fixes wages, 𝑤 ≥ 0. Firm’s profits are given by Π! (𝑤, 𝐿) = 100𝐿 − 0,1𝐿- − 𝑤𝐿
whereas union’s payoff is given by total wage, Π% (𝑤, 𝐿) = 𝑤𝐿. Suppose that the union
chooses first the wage w, and the firm observes w and then chooses labor input L.
(a) Draw the extensive form of the game and find the subgame perfect equilibrium.
(b) Suppose that the union is worried about reaching an employment level of X at
least, so that its payoff function is now
Π% (𝑤, 𝐿) = (𝐿 − 𝐸)𝑤
Draw the extensive form of the game and find the subgame perfect equilibrium,
as a function of E.
28. Consider the following effort-negotiation game between two partners in a joint
project X. In a first stage partners 1 and 2 must choose simultaneously the effort level,
𝑒, ∈ [0,∞) for i = 1, 2, to exert in the joint project X. Gains from project X are:
Π(𝑒. , 𝑒- ) = 𝑒. + 𝑒- + 𝑒. 𝑒- .
The cost of exerting effort is given by
.
𝐶(𝑒, ) = - 𝑒,- , for 𝑖 = 1,2.
In a second stage, once 𝑒. and 𝑒- have been chosen, the two partners agree to share
those gains as follows. They flip a coin and if the result is heads Partner 1 proposes a
division of the gains between him and Partner 2. The latter must decide whether to
accept or reject that division. If rejected, the game ends and both partners earn zero. If
tails, the allocation procedure is the same but Partner 2 will be the one proposing the
division of gains. Find all the subgame perfect equilibria of the game. Specify your
results in terms of the strategies of each of the players
29. Consider the following Extensive form game among three players
Game problem 29
(a) If the game is one of perfect information and all players can observe previous
actions of the other players, determine all subgame perfect Nash equilibria in
pure strategies, the equilibrium path and the equilibrium payoffs.
(b) Assume now that Player B cannot observe the actions of A. In this case:
(i) Represent the new game in extensive form.
(ii) Are there pure strategy subgame perfect Nash equilibria?
(c) Suppose now that A’s actions are observable by B and C, but that C cannot
observe the actions of B. In this case:
(i) Represent the new game in extensive form.
(ii) Are there any pure strategy subgame perfect Nash equilibria?
Note: If a player does not participate in a given subgame, his/her payoffs are not
relevant for the calculation of the NE in that subgame
30. Two companies competing in a market are considering the possibility of a mail sale
campaign. The cost of this campaign is 200 euros. If only one company makes the
campaign, it will ensure for itself the sale of 18 units at a price of 30 euros, while if the
two companies do it, everyone would sell 12 units at a price of 15 euros. Both
companies can produce any quantity at zero cost. Suppose that firms, after deciding
whether or not to undertake the mail sale campaign, compete in quantities in a market
whose demand is given by the function 𝑃 = (99 − 𝑉) − 𝑞, where P represents price, V
is the total volume of sales and 𝑞 = 𝑞. + 𝑞- is the total amount sold in this market (net
of mail sales). Consider the sequential game in which the two companies must first
decide simultaneously whether to make the mail sales campaign or not to do it, and,
after knowing the decisions about the campaign, there is Cournot competition.
(a) Draw the extensive form game
(b) Show the information sets for each company. Show also the subsets of this
game.
(c) Compute the Nash equilibria of all subgames.
(d) Find all the SPNE of the game.