ECO326 Advanced Economic Theory: Game Theory

Winter 2020

Contact information

	Name	Lecture	Office hours	Contact
Instructor	Marcin Pęski	Monday, 10-12pm, SS1085	Tuesday 9.15-11.10 am (priority 9.15-10.10 am), Max Gluskin 207	mpeski@gmail.com
TA	David Walker-Jones	Tutorial: Monday 12-1pm, SS1085	Thursday 4-5 pm, GE 313

Extra office hours: TA will have additional office hours in the week before midterm and the final exam. The time and date will be announced later.

Course information

Here you can find the syllabus.

The required text is Martin J. Osborne, An introduction to game theory (Oxford University Press, New York, 2004). The (tentative) course schedule and the assigned readings (from the book) are listed below.

Date	Topic	Readings	Theory topics	Important games/Extras
06-01	Lecture 1. Games. Dominant strategies↓	1,2.1-2.5, 2.9	Key problem of game theory. Definition of a game. Examples. Strictly (weakly) dominated strategies (SD). Dominant strategies.	Plurality voting↓.
13-01	Lecture 2. Iterated elimination and rationalizability↓	12.2-4* (see comment below)	Rationality, knowledge of rationality. Iterated elimination of strictly dominated strategies (IESD). Best responses. Best responses against beliefs. Relation between dominated strategies and never best responses.	Bubble game↓. Hotelling model of politics↓.
20-01	Lecture 3. Nash equilibrium↓	2.6-2.8, 3.1	Nash equilibrium. Relation between Nash equilibrium and SD or IESD. Multiplicity of Nash equilibria. Equilibrium selection.	Cournot duopoly. IESD in Cournot duopoly↓
27-01	Lecture 4. Nash equilibrium – examples↓	3.2, 3.5		Cournot oligopoly. Cournot duopoly with fixed costs↓. Bertrand duopoly. Bertrand with differentiated products. First attack↓.
03-02	Lecture 5. Mixed strategies↓	4.1-4.5, 4.9	Mixed strategies. Nash equilibrium in mixed strategies.	Penalty shot. Traffic game.
10-02	Midterm↓. Location: AH400 (the regular hours 10-12pm; AH=Alumni Hall).
24-02	Lecture 6. Extensive form games. Subgame perfection↓	5.1-5.5, 6.1-6.2	Extensive-form game. Strategies. Nash equilibrium. Subgame Perfect equilibrium.
2-03	Lecture 7. Extensive form games – examples↓	7.1-7.2, 7.6-7.7		Ultimatum game. Alternating offer bargaining. Hold-up model. Entry game.
9-03	Lecture 8. Repeated games↓	14.1-14.2, 14.4-14.6, 14.7.1., 14.10.1	Repeated games.	Prisoner’s Dilemma followed by Coordinated Investment. Finitely repeated Prisoner’s Dilemma.
16-03	Lecture 9. Games with incomplete information↓, Infinitely repeated games Lecture notes: Infinitely repeated games Lecture (voice):Infinitely repeated games, part II Games with incomplete information I Lecture notes:Games with incomplete information, part I Lecture (voice):Games with incomplete information, part I	9.1-9.3	Inifnitely Repared games. Games with incomplete informarion. Bayesian Nash equilibrium	Infinitely repeated Prisoner’s Dilemma.
23-03	Lecture 10. Games with incomplete information II↓, Games with incomplete information II Lecture notes:Games with incomplete information, part II Lecture (voice):Games with incomplete information, part II Games with incomplete information II Lecture notes:Games with incomplete information, part III Lecture (voice):Games with incomplete information, part III	9.4-9.5, 7.6		Battle of Sexes with uncertain preferences. Cournot oligopoly with uncertain costs. Oil auction↓. Firm-labor union bargaining↓
30-03**	Lecture 11. Auctions↓ Games with incomplete information II Lecture notes:Auctions Lecture (voice):Auctions	Auctions, 3.5, 9.6
TBA	Final exam↓			First-, second-price and all-pay auctions.

*In general, I encourage you to do the reading before the lecture. The only exception is the reading assigned for Lecture 2 (and denoted with asterisk) - the material in chapter 12 may be difficult to read before the lecture.

** In the Fall semester, this is an additional lecture scheduled (not on Monday) to make up for Thanksgiving.

Problem sets:

Click on the lecture link to see the problem sets assigned to each lecture.
The solutions to the textbook problems without asterisks can be found online.
The solutions to other problems will be discussed during the tutorial.

Lecture 1. Games. Dominant strategies

Problem set:

Textbook:
1. 6.1 “Alternative representation of preferences”,
2. 16.1 “Working on a joint project”,
3. 17.1 “Games equivalent to the Prisoner’s Dilemma”,
4. 20.1 “Games without conflict”,
5. 47.1 “Strict equilibria and dominated actions” (the first sentence only),
6. 49.1* “Voting between three candidates” (without the last sentence),
7. 49.2* “Approval voting”
Watch this video:
- Describe the game (players, actions, matrix of payoffs). When you describe the payoffs, think about the assumptions you are making (are the payoffs purely monetary or there is something else that may affect players’ utility).
- Are there any strictly and weakly dominated strategies? If yes, find all of them. If no, explain. How do your assumptions from part (a) affect your answer to part (b)?
Consider a version of the voting game from the end of the class. Suppose that there are 100 voters, trying collectively to choose one of the three alternatives, A, B, or C. Each voter submits one vote (A, B, or C) and then the alternative is chosen with the probability proportional to the number of votes. So, if there are 45 votes for A, 55 votes for B and 0 for C, then A is chosen with 45 probability, and B is chosen with 55 probability. Suppose that each voter i has preferences over outcomes represented by utility functions u_i(A), u_i(B), and u_i(C) and that the preferences are strict, i.e., each of these numbers is different. Show that voting for your favorite alternative is a strictly dominant strategy.
There are N individuals and three choices: A, B, and C. The choice is selected through the following voting procedure: Each individual has one vote. The alternative with the smallest number of votes wins. Ties are broken by choosing the alternative with equal probability among all the alternatives with the smallest number of votes.
1. Suppose that individual i has preferences u_i(A) > u_i(B) > u_i(C). Does she have a strictly dominant strategy?
2. Does she have a weakly dominant strategy?
3. Does she have a weakly dominated strategy?

Before the next class: Play this game. Are you smarter than the NYTimes readers?

Solutions↓

Lecture 2. Iterated elimination and rationalizability

Problem set:

Textbook: 387.2 “Finding rationalizable actions”.
Find all actions that survive the iterated elimination of weakly dominated strategies in problems 391.2, 391.3.
(Median voter theorem) In the model of platform (i.e., politician’s location) choice discussed in the class, we assumed that each location contains the same number of voters. This assumption can be easily generalized. Suppose that there are 11 locations as previously, arranged from extreme left 0 to extreme right 10. Each location n contains m_n > 0 voters and the total number of voters is M = m₀ + m₁ + m₂ + … + m₁₀. As in the class, each voter votes for the closest politician and splits the vote in case of tie.
- Suppose that there exists a location n* with the following property. The number of voters in locations n < n* is strictly less than M ⁄ 2 and the number of voters in locations n > n* is strictly less than M ⁄ 2. We say that the location n* is the median of the distribution of voters. (Notice that that is the situation that we saw in the class with n* = 5.) Show that the only action that survives the iterated elimination of strictly dominated strategies is to choose location n*. (Hint: try to describe the payoffs in the table, as we did in the class.)
- It may happen that that there exists a location n* such that the number of voters in locations n≤n* is equal to M ⁄ 2 and the number of voters in locations n > n* is equal to M ⁄ 2. Show that there are exactly two locations that survive the iterated elimination: n* and n* + 1.
In the voting game in the class, we assumed that the players (i.e., politicians) want to maximize their share of votes. Suppose now that instead, the politicians care only about who wins more votes: Each politician i chooses a number n_i = 0, ..., 10, the voters are distributed in locations 0, ...10 and they vote for the closest politician (splitting their vote equally in case of two politicians with equal distance). The payoffs are:
- if politician i wins more votes than the other politician, he receives payoff 1,
- if he wins less votes, he gets 0, and he gets ½ in case of a tie.
  Show that any strategy n_i ≠ 5 is weakly dominated by 5. Show that 5 is the only actions that survive the iterated elimination of weakly dominated strategies.
There are N > 10 people in the class. All players write a number between 0 and 100. The player whose number is closest to the 2/3 of the average number in the class receive payoff 1. If there are ties, all players who are closest to the 2/3 of the average receive the winning payoff 1. All other players receive payoff 0. Find all strategies that survive iterated elimination of weakly and strictly dominated strategies.

Solutions to Lecture 2 problems↓

Lecture 3. Nash equilibrium

In the class, we discussed graphically the IESD in Cournot duopoly↓. I claimed that the set of surviving strategies converges to the unique Nash equilibrium. You can find a formal argument to support this fact under the above link.

Textbook:
1. 37.1 “Finding Nash equilibria using best response functions” ,
2. 38.1 “Constructing best response functions”,
3. 38.2 “Dividing money”,
4. 27.1* “Variant of Prisoner’s Dilemma with altruistic preferences”,
5. 27.2* “Selfish and altruistic social behavior”,
6. 31.1 “Extension of the Stag-Hunt game”,
7. 31.2* “Hawk-Dove”,
8. 42.1* “Finding Nash equilibria using best response functions”,
9. 42.2* “A joint project”,

Lecture 4. Nash equilibrium – examples

In the class, we talked about Cournot duopoly with fixed costs↓. The link contains a more detailed exposition of the topic.

Problem set:

Textbook:
1. 58.1 “Cournot’s duopoly game with linear inverse demand and different unit costs”
2. 59.2* “Cournot’s duopoly game with linear inverse demand and a fixed cost” (notice that the game is symmetric, but for some combination of parameters, it may only have asymmetric equilibria),
3. 63.1 “Interaction among resource users””,
4. 67.1 “Bertrand’s duopoly game with discrete prices”,
5. 68.2 “Bertrand’s duopoly game with different unit costs”,
6. 392.1 “Bertrand’s duopoly game” (rationalizability in Bertrand duopoly).
(Voluntary public good provision) There is a city with N freedom-loving citizens. The citizens believe that any form of the government constitutes an unacceptable oppression. They finance all public jobs by voluntary contribution. In particular, police budget is equal to a sum P = p₁ + … + p_N of voluntary contributions p_i of each of the citizens. Suppose that each hour of police work costs $50 and the total number of hours provided is H = P ⁄ 50. The citizens’ utility from H hours of police work is equal to U(H) = √(20000H)) . Additionally, each citizen i suffers dis-utility − p_i of making her contribution.
1. Describe the above model as a game: what are the players, actions and payoffs?
2. Derive each player’s best response function.
3. Find the Nash equilibrium contribution levels. (Be careful. There are many Nash equilibria, and, in particular, there are many asymmetric equilibria, in spite of the fact that the game is symmetric.) Find the Nash equilibrium number of police work. Compute the utility of each of the citizens.
4. Suppose that instead of voluntary contributions, the citizens decide to finance the public good through revenues from a non-voluntary and equal tax t. The entire tax revenue Nt is used to finance the public good. Each citizen’s utility becomes equal to√(20000*Nt ⁄ 50) . Find the tax level that maximizes the citizen’s utility. Compute the number of hours and the utility of each citizen given that the tax level is chosen optimally.
5. Compare your answers to the last two questions. Can you explain the difference?
(Bertrand with differentiated products and different costs). There are two food trucks i = 1, 2 parked at two ends of St. George St. Both trucks offer the same menu of tasty takeout. Each item on the menu in Truck i is sold at price p_i. The prices are set simultaneously. The production costs in Truck i are equal to c_i ≥ 0. In particular, the prices and the costs are the same for all items, but they may differ between the two trucks. The profits of truck i are equal to
(p_i − c_i)D_i(p_i, p_− i),
where D_i(p_i, p_− i) is the demand for products of truck i and it is equal to
D_i(p_i, p_− i) = ⎧⎪⎨⎪⎩ 0, if p_i ≥ p_− i + 1, (1)/(2)(p_− i − p_i + 1), if p_− i − 1 ≤ p_i ≤ p_− i + 1, 1, if p_i ≤ p_− i − 1.
1. Find the best response function of each truck.
2. Show that there exists values of costs c₁ and c₂ and an equilibrium prices given these costs so that one of trucks does not sell anything.

Solutions to Lecture 4 problems↓

Lecture 5. Mixed strategies

Before the lecture, play Rock-Scissors-Paper on this website. (You may need to allow your browser to install some older version of Flash.)

First, try to play against Veteran without looking at what computer is thinking. How is your score?
If you lose miserably (like me), and you have somewhere a cubic die, use it to randomize your strategy (for example, by playing Rock when the die says 1 or 2, Scissors when it says 3 to 4, etc). Does your score improve?

Problem set:

Textbook:
1. 114.2 “Games with mixed strategy equilibria”,
2. 114.3 “A coordination game”,
3. 114.4 “Swimming with sharks”,
4. 117.2 “Choosing numbers”,
5. 120.2 “Strictly dominating mixed strategices”,
6. 120.3 “Strict domination for mixed strategies”
Find the mixed strategy equilibrium in Rock-Scissors-Paper. Compute the players’ payoff. Compare this payoff with the score you obtained playing the Rock-Scissors-Paper against computer online.
Penalty kick: There are two players, the Kicker and the Goalie. Each player chooses one of three actions (L)eft, (C)enter, and (R)ight. The Kicker’s payoff is equal to the probability of scoring the goal and it depends on the choices of both players as described in the Table below.

Kicker \ Goalie L C R

L 0.6 0.9 0.9

C 1 0.4 1

R 0.9 0.9 0.6

The Goalie’s payoff is equal to the probability of saving the goal and it can be derived from the above table (if probability of scoring is p, then the probability of saving is 1 − p).
- Show that there is no pure strategy Nash equilibrium.
- We will show that there is no mixed strategy equilibrium in which none of the players plays C.
  - Suppose that (α, 0, 1 − α) is a mixed strategy of the Kicker such that she plays L with probability α, R with probability 1- α, and she does not kick C. Find α such that the Goalie is indifferent between playing L and R.
  - Suppose that (β, 0, 1 − β) is a mixed strategy of the Goalie such that she plays L with probability β, R with probability 1 − β, and she does not kick C. Find β such that the Kicker is indifferent between playing L and R.
  - Is (α, 0, 1 − α) and (β, 0, 1 − β) a mixed strategy equilibrium? Why? This example illustrates the importance of the other rule of looking for mixed strategy equilibria that we discussed in the class: the actions that are played with zero probability should not lead to higher payoffs as the actions that are played with positive probability.
- Find a mixed strategy equilibrium in which both players randomize between all three strategies.
- The penalty kick game is a real game that is played in the real world. Because it has important consequences for the parties involved, we should expect that the players want to choose strategies that maximize their payoffs given the behavior of the opponent. But do they really do it? And if so, does it mean that they play Nash Equilibrium?
  It turns out that we can answer these questions (to some degree). The beauty of the penalty kick is that the game is very simple to represent, to analyze, and, in the same time, there are tremendous amounts of data that document how it is played by professionals. We can use the date to test the predictions of our theory. To learn how our theory fares when faced with real data, read this paper. Spoiler alert: the authors cannot reject Nash equilibrium. However, look at the paper to see how exactly they go about it. That is a beautiful scientific paper that is written in a way that is entirely accessible to the students at your level.
Consider the following game:

Pl.1\Pl.2 L C R

U 4,5 -1,2 3,0

M 3,1 2,3 3,6

D 0,4 3,3 4,3

Explain carefully the consequences of the following statements for actions that the player may play:
- Player 1 is rational.
- Player 2 is rational.
- Player 1 is rational and she thinks that player 2 is rational.
- Player 2 is rational and he thinks that player 1 is rational.
- Player 2 is rational and he thinks (a) that player 1 is rational and (b) that player 1 thinks that player 2 is rational.

Solutions to Lecture 5 problems↓

Midterm

Here are links to some of the past midterms:

Lecture 6. Extensive form games. Subgame perfection

Problem set:

Textbook:
1. 156.2* “Examples of extensive games with perfect information”,
2. 161.1* “Strategies in extensive games”,
3. 163.1 “Nash equilibria of extensive games”,
4. 163.2* “Voting by alternating veto”,
5. 164.2 “Subgames”,
6. 168.1 “Checking for subgame perfect equilibria””,
7. 173.2* “Finding subgame perfect equilibrium””,
8. 173.3* “Voting by alternating veto”,
9. 173.4* “Burning a bridge”,
10. 174.1 “Sharing heterogeneous object””,
11. 189.1 “Stackelber’s duopoly with quadratic costs”,
12. 191.1* “Stackelberg’s duopoly with fixed costs”,
There are two players. There are k coins on the table. Players move sequentially with player 1 moving first. Each player chooses to take either one or two coins from the table. The player who takes the last coin wins.
1. Suppose that k = 4. Represent the game in the form of terminal histories and subhistories. Describe all strategies. Describe the matrix of payoffs.
2. Find all Nash equilibria.
3. Find the subgame perfect equilibrium. Which player has a winning strategy?
4. Is there k such that in game with k coins, player 1 has a winning strategy? Is there k such that player 2 has a winning strategy? e. Find backward induction solution to this game for general k

2. Find all Nash equilibria (not just subgame perfect equilibria) in the Stackelberg duopoly game.

Solutions to Lecture 6 problems↓

Lecture 7. Extensive form games – examples

Problem set:

Textbook:
1. 174.2* “An entry game with a financially constrained firm”,
2. 177.1* “Firm-union bargaining”,
3. 177.2* “The rotten kid theorem””,
4. 183.1 “Nash equilibria of the ultimatum game”,
5. 183.2* “Subgame perfect equilibria of the ultimatum game””,
6. 183.3* “Dictator game and impunity game”,
7. 183.4* “Variants of ultimatum game and impunity game with equity-conscious players”,
8. 185.2 “Dividing a cake fairly””,
9. 186.1 “Hold-up game”,
10. 192.1* “Sequential variant of Bertrand’s duopoly game”.
(Ultimatum game with randomly chosen person to make an offer). There are two players dividing 1 dollar in an ultimatum game (as in class). Prior to the game, Nature chooses the player who makes the first (and the only) offer. Player 1 is chosen with probability p and player 2 is chosen with probability 1-p. \begin_inset Separator latexpar\end_inset
1. What is the expected subgame perfect payoff of player 1 if player 1 is chosen?
2. What is the expected subgame perfect payoff of player 1 if player 2 is chosen?
3. What is the expected payoff of player 1?
Sarah and Ann are software developers and they work together on a new idea for an Ipad app. Each of them must decide how much effort to put into developing the idea. The cost of effort e > 0 is equal to c(e) = e² for each one of them. The quality of the idea, and their join profits depend on their join efforts. If Sarah chooses e_S and Ann chooses e_A, then their expected joint profits are equal to p(e_A, e_S) = √(e_S) + √(e_A). After they choose their effort, they enter two rounds of alternating offer bargaining about the profits. Sarah makes the first offer, and if the offer is rejected, Ann makes the offer. If Sarah’s offer is rejected, the joint profits fall to (1)/(2)p(e_A, e_S). If Ann’s offer is rejected, the joint profits fall to 0 and the game ends. (You can think about the situation where any delay in implementing the idea increases the chance that a competitor comes up with a better app and takes away their demand). What are the subgame perfect equilibrium levels of effort?
(Alternating offer bargaining with different discount factors) We consider a modification of the Rubinstein model with different discount factors for two players. Specifically, suppose that the players bargain about the cake of size 1. Assume that players discount future with (possibly different) discount factors and the discount factor of player 1 is equal to δ₁ < 1 and the discount factor of player 2 is equal to δ₂ < 1. \begin_inset Separator latexpar\end_inset
1. Find the unique subgame perfect equilibrium of the ultimatum game in which player 1 makes the first offer.
2. Find the unique subgame perfect equilibrium of the two-period game in which player 2 makes the first offer and if the offer is rejected, player 1 makes the second offer.
3. Find the unique subgame perfect equilibrium of the three-period game in which player 1 makes the first offer.
4. Find the unique subgame perfect equilibrium of the (2k + 1) -period game in which player 1 makes the first offer.

Additional reading on experiments with the ultimatum game: Stakes Matter in Ultimatum Games

Solutions to Lecture 7 problems↓

Lecture 8. Repeated games

Problem set.

Textbook:
1. 210.2 “Extensive form game with simultaneous moves”,
2. 211.1* “Timing claims on investment”,
3. 211.2* “A market game”,
4. 212.1* “Price competition”,
5. 214.1* “Bertrand’s duopoly game with entry”,
6. 234.1* “Nash equilibria of the centipede game””,
7. 426.1 “Subgame perfect equilibrium of finitely repeated Prisoner’s Dilemma”,
8. 428.1 “Strategies in an infinitely repeated Prisoner’s Dilemma”,
9. 429.1 “Grim-trigger strategies in a general Prison’er’s Dilemma”,
10. 430.1* “Limited punishment strategies in an infinitely repeated Prisoner’s Dilemma”,
11. 431.1* “Tit-for-tat in an infinitely repeated Prison’er’s Dilemma”,
12. 431.2 “Nash equilibria of the infinitely repeated Prisoner’s Dilemma”*
Consider twice repeated Prisoner’s Dilemma with payoffs

C D

C ( − 1, − 1) ( − 10, 0)

D (0, − 10) ( − 5, − 5)

Show that the only Nash equilibrium of this game is to play (D, D) in each period. (The exercise asks you to check what happens in all Nash equilibria, not only in the subgame perfect equilibria.)
Consider the following extensive form game. In the first period, players play Prisoner’s Dilemma with payoffs like above. In the second period, players play the following game:

Nice Not nice

Nice (2, 2) (0, − 2)

Not nice ( − 2, 0) ( − 1, − 1)

In other words, players choose whether to be nice or not nice to each other. If player 1 is not nice, then player 2 suffers, but player 1 suffers more (possibly because of shame).
1. Show that the game has a unique subgame perfect equilibrium. What are the actions in the first period?
2. Show that there exists a Nash equilibrium (not necessarily subgame perfect) in which both players stay silent (play C) in the period 1 Prisoner’s Dilemma game. Why this Nash equilibrium is not subgame perfect?

Solutions to Lecture 8 problems↓

Lecture 9. Games with incomplete information

Problem set:

Consider the infinitely repeated game in which in each period, players play the Battle of Sexes:

She\He Opera Stadium

Opera 5,3 0,0

Stadium 0,0 3,5

Assume that the players discount future with discount factor δ such that 0 < δ < 1. Suppose that She is using the following strategy δ:
- alternate between Opera and Stadium, starting with Opera until the first time in which She and He does not meet (or forever if She and He meet in every period),
- if She and He do not meet in some period in the past, play Opera forever.
1. Suppose that He plays Opera forever, no matter what. Describe the outcome (i.e., infinite history) of the game and compute the payoffs of both players.
2. Suppose that He plays the following strategy: - alternate between Opera and Stadium, starting with Opera.
  1. Show that the profile of Her and His strategies is a Nash equilibrium of the infinitely repeated game.
  2. Explain that it is not a subgame perfect equilibrium (identify a subgame and a player whose strategy is not a best response to the strategy of the other player).
  3. Show that strategy of He can be modified so that the profile of strategies is a subgame perfect equilibrium.
Consider a version of Battle of Sexes, in which She has two types (“meet” and “avoid”) and He has three types (“didn’t hear”, “heard M”, and “heard A”). His believes that both of her types have equal probability and She believes that he heard her conversation with probability p such that 0 < p < 1.
1. Show that if p is not too high there exists a pure strategy Bayesian Nash equilibrium in which His type “didn’t hear” goes to the Stadium. What do other types do?
2. What happens when p is high (i.e., close to 1)? Find an equilibrium when p = 0.9.

Solutions to Lecture 9 problems↓

Lecture 10. Games with incomplete information II

Problem set.

Textbook:
1. 227.1 “Variant of ultimatum game with equity-conscious players”,
2. 227.2* ”Firm-union bargaining”,
3. 227.3* “Sequential duel”,
4. 276.1 “Equilibria of a variant of BoS with imperfect information”,
5. 277.1 “Expected payoffs in a variant of BoS with imperfect information”,
6. 282.1* “Fighting an opponent of unknown strategy”,
7. 282.2 “An exchange game”,
8. 282.3* “Adverse selection”,
9. 287.1 “Cournot’s duopoly game with imperfect information”,
10. 288.1 “Cournot’s duopoly game with imperfect information”,
Consider a Cournot model analyzed in the class, but with asymmetric beliefs about the costs. In other words, suppose that firm i’s cost is high with probability π_i, and low with probability 1 − π_i, and that the probabilities π₁ and π₂ are not necessarily equal. We can treat π_i as the belief of firm –i about the costs of firm i.\begin_inset Separator latexpar\end_inset
1. Find the unique Bayesian Nash equilibrium.
2. Compute the equilibrium payoff of firm 1 with cost type c. How does the payoff of each type of firm 1 depend on belief π_i?
Two generals approach the city from two different directions. Each general observes the strength of the city fortifications from his own side. The fortifications are either weak or strong. General i believes that the fortifications on the other side of the city are strong with probability π_i. Each general must make a decision whether to attack the city or not. The generals know that the attack is successful if and only if both generals attack simultaneously and the fortifications are weak. Suppose that the payoff from successful attack is 1. If a general attacks and the attack is not successful, his payoff is equal to -1. If the general does not attack, his payoff is 0.
1. Represent the above situation as a game with incomplete information.
2. Consider a strategy of general 2 in which he attacks if and only if the fortifications are weak. Compute the payoff of different
3. For what values of the parameters does there exist a Bayesian Nash equilibrium in which the two generals never attack?
4. For what values of the parameters does there exist a Bayesian Nash equilibrium in which the two generals attack with positive probability? What is the probability that the attack is successful?
Find all the Bayesian Nash equilibria of the cleaning room game from the class given that pv < v − c.
Find all the Bayesian Nash equilibria of a version of the cleaning room game in which players equally split the cost of cleaning the room if both of them simultaneously decide to clean. (If only one person decides the clean he or she pays full cost c.)
Juliet would like to spend Friday evening with her friends. It is her turn to suggest the place and she can choose between Casino or Boxing Match. Romeo is trying to follow Juliet wherever she goes and tries to impress her with his charms. Juliet finds Romeo creepy and she is worried that Romeo will spoil her evening by showing up in the same place. Juliet payoffs depend on her type: If she feels lucky, she wants to go to the Casino, if not, she prefers the Boxing Match. Additionally, she suffers disutility from meetng Romeo. Her payoffs can be described in the following tables:

If Juliet feels lucky,

Juliet\Romeo Casino Boxing Match

Casino -1 3

Boxing Match 1 -1

,

and if Juliet feels unlucky,

Juliet\Romeo Casino Boxing Match

Casino -1 1

Boxing Match 3 -1

Romeo always feels lucky so he receives payoff 1 from choosing Casino and payoff 0 from choosing Boxing Match. If he meets Juliet, he gets additionally payoff of 2.
1. Suppose that Romeo believes that Juliet feels lucky with probability p ∈ (0, 1). Compute Romeo’s best response if Juliet strategy is to go to Casino whenever she feels lucky and to the Boxing Match otherwise. Does Juliet and Romeo’s strategy form an equilibrium?
2. Suppose that lucky Juliet goes to the Casino with probability α_L ∈ (0, 1), and that that unlucky Juliet always goes to the Boxing Match. What is the expected payoff of Romeo from going to Casino? What is the expected payoff from going to the Boxing Match?
3. For what values p is there a (Bayesian Nash) equilibrium in which Romeo and lucky Juliet randomize and the unlucky Juliet always go to the Boxing Match? What are the strategies of Romeo and Juliet?
4. Suppose that Juliet’s good but talkative friend, Friar, tells Romeo about Juliet’s mood. In particular, Romeo knows whether Juliet feels lucky or unlucky (and because Friar also tells Juliet that he talked to Romeo, Juliet knows that he knows). How does this information affect Juliet’s equilibrium strategies?

Solutions to Lecture 10 problems↓

Lecture 11. Auctions

Problem set:

Textbook: 294.1, 294.2, 296.1

Final exam

Here are links to some of the past final exams:

Solutions

Solutions to Lecture 1 problems

Lecture 1. Games. Dominant strategies↑

Voting game with randomly chosen alternative

In order to show that a strategy is strictly dominant, we need to show that that it leads to the highest payoff regardless what actions are used by other players.

Let us fix a player i and without loss of generality suppose that

(1) u_i(A) > u_i(B) > u_i(C)

We will show that voting for A is a strictly dominant strategy for this player.

Take arbitrary action profile of other players and suppose that there are n_A other players choosing A, n_B other players choosing B, and n_C other players choosing C. Of course, it must be that n_A + n_B + n_C = 99.
The payoff of player i is the expected utility obtained from the alternative chosen by the voting process. We compute the payoff of player i from his strategies. \begin_inset Separator latexpar\end_inset
- the payoff from strategy A is
  (n_A + 1)/(100)u_i(A) + (n_B)/(100)u_i(B) + (n_C)/(100)u_i(C).
  Indeed, notice that if player i votes A, then there are n_A + 1 players voting A, which means that Ais chosen with probability (n_A + 1)/(100),
- the payoff from strategy B is
  (n_A)/(100)u_i(A) + (n_B + 1)/(100)u_i(B) + (n_C)/(100)u_i(C),
- the payoff from strategy C is
  (n_A)/(100)u_i(A) + (n_B)/(100)u_i(B) + (n_C + 1)/(100)u_i(C).
We compare the payoffs between strategies:\begin_inset Separator latexpar\end_inset
- the payoff from strategy A minus the payoff from B is equal to
  (n_A + 1)/(100)u_i(A) + (n_B)/(100)u_i(B) + (n_C)/(100)u_i(C) − ⎛⎝(n_A)/(100)u_i(A) + (n_B + 1)/(100)u_i(B) + (n_C)/(100)u_i(C)⎞⎠ = (1)/(100)(u_i(A) − u_i(B)) > 0.
  The last inequality comes from (1↑). In particular, the payoff from A is strictly higher than the payoff from B.
- Similarly, we show that the payoff from A is strictly higher than the payoff from C.
Thus, the payoff from A is strictly higher than the payoff from B or C no matter what actions are used by the other players. This means that A is strictly dominant.

Voting for the worst alternative

Part 1. No. Below, we will show that i does not have a weakly dominant strategy, which implies that she does not have a strictly dominant strategy.

Part 2. No. First, we will show that voting for C is not weakly dominant. Indeed, suppose that alternatives A and B are tied with respect to the smallest number of votes among all the other players b and there are strictly more votes for C . In such a case, if individual i votes for B, then A becomes the chosen outcome. If i votes for C instead, then the voting rule chooses randomly between A and B. Because the utility from A is strictly higher, i strictly prefers to vote for B.

Second, we will show that voting for B is not weakly dominant. Suppose that B and C are tied with respect to the smallest number of votes among all the other players, and there are strictly more votes for A. Then, voting for B leads to alternative C being chosen; whereas voting for C leads to alternative B. Thus, in such a case, voting for C leads to a strictly higher payoff.

A similar argument shows that voting for A is not weakly dominant.

Part 3. Yes. Voting for A is weakly dominated by voting for C. Indeed, there are some situations (like when A and C are tied with respect to the smallest number of votes) when voting for C leads to strictly higher payoff. On the other hand, in any situation, the only way that voting for C rather than A may change the result is to increase the chance of A vs C or A vs B, or B vs C outcome. In each of the cases, i’s payoff may either get higher or stay unchanged if i’s swicthes her vote from SA to C.

Solutions to Lecture 2 problems

Lecture 2. Iterated elimination and rationalizability↑

Median voter theorem

We only discuss part (a) as the argument in part (b) is similar. The argument is by induction. Take any a, b ∈ {0, 1, ..., 10} such that a < n^* < b^* and suppose that we have already eliminated all the strategies of both players such that s_i < a, and s_i > b. In other words, we consider a game with the strategy space {a, a + 1, ..., b − 1, b} for both players. We can show that in such a game

strategy s_i = a is strictly dominated by a + 1,\begin_inset Separator latexpar\end_inset
1. strategy s_i = b is strictly dominated by b − 1.
We will show only (i) as the argument in case (ii) is similar. We need to show that no matter what is the strategy s_− i of the opponent, the number of votes obtained by playing a is strictly lower than the number of votes obtained if i were to choose location a + 1.
- Suppose that s_− i = a. Then, \begin_inset Separator latexpar\end_inset
  - the number of votes obtained from playing s_i = a is equal to (M)/(2). Indeed, in such a case, both players choose the same location and all voters are indifferent between them.
  - the number of votes received from playing s_i = a + 1 is equal to m_a + 1 + ... + m₁₀ = M − (m₀ + ... + m_a). Indeed, notice that all voters x = 0, ..., a vote for − i, and all other voters x = a + 1, a + 2, ..., 10 vote for i,
  - because a < n^*, the definition of the median voter n^* implies that
    m_a + 1 + ... + m₁₀ > (M)/(2).
    Thus, playing s_i = a + 1 leads to a strictly higher payoff.
- Suppose that s_− i = a + 1. Then, \begin_inset Separator latexpar\end_inset
  - the number of votes obtained from playing s_i = a is equal to m₀ + ... + m_a,
  - the number of votes received from playing s_i = a + 1 is equal to (M)/(2),
  - because a < n^*, the definition of the median voter n^* implies that
    m₀ + ... + m_a < (M)/(2).
    Thus, playing s_i = a + 1 leads to a strictly higher payoff.
- Suppose that s_− i > a + 1. Then, switching from strategy s_i = a to a + 1 allows player i to gain (1)/(2)m_k voters, where k is a location somewhere in the “middler” between a and s_− i. Thus, \begin_inset Separator latexpar\end_inset
  - (More precisely, if s_− i − a is an even number, then k = a + (s_− i − a)/(2). Indeed, in such a case, if player i chooses s_i = a, he receives votes from locations 0, .., k − 1 and half of the votes from location k. If she switches to a + 1, she gains all the remaining votes at location k.
  - If s_− i − a is an odd number, then k = a + (s_− i − a + 1)/(2). Indeed, choosing s_i = a leads to votes from locations 0, ..., k − 1 and nothing else. Switching to a + 1 leads to extra (1)/(2) of the votes from location k.)
- Thus, no matter what the opponent is doing playing a + 1 leads to a strictly higher number of votes than pplaying a. It follows that a is strictly dominated by a + 1.
The induction argument implies that n^* is the only strategy that survives the iterated elimination of strictly dominated strategies.

Platform choice when politicians want to win

We will show that no matter what is the action n_− i of player i, choosing 5 leads to (weakly, and sometimes strictly) higher payoff for player i than choosing n_i ≠ 5.

Suppose that n_− i ≠ 5. Then, if player i chooses n_i = 5, she wins the election. In any other case, she may lose or tie. Thus, i’s payoff is weakly higher if she chooses n_i = 5.
Suppose that n_− i = 5. Then, if player i chooses n_i = 5, she ties and she wins the election with probability (1)/(2). In any other case, she will lose. Thus, i’s payoff is strictly higher if she chooses n_i = 5.

Guess the 2/3 of the average game

As the first step, we will describe all weakly and strictly dominated strategies in a game in which players must choose a number between 0 to m, where m is some number that is equal or less than m ≤ 100. (That means that actions of all players are restricted to 0, 1, ..., m). Let m^*(m) = ⎡⎣(2)/(3)m⎤⎦ be the natural number that is closest to (2)/(3)m. (If there are more than one number like this (i.e. (2)/(3)m = k + (1)/(2) for some natural k), then take m^*(m) = ⎡⎣(2)/(3)m⎤⎦ to be the larger number (i.e., m^*(m) = ⎡⎣(2)/(3)m⎤⎦ = k + 1).

Observe that if m > m^*(m) (this occurs whenever m > 1), then any strategy s = m^*(m) + 1, m^*(m) + 2, ..., m is weakly dominated by m^*(m) in this restriced game. Indeed, because m^* is closer to the (2)/(3) of the average than s, m^* leads to at least as high payoff as s. Moreover, if all the other players play s, then m^* leads to a strictly higher payoff.

In the same time, there are no strictly dominated strategies (make sure that you understand why).

Next, we go back to our original game in whcih players can choose actions from 0 to 100. We describe the outcome of the iterated elimination. Because there are no strictly dominated strategies, the iterated elimination of strictly dominated strategies has no bite. Next, suppose that strategies 0, ..., m survive the iterated elimination of weakly dominated strategies. On the other hand, if m > 1, then m > m^*(m) and strategy m is weakly dominated and it should have been eliminated. Thus, the only strategies that survive the elimination are 0 and 1.

Solutions to Lecture 4 problems

Lecture 4. Nash equilibrium – examples↑

Textbook problem 59.2*

In this problem, firm i’s payoffs are equal to

π_i(q_i, q_− i) = ⎧⎨⎩ q_i(α − c − q_i − q_− i) − f, if q_i = 0, 0, otherwise.

In particular, the payoffs are described by two different functions depending on whether the firm is active (q_i > 0) or inactive (q_i = 0). This complicates somehow the problem of finding equilibria.

In order to simplify the process, we separately analyze three possible types of equilibria, depending on whether the firms are active or not:

Case 1: Both firms are inactive, q^*₁ = q^*₂ = 0. In such a case, the payoff of firm i from quantity q^*_iis equal to 0. On the other hand, if the firm changes its action to q_i > 0, its payoff is going to be equal to
q_i(α − c − q_i) − f.
The above expression is maximized by q^mon_i = (1)/(2)(α − c) (this can be derived from the standard first order conditions - notice that the above function is concave in q_i) [A] [A] Notice that q^mon_i is equal to the optimal monopoly quantity., in which case, the payoff becomes equal to
q^mon_i(α − c − q^mon_i) − f = (1)/(4)(α − c)² − f.
In equilibrium, Thus, there is an equilibrium of Case 1 form (i.e., in which both firms are inactive) if and only if (1)/(4)(α − c)² − f ≤ 0.
Case 2: Only firm i is active, q_i > 0, q_− i = 0. In such a case, the (active) best response of firm i (as calculated above) is q^mon_i = (1)/(2)(α − c). The active quantity is a best response if
q^mon_i(α − c − q^mon_i) − f = (1)/(4)(α − c)² − f ≥ 0.
The inactive payoff of firm − i is equal to 0. If firm − i became active with quantity q₂ > 0, her payoff would be equal to
q₂(α − c − q^mon₁ − q₂) − f = q₂⎛⎝(1)/(2)(α − c) − q₂⎞⎠ − f.
The above expression is maximized at q^Follower_− i = (1)/(4)(α − c) (again, this can be derived from the first order conditions) [B] [B] The name “Follower” will become clear when we start discussing the Stackelberg game.. The maximal payoff from being active is equal to
q^Follower₂⎛⎝(1)/(2)(α − c) − q^Follower₂⎞⎠ − f = (1)/(16)(α − c)² − f.
Thus, the inactive strategy of firm − i is an equillibrium if (1)/(16)(α − c)² − f ≤ 0.
Case 3: both firms are active. As in the standard Cournot duopoly (i.e., case of f = 0), the optimal behavior of both firms can be derived from solving the first order conditions and it is equal to
q^Cournot_i = (1)/(3)(α − c).
The payoffs of both firms are equal to
q^Cournot_i(α − c − q^Cournot_i − q^Cournot_− i) − f = (1)/(9)(α − c)² − f.
The active quantitites are equilibrium if (1)/(9)(α − c)² − f ≥ 0.

Voluntary public good provision

Part (a). There are N players. Actions A_i = {p_i:p_i ≥ 0}. Payoffs

u_i(p_i, p_− i) = ⎛⎝20000(p₁ + … + p_N)/(50)⎞⎠^1 ⁄ 2 = 20√(p₁ + ... + p_N) − p_i.

Part (b). Given the actions p_− i of other players, the first order conditions for the maximum payoff of player i is

20(1)/(2√(p₁ + ... + p_N)) − 1 = 0.

This implies that

p₁ + ... + p_N = 100,

or that

p_i = max(100 − (p₁ − ... − p_i − 1 − p_i + 1 − ...p_N), 0). = max(100 − P_− i, 0).

Here,

P_− i = p₁ − ... − p_i − 1 − p_i + 1 − ...p_N

is the total contribution of all players but i. We use the maximum to take into account that the optimal action p_i = 0 does not need to satisfy the first order conditions if the total contribution of all other players is higher than 100.

Part (c). Any profile of contributions such that

p^*₁ + ... + p^*_N = 100

is a Nash equilibrium. Two examples of Nash equilibria:

Symmetric contributions: everybody contributes (1)/(N)100.
All contributions are made by player i: Player i contributes 100 and nobody else contributes anything.

The Nash equilibrium total contribution is equal to P^* = 100, and the total equilibrium number of police hours is H^* = 100 ⁄ 50 = 2.

Part (d). We maximize

(20000*Nt ⁄ 50)^1 ⁄ 2 − t

with respect to t. The first order conditions are

(20√(N))/(2*√(t^*)) = 1,

which implies that

t^* = 100N.

The total optimum number of police hours is

H^opt = (Nt^*)/(50) = 2N².

There are more police hours if the citizens decide to tax themselves rather than pay police by voluntary contributions. The problem in the latter case is that each contribution benefits the contributor as well as the rest of the society. However, in Nash equilibrium, the citizens choose the contributions to maximize their own private payoffs, the rest of the society be damned. In the taxation case, they realize that raising taxes is one one hand costly for them (more out-of-pocket contributions), but it is also beneficial (because each one of them gets more police hours paid by other people taxes).

Bertrand duoploy with differentiated products and different costs.

Part (a). Notice that the best response cannot be lower than p_− i − 1 because otherwise player i can increase the price to p_− i − 1 and increase her profits. (Notice that such an increase in price does not reduce the demand.)

Moreover, if p_− i > c_i − 1, then the best response cannot be higher than p_− i + 1 because in such a case player i has negative profits and she can have strictly positive profits by setting p_i = p_− i + 1 − ϵ for some small ϵ > 0.

Thus, if p_− i > c_i − 1, then compute

max(p_i − c_i)(p_− i − p_i + 1) st. p_i ≥ p_− i − 1.

The first order conditions imply that that the best response is equal to

p^BR_i(p_− i) = max⎛⎝p_− i − 1, (1)/(2)(1 + p_− i + c_i)⎞⎠.

If p_− i ≤ c_i − 1, then any price p_i ≥ p_− i + 1 is best response (and it leads to 0 profits).

Part (b). Suppose that c₂ > 3 + c₁. Let p^*₁ = c₂ − 1, p^*₂ = c₂. This is an equilibrium given the above characterization of best responses.(We need to check that

p^*₁ − 1 > (1)/(2)(1 + p^*₂ + c₁)

Moreover, truck 2 does not sell anything.

The question does not ask you to show it, but we can verify that the above is a unique equilibrium given that c₂ > 3 + c₁. (How?)

Solutions to Lecture 5 problems

Lecture 5. Mixed strategies↑

Rock-Scissors-Paper

Each player randomizes equally between all actions. The expected payoff is 0.

Penalty kick

Consider the following mixed strategies

Kicker (s) and Goalie (a) L, γ C, 1 − γ − φ R, γ L, α 0.6 0.9 0.9 C, 1 − α − β 1 0.4 1 R, β 0.9 0.9 0.6

We will check α, β, γ, φ so that each player is indifferent between all his actions. The indifference condition for the Goalie implies that

0.6α + 1(1 − α − β) + 0.9β = 0.9α + 0.4(1 − α − β) + 0.9β = 0.9α + 1(1 − α − β) + 0.6β.

The solution is

α = β = (6)/(15).

A similar indifference condition for the Kicker yields

0.6γ + 0.9(1 − γ − φ) + 0.9φ = 1γ + 0.4(1 − γ − φ) + 1φ = 0.9γ + 0.9(1 − γ − φ) + 0.6φ.

The solution is

γ = φ = (1)/(3).

Statements about rationality

Player 1 is rational implies that Player 1 won’t play strictly dominated strategies. Because Player 1 does not have any dominated strategies (make sure that you understand why!), this claim does not have any consequences.
Player 2 is rational implies that Player 2 won’t play strictly dominated strategies. Here, strategy C is strictly dominated by a mixture L^0.5R^0.5. So, the claim implies that player 2 is not going to play strategy C.
Player 1 is rational and she thinks that player 2 is rational implies that player 1 knows that 2 is not going to play C and that 1 is not going to play any dominated strategies in a game in which strategy C is eliminated. Notice that in such a game, strategy M is strictly dominated by the mixture U^4 ⁄ 5D^1 ⁄ 5.
Player 2 is rational and he thinks that player 1 is rational. Because player 1 does not have any strictly dominated strategies, the second part of the claim does not provide any information to player 2. The claim implies that player 2 is not going to play strategy C.
Player 2 is rational and he thinks (a) that player 1 is rational and (b) that player 1 thinks that player 2 is rational. Here, (a) and (b) imply that player 2 thinks that player 1 won’t play strategy M. In a game in which M is eliminated, action L is dominant. Thus, the claim implies that player 2 is going to play L.

Solutions to Lecture 6 problems

Lecture 6. Extensive form games. Subgame perfection↑

Coins

Part (1). Strategies of player 1:

σ₁( Ø) = 1, σ₁(11) = 1- meaning, take 1 coin initially and then take 1 coin after history in which player 1 takes one coin, followed by player 2 taking 1 coin.
σ₁( Ø) = 1, σ₁(11) = 2
σ₁( Ø) = 2, σ₁(11) = 1
σ₁( Ø) = 2, σ₁(11) = 2

Strategies of player 2:

σ₂(1) = 1, σ₂(2) = 1,
σ₂(1) = 1, σ₂(2) = 2,
σ₂(1) = 2, σ₂(2) = 1,
σ₂(1) = 2, σ₂(2) = 2,

Part (2). Strategy σ₁( Ø) = 1, σ₁(11) = 2 of player 1 ensures that she wins (no matter what is the strategy of player 2). It follows that in any Nash equilibrium, player 1 must win (otherwise he would prefer to play this strategy). Because this is also the only strategy that ensures player 1’s victory, it is the only strategy of player 1 that can be played in Nash equilibrium.

Any strategy of player 2 is a best response to the above strategy. Hence, any player 2 strategy can be played in Nash equilibrium.

Part (3) Strategy σ₁( Ø) = 1, σ₁(11) = 2 for player 1 and any of the following two strategies of player 2 constitute the subgame perfect equilibrium:

σ₂(1) = 1, σ₂(2) = 2,
σ₂(1) = 2, σ₂(2) = 2.

Notice that the other strategies of player 2 are not best responses in the subgame after history in whihc player 1 initially takes 2 coins, hence they cannot be played in subgame perfect equilibrium. (As you can see in the answer to question (b), they can be played in Nash equilibrium.

Player 1 has a winnning strategy.

Part (4). Player 2 has a winning strategy if k = 3n for some n (the strategy is to take 1 coin if player took 2 coins in the previous period and 2 coins otherwise). Player 1 has a winning strategy for any other k.

Stackelberg duopoly

We will show that any quantity 0 < q^*₁ < α − c can be played player 1 in some Nash equilibrium. Indeed, consider strategy q^*₁for player 1 and strategy

q^*₂(q₁) = ⎧⎨⎩ (α − c − q^*₁)/(2) if q₁ = q^*₁ α − c otherwise

Then, strategy profile (q^*₁, q^*₂(.)) is a Nash equilibrium.

We check that player 1 is best responding. If player 1 chooses q^*₁, he receives payoff
⎛⎝α − c − q^*₁ − (α − c − q^*₁)/(2)⎞⎠q^*₁ = ⎛⎝(α − c − q^*₁)/(2)⎞⎠q^*₁ > 0.
If he chooses any other quantity q₁ ≥ 0, he gets \strikeout off\uuline off\uwave off
(α − c − q₁ − (α − c))q₁ = ( − q₁)q₁ ≤ 0.
We check that player 2 is best responding. Indeed, if player 1 chooses quantity q^*₁, then (α − c − q^*₁)/(2) is player 2’s best response

Notice that the above strategy profile is not subgame perfect.

Solutions to Lecture 7 problems

Lecture 7. Extensive form games – examples↑

Ultimatum game with randomly chosen offerent

Part (1). 1.

Part (2). 0.

Part (3). p.

Sarah and Ann

In the second stage of the bargaining, Ann offer 0 to Sarah and (1)/(2)p(e_A, e_S) to herself and the offer is accepted. Anticipating that, in the first stage of bargaining, Sarah proposes to split the profits equally and the offer is accepted. Thus, the payoff of player i = A, S is equal to

(1)/(2)(√(e_i) + √(e_− i)) − e²_i.

The best response level of effort maximizes the above expression. By taking the first order conditions, we find that

(1)/(4√(e_i)) − 2e_i = 0,

which implies that e^*_i = (1)/(4). Thus, profile ⎛⎝(1)/(4), (1)/(4)⎞⎠of Sarah’s and Ann’s choices of effort followed by the bargaining strategies described above is the unique subgame perfect equilibrium.

Alternating offer bargaining with different discount factors\

Part (1). (1, 0).

Part (2). (δ₁, 1 − δ₁)

Part (3). (1 − δ₂(1 − δ₁), δ₂(1 − δ₁)).

Part (4). Player 1 offers 1 − δ₂ + δ₁δ₂ − δ₁δ²₂ + δ²₁δ²₂ − ... + δ^k₁δ^k₂ for himself and δ₂ − δ₁δ₂ + δ₁δ²₂ − δ²₁δ²₂ + ... − δ^k₁δ^k₂ for player 2 and the offer is accepted.

Solutions to Lecture 8 problems

Lecture 8. Repeated games↑

Twice repeated Prisoner’s Dilemma

There is a Nash equilibrium in which both players play D in each period, after each history.

We show that there is no other Nash equilibrium. Suppose that (σ₁, σ₂) is a Nash equilibrium, and let a_i = σ_i(Ø) be the first period action played by player i. Then, because (σ₁, σ₂) is Nash equilibrium, and (a₁, a₂) is a history that will happen in this equilibrium, it must be that the second period strategies after history (a₁, a₂) prescribe the unique equilibrium of the second period game, (D, D). (Remember that the Nash equilibrium strategies must be best responses in each subgame that is reached in equilibrium.) Thus, each player gets -5 payoff in the second period game.

Assume now that, contrary to our claim, a_i = C. Consider a strategy σ_i’ such that player i plays D in period 1 and in period 2 after each history. Strategy σ_i’ ensures payoff of -5 in the second period. Moreover, it leads to a payoff of at least 1 more than the payoff from strategy σ_i in the first period. Thus, it is profitable deviation. It follows that if (σ₁, σ₂) is a Nash equilibrium, then σ_i(Ø) = D for each player i.

Prisoner’s Dilemma followed by Nice-NotNice game.

Part (1). (Nice, Nice) is the only equilibrium of the second period subgame. Thus, each player players Nice after any 1st period history. Because the second period strategies do not depend on the history, (D, D) is the only equilibrium of the first period game. In other words, profile of strategies σ_i(Ø) = C, σ_i(h) = Nice after each 1-period history h is the only subgame perfect equilibrium.

Part (2). Strategy profile σ_i(Ø) = C and σ_i(h) = ⎧⎨⎩ Nice if h = CC Not nice otherwise for each player i is a Nash equilibrium.

Solutions to Lecture 9 problems

Lecture 9. Games with incomplete information↑

Infinitely repeated Battle of Sexes

Part (1). The infinite outcome is (OO,SO,OO,OO, OO, ...). (We use a convention that Her action is denoted first and His action is second).

The payoff of She is

5 + 0δ + 5δ² + 5δ³ + ... = 5 + 5δ²(1 + δ + δ² + ...) = 5 + 5δ²(1)/(1 − δ).

The payoff of He is

3 + 0δ + 3δ² + 3δ³ + ... = 3 + 3δ²(1 + δ + δ² + ...) = 3 + 3δ²(1)/(1 − δ).

Part (2i). Her current payoff is equal to

5 + δ3 + δ²5 + δ³3 + ... = (5 + δ3)(1 + δ² + δ⁴ + ...) = (5 + δ3)/(1 − δ²).

If she deviates in any period, she receives 0 in that period (insted of 3 or 5) and at most the the same payoff in any other subsequent period as using the current strategy. Because 0 is smaller than 3 or 5, her current strategy is a best response.

His current payoff is

3 + δ5 + δ²3 + δ³5 + ... = (3 + δ5)(1 + δ² + δ⁴ + ...) = (3 + δ5)/(1 − δ²).

If he deviates in any period, he receives 0 in that period and at most 3 in any subsequent period (notice that following his deviation, she plays Opera forever). Thus, the deviation leads to weakly smaller payoff in each period than the current strategy. It follows that his behavior is a Nash equilibrium.

Part (2ii). Consider a history in the beginning of period 2 h = (OS). In particular, in period 1 she played Opera and he played Stadium. From now on, His strategy tells Him to alternate between Stadium (periods 2, 4, 6,...) and Opera (periods 3, 5, 7, ..). Her strategy tells her to play Opera forever. Her strategy is not abest response as she would like to met Him in every period.

Part (2iii). We can modify His strategy so that He always plays Opera after every history in which He and She did not met in the past.

Battle of Sexes with incomplete information

Part (a) Let

σ_He(dh) = S = σ_He(hM), σ_He(hA) = O,

σ_She(m) = S, σ_She(a) = O.

We will show that this strategy profile is a Bayesian Nash equilibrium for p ≤ (5)/(8).

In the same way as in the class, we can check that his strategy is a best response to her strategy (remember that type “didn’t hear” consider both of the types of She equally likely).

We check whether Her strategy is a best response. If She has type “meet”, she knows for sure that He will choose S. Because She “meet” type wants to meet with Him, she will choose S as a best response.

On the other hand, She “avoid” type expects that He chooses O with probability p (i.e., when He is hA type) and He chooses S with probabiltiy 1 − p (i.e., when He is the “meet” type. If p ≤ (5)/(8), choosing O is a best response for Her.

Part (2) When p > (2)/(3), then the strategy profile described above is not an equilibrium because Her action if she is “avoid” type is not a best response. Intuitively, when She is pretty sure that he heard her conversation, She expect him to follow Her to the Opera.

We will find an equilibrium, in which Her “avoid” type randomizes. Let

σ_He(dh) = S = σ_He(hM), σ_He(O|hA) = (5)/(8p),

σ_She(m) = S, σ_She(O|a) = (5)/(8).

We will show that this strategy profile is a Bayesian Nash equilibrium for p > (5)/(8).

Notice that the incentives of His type “heard M” and Her type “meet” are the same as previously. His type “didn’t hear” expects to find her at the Stadium with probability more than 1 ⁄ 2, which only strenghtens his resolve to choose S.

We will check that the types “heard A of Him and “avoid” of Her are indifferent between playing O and S. Notice that She “avoid” expects him to choose Opera with the probability exactly (1 − p)0 + p(5)/(8p) = (5)/(8). This makes her indifferent between choosing O and S. Moreover, He “heard A” expects Her to be in the Opera with probability (2)/(3). Thus, He is indifferent as well.

Solutions to Lecture 10 problems

Lecture 10. Games with incomplete information II↑

Cournot model with asymmetric beliefs about costs

Update (02.12.2014): The text of this solution was corrected to reflect the discussion that we had in class. The previous solution did not take into account the fact that the best response and the equilibrium actions have to be non-negative.

Part (1). Define E_ic = π_ic_H + (1 − π_i)c_L. for each player i Then, using the same arguments as in the class, we can check that each player i type c best response quantity is equal to

(2) q^BR_i(q_− i, c) = max⎛⎝(1)/(2)(α − c − E_iq_− i), 0⎞⎠,

where

E_iq_− i = π_− iq^H_− i + (1 − π_− i)q^L_− i.

Notice that the best response of the low cost type is always higher than the best response of the high cost type, q^BR_i(q_− i, c^L) ≥ q_i(q_− i, c^L)

Suppose that (q_i(c))^{c = L, H}_{i = 1, 2} is a profile of equilibrium quantities. Then, for each i and each cost c, it must be that

q_i(c) = q^BR_i(q_− i, c).

Given the best response formula (2↑), for each player i, there are three possible cases:

q^L_i > q^H_i > 0. In this case, it must be that
(3) q_i(c) = (1)/(2)(α − c − E_iq_− i) > 0 , for each c.
q^L_i > q^H_i = 0. In this case, it must be that
(4) q^L_i = (1)/(2)(α − c^L − E_iq_− i) > 0, α − c^H < E_iq_− i.
q^L_i = q^H_i = 0. In this case, it must be that
(5) α − c^L < E_iq_− i.

We need to consider all possible combination of cases. For instance, consider cases 1⁽¹⁾1⁽²⁾ (here, the superscript denotes the player). Then all quatities solve equations (3↑) . We can solve the equations in similar way to the equations that we solved in class. The solutions are equal to

q_i(c) = (α − c − E_− iq_− i)/(2) = (α − c − (α − 2E_− ic + E_ic)/(3))/(2).

The above profile is an equilibrium of the game with incomplete information if and only if all the above quantities are positive. The last requirement delivers conditions on parameters under which the above solution is an equilibrium.

For another example, consider the case 3⁽¹⁾1⁽²⁾. Here, we have

q^H₂ = (1)/(2)(α − c^H), q^L₂ = (1)/(2)(α − c^L), q^H₁ = q^L₁ = 0.

The above profile is a Bayesian Nash equilibrium if and only if inequalities (3↑) for player 2 and (5↑) for player 1 are satisfied, i.e.,

α − c^L < π₂⎛⎝(1)/(2)(α − c^H)⎞⎠ + (1 − π₂)⎛⎝(1)/(2)(α − c^L)⎞⎠, α − c^L > α − c^L > 0.

All the other cases are dealt accordingly.

Part (2). The expected equilibrium payoff of type c is

q_i(c)(α − c − q_i(c) − E_− iq_− i) = ⎛⎜⎝(α − c − (α − 2E_− ic + E_ic)/(3))/(2)⎞⎟⎠⎛⎜⎝α − c − (α − c − (α − 2E_− ic + E_ic)/(3))/(2) − (α − 2E_− ic + E_ic)/(3)⎞⎟⎠ = ⎛⎜⎝(α − c − (α − 2E_− ic + E_ic)/(3))/(2)⎞⎟⎠⎛⎝(1)/(2)(α − c) + (1)/(2)(α − 2E_− ic + E_ic)/(3) − (α − 2E_− ic + E_ic)/(3)⎞⎠ = (1)/(4)⎛⎝α − c − (α − 2E_− ic + E_ic)/(3)⎞⎠².

The higher the beliefs π_i, the higher the expected cost of player i, E_ic, and the lower the profits of player i’s types. This makes sense - if player i is likely to have high cost, player − i expects that player i chooses small quantity. This makes it best response for player − i to choose large quantity (remember that in Cournot duopoly, player − ibest response decreases with player i’s quantity.) But large quantity of player − i reduces the profits of player i's types.

Thus, player i would like player − i to belief that i has low costs, or that π_i is very low.

Attack on the city

Part (1). There are two players. Each player has two types, w, s. Type shas probability π_i and type w has probability 1 − π_i.

Part (2). The payoff of type w of player 1 is equal to

(1 − π_− i)⋅1 + π_− i⋅( − 1) = 1 − 2π_− i

if she attackes, and 0 if she does not attack.

The payoff of type s of player 1 is equal to − 1if she attacks and 0 if she does not attack.

Part (3). Such an equilibrium always exists.

Part (4). If 2π_i ≤ 1 for each player i, then there exists an equilibrium, in which the generals attack if and only if the see weak fortifications. The probabiloity that the attack is successful is equal to the probability that both sides of the fortifications are weak, which is equal to (1 − π₁)(1 − π₂).

Cleaning room game I

There is a unique BNE in which both high value types always clean and the low value types never clean. (To see why, notice that clkeaning is a best response for the high type given that the low type of the other guy does not clean and no matter what the high type of the other guy is doing.)

Romeo and Juliet

Part 1. No. (If p > (1)/(4), then Romeo’s best response is Casino. In such a case, Lucky’s JUliet action is not optimal. If p < (1)/(4), Rome’s best response is Boxing, in which case Unlucky Juliet’s action is not optimal.

Part 2. The payoff from Casino is equal to

p(α_L(1 + 2) + (1 − α_L)1) + (1 − p)1.

The payoff from Boxing Match is equal to

p(α_L0 + (1 − α_L)2) + (1 − p)2.

This implies

α_L = (1)/(4p)

Part 3. Let α_L be the probability that l ucky Juliet goes to the Casino and let β be the probability that Romeo goes to the Casino. Because lucky Juliet must be indifferent in equilibrium, we have

− β + 3(1 − β) = β − (1 − β),

which implies β = (2)/(3). Unlucky Juliet must prefer Boxing, so that

3β − (1 − β) > − β + 1 − β,

which holds if β = (2)/(3). Because Romeo must also be indifferent, we have

p(α_L(1 + 2) + (1 − α_L)1) + (1 − p)1 = p(α_L0 + (1 − α_L)2) + (1 − p)2.

This implies

α_L = (1)/(4p).

In particular, α_L is a well-defined probability if p ≥ (1)/(4).

Part 4. We consider two separate games with perfect information. The two games are solved separately. With Lucky Juliet, there is a unique equilibrium. In the equilibrium, Juliet goes to Casino with prob. (1)/(4), and Romeo goes to Casin with prob. (2)/(3). When Juliet is Unlucky, it is, respectively, (1)/(4) and (1)/(3).

Extras

Plurality voting

Lecture 1. Games. Dominant strategies↑

In the class, we consider a plurality voting with three proposals a, b, c. There are N = 50 voters. Each voter votes for one proposal. The proposal with the largest number of votes wins. In case of ties, the outcome is chosen randomly from all the proposals that received the largest number of votes.

Assume that an indidual M has the following preferences:

M: Prefers a to b, b to c.

The above preferences implies (some) ranking over ties. For example, M prefers a to tie ac to c.

Claim 1. There is no (weakly or strictly) dominant action.

Proof. We will show only that voting for a is not weakly dominant (the proof in case of voting for b or c is either analogous or easier). It is enough to show that there is a profile of other players actions (i.e., votes) such that voting for a gives a strictly lower payoff than voting for something else. Indeed, suppose that 20 of other people vote for b, 20 vote for c, and the rest (i.e., 9 other people) vote for a. We will write a⁹b²⁰c²⁰. Then, voting for a leads to a tie bc; voting for b leads to alternative b being chosen. Because M prefers b to tie bc (recall that c is the worst alternative), voting for b leads to a higher payoff. QED.

Claim 2. Voting for a or b is not weakly dominated.

Proof. The proof of the above claim implies that voting for b is not weakly dominated (make sure that you understand why). Convince yourself that a is not weakly dominated as well. QED.

Claim 3. Voting for c is weakly dominated by voting for a.

Proof. We need to show that (1) for each profile of other players’ actions, voting for a leads to a better or equal outcome than voting for c, and (2) sometimes, voting for a leads to a strictly better outcome.

Part (2) is easier. Suppose that the rest votes a²⁰b⁹c²⁰. Then, voting for a leads to a being chosen, and voting for c leads to a c winning, which is strictly worse.

For part (1), suppose that other (than M) people votes are a^n_ab^n_bc^n_c, where n_a + n_b + n_c = N − 1 = 49. To emphasize, n_a is the number of votes for A without counting M’s vote. If M’s vote is counted, I will denote the total number of votes for A as n’_a with analogous notations for other outcomes. We consider the following cases

Outcome if vote for c	Case	Outcome if vote for a
A, (n’_a = n_a > n’_b = n_b, n’_c = n_c + 1)	n_a > n_c + 1, n_b	A (n’_a = n_a + 1 > n’_b = n_b, n’_c = n_c)
AB	n_a = n_b > n_c + 1	A
ABC	n_a = n_b = n_c + 1	A
AC	n_a = n_c + 1 > n_b	A
B	n_b > n_a, n_c + 1	AB or B
BC	n_b = n_c + 1 > n_a	AB or B
C	n_c + 1 > n_a, n_b	does not matter

In all cases, it is either better to vote for a than c or there is no effect. QED.

Bubble game

Lecture 2. Iterated elimination and rationalizability↑

There are N ≥ 2 players. Each player chooses an action a_i = 0, ..., 100 and recives payoff equal to

u_i(a_i, a_− i) = a_i − penalty_i(a_i, a_− i)

where

penalty_i(a_i, a_− i) = ⎧⎨⎩ 0, if a_i ≤ max_j ≠ ia_j − 10 10(a_i − (max_j ≠ ia_j − 10)) if a_i > max_j≠ia_j − 10.

In other words, each player’s payoff is increasing in her action, as long as the action is smaller than the largest action among other players minus 10. Then, the payoff is quickly decreasing in one’s own action.

(COMMENT: Notice that the maximum in the payoff function is taken over all the other players but i. If, instead max_j ≠ i we took max_j, the analysis would be change. Try to convince yourself that you understand why.)

Claim. For each n ≤ 10, the set of actions that survives the IESD is equal to Aⁿ_i = {0, ..., 100 − 10n}. For each n > 10, Aⁿ_i = {0}.

See the proof below. Before that, two comments:

This is an example of a game that can be solved by IESD. Common knowledge of rationality implies that all players should be playing 0. In fact., when you learn about Nash equilibrium, you can check that this game has a unique Nash equilibrium in which everyone is playing 0. But, as we have seen in class, the behavior in the real world may look very different.
If we repeated this game many times, the actions would probably converge to the Nash equilibrium. Think why.

Proof: The proof goes by induction on n. The claim holds for n = 0 as A⁰_i = {0, ...100} is the initial set of actions. Suppose that Aⁿ_i = {0, ..., 100 − 10n} is the set of actions that survives the nth stage, and suppose that n < 10. At the (n + 1)th stage, each player knows that only actions a_j ≤ 100 − 10n are going to be used by other players. In particular,

max_j ≠ ia_j − 10 ≤ 100 − 10n − 10 = 100 − 10(n + 1).

Define a^*_i = 100 − 10(n + 1).

We want to show that any action a_i such that a_i > a^*_i is strictly dominated by a^*_i. Given that a_j ∈ Aⁿ_i for each j, the payoff from a_i is equal to

u_i(a_i, a_− i) = a_i − 10(a_i − (max_j ≠ ia_j − 10)) = − 9a_i + 10(max_j ≠ ia_j − 10).

The payoff from a^*_i is equal to

u_i(a^*_i, a_− i) = a_i − 10(a_i − (max_j ≠ ia_j − 10)) = − 9a^*_i + 10(max_j ≠ ia_j − 10).

Because a_i > a^*_i, the latter is strictly larger than the former.

Hotelling model of politics

Lecture 2. Iterated elimination and rationalizability↑

Game:

Players: i = 1, 2 - two (opportunist) politicians,
Actions: a_i = 1, ..., Ṁ - two candidates choose locations on the political spectrum - they choose their platforms a₁, a₂ = 1, 2, ..., M. We assume that M is even and M ≥ 4.
Payoffs: the number of votes received. Each one of each locations is inhabited by exactly one voter. Each voter votes of the closer candidate. If two candidates equally close, votes are split equally. The payoffs are equal to
u_i(a_i, a_− i) = ⎧⎪⎨⎪⎩ a_i + (1)/(2)((a_− i − 1) − a_i), if a_i < a_− i M ⁄ 2, if a_i = a_− i, M − ⎛⎝a_− i + (1)/(2)((a_i − 1) − a_− i)⎞⎠, if a_i > a_− i.

Claim. For each player, action 1 is strictly dominated by 2.

Proof: Indeed,

a_− i u(1, a_− i) u(2, a_− i) 1 M ⁄ 2 M − 1 2 is strictly better 2 1 M ⁄ 2 2 is strictly better a_− i > 2 (1)/(2)a_− i (1)/(2) + (1)/(2)a_− i 2 is strictly better

A similar argument shows that M is strictly dominated by M − 1. More generally, we have.

Claim. For each k < (M)/(2), A^k_i = {k + 1, ..., M − k}.

Proof. By induction on k. Suppose that the claim holds for k. Then, only actions A^k_i = {k + 1, ..., M − k} survive the first k stages of IESD. We show that in the k + 1 stage game, if k + 1 < (M)/(2), then action k + 1 is strictly dominated by k + 2. Indeed, given that a_− i ≥ k + 1 , we have

a_− i u(k + 1, a_− i) u(k + 2, a_− i) k + 1 M ⁄ 2 M − (k + 1) k + 2 is strictly better k + 2 k + 1 M ⁄ 2 k + 2 is strictly better a_− i > k + 2 (1)/(2)k + (1)/(2)a_− i (1)/(2)k + (1)/(2) + (1)/(2)a_− i k + 2 is strictly better

(Notice that the above comparison rely on the fact that k + 1 < (M)/(2).) A similar argument shows that M − k is strictly odminated by M − k − 1.

IESD in Cournot duopoly

Lecture 3. Nash equilibrium↑

Recall that in Cournot duopoly, there are two firms, i = 1, 2 that simultaneously choose quantities q_i ≥ 0 and receive profits:

π_i(q_i, q_− i) = (α − c − (q_i + q_− i))q_i.

The best response function for each i is given by

b_i(q_− i) = max⎛⎝0, (1)/(2)(α − c − q_− i)⎞⎠.

Notice that the best response function is (weakly) decreasing in the quantity of the other guy. Also, notice that for each x < y, the set of best responses to quantities q_− i ∈ [x, y] (i.e., the image of the interval [x, y] under the best response function) is equal to

b_i([x, y]) = [b_i(y), b_i(x)].

(In other words, the boundaries of the interval get flipped. This is due to the fact that the best response function is decreasing.)

We define formally the process of the iterated elimination of never best responses. Let

A⁰_i = [0, ∞)

be the set of actions in the original game. Suppose that A^k_. be the set of actions that survived the first k stages of elimination. Let

A^k + 1_i = b_i(A^k_− i)

be the set of actions that are best responses to some of the actions of player − i that survived the first k stages. Then, A^k + 1_i is the set of actions of player i that survived the first k + 1 stages of elimination.

Claim 1. For each k ≥ 0, there exists 0 ≤ x^k < y^k such that the set of actions that survive the iterated elimination in k stages is equal to the interval A^k_i = [x^k_i, y^k_i]. Moreover we have

x^k + 2_i = b_i(b_− i(x^k_i)), y^k + 2_i = b_i(b_− i(y^k_i)).

Proof. We proceed by induction. Indeed, notice that the inductive claim holds for k = 0 with x⁰_i = 0 and y⁰_i = ∞. If the inductive claim holds for 1, ..., k, then

A^k + 1_− i = b_− i(A^k_i) = b_− i([x^k_i, y^k_i]) = [b_− i(y^k_i), b_− i(x^k_i)],

which implies that the inductive claim holds for k + 1 as well with

x^k + 1_− i = b_− i(y^k₋), y^k + 1_− i = b_− i(x^k_i).

Notice that the above values do not depend on i because the best response functions for both players are the same, b_i = b_− i. Moreover,

A^k + 2_i = [x^k + 2_i, y^k + 2_i] = b_i([x^k + 1_− i, y^k + 1_− i]) = [b_i(y^k + 1_− i), b_i(x^k + 1_− i)] = [b_i(b_− i(x^k_i)), b_i(b_− i(y^k_i))].

QED.

Claim 2. x^k → (1)/(3)(α − c) .

Proof. Notice first that for each k ≥ 1, 0 < x^k_i < y^k_i < (1)/(2)(α − c). (It is easy to see the claim for k = 1, and the rest follows from the fact that each of the subsequent steps is contained in the previous one.) So, we can ignore the “max” operator in the description of the best response function. The first claim implies that for each k,

x^k + 2_i = (1)/(2)⎛⎝α − c − (1)/(2)(α − c − x^k_i)⎞⎠ = (1)/(4)(α − c) + (1)/(4)x^k_i.

Thus,

(1)/(3)(α − c) − x^k + 2 = (1)/(3)(α − c) − (1)/(4)(α − c) − (1)/(4)x^k = (1)/(12)(α − c) − (1)/(4)x^k = (1)/(4)⎛⎝(1)/(3)(α − c) − x^k⎞⎠.

Thus, if k is even, then the repeated application of the above equality shows that

(1)/(3)(α − c) − x^k + 2 = (1)/(4)⎛⎝(1)/(3)(α − c) − x^k⎞⎠ = ⎛⎝(1)/(4)⎞⎠²⎛⎝(1)/(3)(α − c) − x^k − 2⎞⎠ = ... = ⎛⎝(1)/(4)⎞⎠^{k ⁄ 2 + 1}⎛⎝(1)/(3)(α − c) − x⁰⎞⎠ = ⎛⎝(1)/(4)⎞⎠^{k ⁄ 2 + 1}⎛⎝(1)/(3)(α − c)⎞⎠.

In the last line, we used the fact that x⁰ = 0. Similarly, when k is odd, we get

x^k + 2 − (1)/(3)(α − c) = (1)/(4)⎛⎝x^k − (1)/(3)(α − c)⎞⎠ = ⎛⎝(1)/(4)⎞⎠^{(k − 1) ⁄ 2}⎛⎝x¹ − (1)/(3)(α − c)⎞⎠ = ⎛⎝(1)/(4)⎞⎠^{(k + 1) ⁄ 2}⎛⎝(1)/(2)(α − c) − (1)/(3)(α − c)⎞⎠ = ⎛⎝(1)/(4)⎞⎠^{(k + 1) ⁄ 2}⎛⎝(1)/(12)(α − c)⎞⎠,

where we used the fact that x¹ = (1)/(2)(α − c). In both cases, ||x^k − (1)/(3)(α − c)|| → 0 as k → ∞.

Because a similar argument shows that y^k → (1)/(3)(α − c), we conclude that

A^k_i → ⎧⎩(1)/(3)(α − c)⎫⎭

as k → ∞. QED.

Cournot duopoly with fixed costs

Lecture 4. Nash equilibrium – examples↑

In the Cournot duopoly with fixed costs, there are two firms, i = 1, 2 that simultaneously choose quantities q_i ≥ 0 and receive profits:

π_i(q_i, q_− i) = ⎧⎨⎩ (α − c − (q_i + q_− i))q_i − f if q_i > 0, 0, if q_i = 0.

Here, f > 0 is a fixed cost of production.

We are going to describe all possible equilibria for all combinations of parameter values. We start with describing the best response function. Because the profit function is given piecewise, we will consider separately two cases.

The best response is q_i = 0. In such a case, the profits of player i are equal to 0.
The best response is strictly positive, q_i > 0. In such a case, the best response maximizes
max_{q_i}q_i(α − c − (q_i + q_− i)) − f.
The first order conditions imply that
q^#_i = (1)/(2)(α − c − q_− i).
The maximial profits are equal to
q^#_i(α − c − (q^#_i + q_− i)) − f = (1)/(2)(α − c − q_− i)⎛⎝α − c − q_− i − (1)/(2)(α − c − q_− i)⎞⎠ − f = (1)/(4)(α − c − q_− i)² − f.

The former case holds if the profits from choosing q_i = 0 (i.e., 0) are larger than the maximal profits from choosing q_i > 0 (i.e., (1)/(4)(α − c − q_− i)² − f). The latter case holds when (1)/(4)(α − c − q_− i)² − f ≥ 0. To summarize, the best response function is given by

b_i(q_− i) = ⎧⎨⎩ 0, if (1)/(4)(α − c − q_− i)² ≤ f, (1)/(2)(α − c − q_− i), if (1)/(4)(α − c − q_− i)² ≥ f.

There are possible for types of equilibria, depending on the type of best response: The table below describes the equilibrium quantities and the conditions for which the equilibrium holds. The conditions are derived from the conditions which imply the type of the best response quantity:

	q₂ = 0	q₂ > 0, q₂ = (1)/(2)(α − c − q₁)
q₁ = 0	Strategies: q₁ = 0, q₂ = 0 Pl.1 EC (1)/(4)(α − c − q₂)² ≤ f⟹(1)/(4)(α − c)² ≤ f Pl.2 EC (1)/(4)(α − c − q₁)² ≤ f⟹(1)/(4)(α − c)² ≤ f	\strikeout off\uuline off\uwave off Strategies: q₁ = 0, q₂ = (1)/(2)(α − c) Pl.1 EC (1)/(4)(α − c − q₂)² ≤ f⟹(1)/(16)(α − c)² ≤ f Pl.2 EC (1)/(4)(α − c − q₁)² ≥ f⟹(1)/(4)(α − c)² ≥ f
q₁ > 0, q₁ = (1)/(2)(α − c − q₂)	Strategies: q₁ = (1)/(2)(α − c), q₂ = 0 Pl.1 EC (1)/(4)(α − c − q₂)² ≥ f⟹(1)/(4)(α − c)² ≥ f Pl.2 EC (1)/(4)(α − c − q₁)² ≤ f⟹(1)/(16)(α − c)² ≤ f	Strategies: q₁ = (1)/(3)(α − c), q₂ = (1)/(3)(α − c) Pl.1 EC (1)/(4)(α − c − q₂)² ≥ f⟹(1)/(9)(α − c)² ≥ f Pl.2 EC (1)/(4)(α − c − q₁)² ≥ f⟹(1)/(9)(α − c)² ≥ f

For example, if (q₁, q₂) is an equilibrium with strictly positive quantities for both players, it must be that both players are best responding, u.e.,

q_i = (1)/(2)(α − c − q_− i).

The unique solution is q₁ = (1)/(3)(α − c), q₂ = (1)/(3)(α − c). In order to ensure that none of the players wants to deviate to q_i’ = 0, it must be that

f ≤ (1)/(4)(a − c − q_− i)² = (1)/(4)⎛⎝a − c − (1)/(3)(α − c)⎞⎠² = (1)/(4)(4)/(9)(α − c)² = (1)/(9)(α − c)².

First attack

There are two players i = 1, 2. The players choose when to attack, where player 1 chooses an odd period t₁ = 1, 3, 5, 7, ..., and player 2 chooses an even period t₂ = 2, 4, 6, ....

If player i attacks first, t_i < t_− i, she receives payoff equal to
p_i(t_i).
We interpret p_i(t_i) ∈ [0, 1] as a probability of winning and we assume that it is strictly increasing in the time of the first attack,
p_i(t) < p_i(t + 2) for each t.
If player i does not attack first, player i wins with probability
1 − p_− i(t_− i),
(which is equal to the complement of the probability that − i wins.

Proposition. If lim_{t → ∞}p₁(t) + p₂(t + 1) > 1, then there exists an equilibrium. In the equilibrium, one player i chooses t^* and the other player − i chooses t^* + 1. Moreover,

(6) p_i(t^*) + p_− i(t^* + 1) ≥ 1, p_i(t^*) + p_− i(t^* − 1) ≤ 1.

Proof.

First, in equilibrium, it must be that either t₁ = t^*₂ + 1 or t^*₂ = t^*₁ + 1. Indeed, suppose that t_i < t_− i is . If t_− i ≠ t_i + 1, then player i would be able to attack first if she deviated to t_i + 2. Because the latter has a larger probability of winning, it is preferrable.

The first step shows that in the equilibrium (if such exists), it must be that one player i chooses t^* and the other player − i chooses t^* + 1. In the second step, we show that the inequalities ($↑) must hold. Indeed, if t_i = t^*, t_− i = t^* + 1 is an equilibrium, then it cannot be profitable for player i to deviate to t_i’ ≥ t^* + 2. If so, it must be that

p_i(t^*) ≥ 1 − p_− i(t^* + 1),

which implies the first inequality in ($↑). Similarly, it cannot be profitable for player − i to deviate to t^* − 1, or

1 − p_i(t^*) ≥ p_− i(t^* − 1),

which implies the second inequality in ($↑).

In the third step, we show that t^* that satisfies the above inequalities exists and it is unique. Indeed, define a function

f(t) = ⎧⎨⎩ p₁(t) + p₂(t + 1), if t is odd, p₂(t) + p₁(t + 1), if t is even.

Function f(t) is strictly increasing and lim_{t → ∞}f(t) > 1. Let t^* be the first (i.e., the smallest) t such that f(t) ≥ 1. If i is the player who is supposed to move at t^*, then

p_i(t^*) + p_− i(t^* − 1) = f(t^* − 1) ≤ 1, and p_i(t^*) + p_− i(t^* + 1) = f(t^*) ≥ 1,

and the conditions ($↑) are satisfied. QED

Notice that there can be at most two equilibria, (convince yourself why).

Oil auction

Lecture 10. Games with incomplete information II↑

We describe a very simplified model of a mineral rights auction (i.e., auction that the government organizes to sell the right to extract auction from a particular area).

There are two firms. The firms want to know the value of the right to extract oil. They think that this value can be equal to ω = 0, 1, 2, ..., 1000 thousand of dollars, and they consider each value equally likely (i.e., the value is uniformly distributed between 0 and 1000).

Prior to auction, both firms examine the area (send prospectors, do sample drillings, etc.) The two firms have different sampling technologies. Firm 1 can learn that the value of oil is either

high, i.e., ω > 500, or
low, i.e., ω ≤ 500.

Firm 2 can learn that the valye of oil is either

very high, i.e., ω > 750,
not so high, i.e., ω ≤ 750.

We describe the beliefs of each firm in the following tables. Beliefs of firm 1.

Types of firm 1\types of firm 2	very high	not so high
high	probability 1/2, conditional expected value = 875	probability 1/2, conditional expected value = 625
low	probability 0,	probability 1, conditional expected value = 250

Beliefs of firm 1

For instance, if firm 1 has high information, i.e., ω > 500, it considers equally likely that ω ≤ 750 or ω > 750, i.e., it considers equally likely that firm 2 has any of its two types. If, additionally, firm 2 has not so high information, it means that ω is between 501 and 750, with average value of 625.

Types of firm 2\types of firm 1	high	low
very high	probability 1, conditional expected value = 875	probability 0,
not so high	probability 1/3, conditional expected value = 625	probability 2/3, conditional expected value = 250

Beliefs of firm 2

In the auction game, both firms choose whether to bid or not. The payoffs of firm i are described in the table:

Action of firm i\action of firm − i	bid_− i	no bid_− i
bid_i	Q_both(ω − p_both)	Q_single(ω − p_single)
no bid_i	0	0

Beliefs of firm 1

Here, Q_both = (1)/(2) is the probability of winning auction when the two firms bid and p_both = 550 is the price paid in such a case. Similarly, Q_single = 1 is the probability of winning the auction if there is only one bidder, and p_single = 275 is the price paid in such a case.

We analyze the game in few steps.

We show that the low type of firm 1 has a dominant action. Compare the payoffs of the low type of firm 1 from the two actions:

no bid₁: 0,
bid₁: either Q_both(250 − p_both) if firm 2 bids, or r Q_single(250 − p_single) if firm 2 does not bid. (Notice that 250 is the expected value of the oil given that firm 1 has a low type.) In any case, the payoff from bidding is strictly negative.

No matter what firm 2 does, the payoff from not bidding is higher than the payoff from bidding. Not bidding is dominant. Hence, in equilibrium, σ₁( low) = no bid₁.

We show that the very high type of firm 2 has a dominant action. Compare the payoffs of the very high type:

no bid₂: 0,
bid₂: either Q_both(875 − p_both) if firm 1 bids, or r Q_single(875 − p_single) if firm 1 does not bid. (Notice that 875 is the expected value of the oil given that firm 2 has a very high type.) In any case, the payoff from bidding is strictly positive.

No matter what firm 1 does, the payoff from bidding is higher than the payoff from not bidding. Bidding is dominant. Hence, in equilibrium, σ₂( very high) = bid₂.

We show not bidding is eliminated at the second stage of the IESD for high type of firm 1 Consider the high type of firm 1 and compare payoffs.

no bid₁: 0,
bid₁: either
(1)/(2)Q_both(875 − p_both) + (1)/(2)Q_both(625 − p_both),
or
(1)/(2)Q_both(875 − p_both) + (1)/(2)Q_single(625 − p_single),
depending on whether the not so high type of firm 2 bids. In both cases, the payoff is strictly positive.

We show not bidding is eliminated at the second stage of the IESD for not so high type of firm 2. Consider the not so high type of firm 2 and compare payoffs.

no bid₂: 0,
bid₂: either
(2)/(3)Q_both(625 − p_both) + (1)/(3)Q_single(250 − p_single),
or
(2)/(3)Q_single(625 − p_single) + (1)/(3)Q_single(250 − p_single),
depending on whether the high type of firm 1 bids. In both cases, the payoff is strictly positive.

Firm-labor union bargaining

In single-person decision problems, more information means that the decision can more precisely respond to the state of the world, which means higher payoffs. More information is always better. M

It turns out that in games, having more information can be bad. We explain how using an example of four related games.

In all four games, a labor union negotiates wages with a firm through an ultimatum game. Union makes the only offer w. Firm decides to accept it or reject. If the firm accepts, the payoffs are (w, π − w), where the first payoff goes to the union, the second one goes to the firm, and π is the value of revenue (minus non-labor costs) that the firm makes. If the firm rejects, both the firm and the union get 0.

We assume that π is uniformly distributed on the interval [0, 1]. That means that π has a p.d.f. (probability density function)

f(π) = 1 if π ∈ [0, 1],

and c.d.f. (cumulative distribution function)

F(x) = Prob(π ≤ x) = x.

Variant Ia. Assume that the firm knows π, but the labor union does not. The firm will accept the wage if and only if π ≥ w. If the firm accepts the wage, the union gets w; otherwise the union gets 0. The expected payoff of the union is equal to

w⋅Prob(w is accepted) + 0⋅Prob(w is rejected) = w⋅Prob(π ≤ w) = w⋅(1 − Prob(π ≤ w)) = w(1 − F(w)) = w(1 − w).

The union chooses wage offer to maximize the expected payoffs,

max_ww(1 − w),

and the optimal wage can be found by the first order conditions,

w^* = (1)/(2).

The expected payoff of the union is equal to

u^Ia = w^*(1 − w^*) = (1)/(4),

and the expected payoff of the firm can be found by integrating over profits for which the firm does not reject the union’s offer:

f^Ia = ¹⌠⌡_w^*(π − w^*)f(π)dπ = ¹⌠⌡_(1)/(2)⎛⎝π − (1)/(2)⎞⎠dπ = (1)/(8).

Variant Ib. Assume now that the union and the firm know π. (For instance, the labor union has a seat on the management board and insight in the financial state of the company.) In such a case, the labor union will demand w = π, and the firm will accept it. The payoff of the union is equal to

u^Ib = ¹⌠⌡₀πf(π)dπ = ¹⌠⌡₀πdπ = (1)/(2).

The payoff of the firm is

f^Ib = 0,

because the labor union extracts the entire surplus. Notice that the labor union is better off with additional information.

Variant IIa. Suppose that prior to bargaining, the firm decides whether to build a factory or not. If the factory is built, the firm pays fixed cost c < (1)/(8), and then proceeds to the bargaining as described in game Ia. Otherwise, the firm does not build factory, the game ends with payoffs 0 for the firm and the union.

The payoffs in the continuation game are

(u^Ia, f^Ia) = ⎛⎝(1)/(2), 0⎞⎠.

In such a case, the firm will decide to build the factory and the payoffs will be

u^IIa = u^Ia = (1)/(4), f^IIa = f^Ia − c = (1)/(8) − c > 0.

Variant IIb. Suppose that prior to bargaining, the firm decides whether to build a factory or not. If the factory is built, the firm pays fixed cost c < (1)/(8), and then proceeds to the bargaining as described in game Ib. Otherwise, the firm does not build factory, the game ends with payoffs 0 for the firm and the union.

The payoffs in the continuation game are

(u^Ia, f^Ia) = ⎛⎝(1)/(2), 0⎞⎠.

In such a case, the firm will prefer not to build the factory and the payoffs of the union will be

u^IIb = 0 < u^IIa.

Comparing cases IIa and IIb, the labor union is worse off with more information.

	Nice	Not nice
Nice	(2, 2)	(0, − 2)
Not nice	( − 2, 0)	( − 1, − 1)

Pl.1\Pl.2	L	C	R
U	4,5	-1,2	3,0
M	3,1	2,3	3,6
D	0,4	3,3	4,3

She\He	Opera	Stadium
Opera	5,3	0,0
Stadium	0,0	3,5