# Contact information

 Name Lecture Office hours Contact Instructor Marcin Pęski Monday, 6-8pm, SS2127 Monday 2.30-4.30 am, Max Gluskin 207 mpeski@gmail.com TA Kevin Fawcett Tutorial: Monday, 8-9pm, SS2127 Wed, 1-2pm, 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 11-09 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↓. 18-09 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. 25-09 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. 02-10 Lecture 4. Nash equilibrium – examples↓ 3.2, 3.5 Cournot oligopoly. Bertrand duopoly. Bertrand with differentiated products. 16-10 Lecture 5. Mixed strategies↓ 4.1-4.5, 4.9 Mixed strategies. Nash equilibrium in mixed strategies. Penalty shot. Traffic game. 23-10 (in class, during the regular class hours) 30-10 Lecture 6. Extensive form games. Subgame perfection↓ 5.1-5.5, 6.1-6.2 Extensive-form game. Strategies. Nash equilibrium. Subgame Perfect equilibrium. 13-11 Lecture 7. Extensive form games – examples↓ 7.1-7.2, 7.6-7.7 Ultimatum game. Alternating offer bargaining. Hold-up model. Entry game. 20-11 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. 27-11 Lecture 9. Games with incomplete information↓ 9.1-9.3 Infinitely repeated Prisoner’s Dilemma. 4-12 Lecture 10. Games with incomplete information II↓ 9.4-9.5, 7.6 Battle of Sexes with uncertain preferences. 7-12** Lecture 11. Auctions↓ 3.5, 9.6 Cournot oligopoly with uncertain costs. 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:
1. Textbook: 6.1, 16.1, 17.1, 20.1, 47.1 (the first sentence only), 49.1* (without the last sentence), 49.2*
2. Watch this video:\begin_inset Separator latexpar\end_inset
• 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)?
3. 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 ui(A), ui(B), and ui(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.
4. 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.\begin_inset Separator latexpar\end_inset
1. Suppose that individual i has preferences ui(A) > ui(B) > ui(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?

# Lecture 2. Iterated elimination and rationalizability

Problem set:
1. Textbook: 387.2.
2. Find all actions that survive the iterated elimination of weakly dominated strategies in problems 391.2, 391.3.
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 mn > 0 voters and the total number of voters is M = m0 + m1 + m2 + … + m10. As in the class, each voter votes for the closest politician and splits the vote in case of tie. \begin_inset Separator latexpar\end_inset
• 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 nn* 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.
4. 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 ni = 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: \begin_inset Separator latexpar\end_inset
• 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 ni ≠ 5 is weakly dominated by 5. Show that 5 is the only actions that survive the iterated elimination of weakly dominated strategies.
5. 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.

# 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.
Problem set: 2 × 2
Textbook: 37.1, 38.1, 38.2, 27.1*, 27.2*, 31.1, 31.2*, 42.1*, 42.2*, 58.1

# 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:
1. Textbook: 58.1, 59.2* (notice that the game is symmetric, but for some comination of parameters, it may only have asymmetric equilibria), 63.1, 67.1, 68.2, 392.1 (rationalizability in Bertrand duopoly).
2. (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 = p1 + … + pN of voluntary contributions pi 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 disutility − pi of making her contribution. \begin_inset Separator latexpar\end_inset 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? 3. (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 pi. The prices are set simultaneously. The production costs in Truck i are equal to ci ≥ 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 (pi − ci)Di(pi, p − i), where Di(pi, p − i) is the demand for products of truck i and it is equal to Di(pi, p − i) = 0, if pi ≥ p − i + 1, (1)/(2)(p − i − pi + 1), if p − i − 1 ≤ pi ≤ p − i + 1, 1, if pi ≤ p − i − 1. 1. Find the best response function of each truck. 2. Show that there exists values of costs c1 and c2 and an equilibrium prices given these costs so that one of trucks does not sell anything. # Lecture 5. Mixed strategies Before the lecture, play Rock-Scissors-Paper on this website. • 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: 1. Textbook: 114.2, 114.3, 114.4, 117.2, 120.2, 120.3 2. 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. 3. 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). \begin_inset Separator latexpar\end_inset • 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. \begin_inset Separator latexpar\end_inset • 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 (that is statisticaleese for “Nash equilibrium does pretty well). 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. 4. 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: \begin_inset Separator latexpar\end_inset • 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. # Midterm Here are links to some of the past midterms: # Lecture 6. Extensive form games. Subgame perfection Problem set: 1. Textbook: 156.2*, 161.1*, 163.1, 163.2*, 164.2, 168.1, 173.2*, 173.3*, 173.4*, 174.1, 189.1, 191.1*, 2. 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. \begin_inset Separator latexpar\end_inset 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. # Lecture 7. Extensive form games – examples Problem set: 1. Textbook: 174.2*, 177.1*, 177.2*, 183.1, 183.2*, 183.3*, 183.4*, 185.2, 186.1, 192.1*. 2. (Ultimatum game with randomly chosen offerent). 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? 3. 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) = e2 for each one of them. The quality of the idea, and their join profits depend on their join efforts. If Sarah chooses eS and Ann chooses eA, then their expected joint profits are equal to p(eA, eS) = (eS) + (eA). 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(eA, eS). 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? 4. (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 < 1 and the discount factor of player 2 is equal to δ2 < 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 # Lecture 8. Repeated games Problem set. 1. Textbook: 210.2, 211.1*, 211.2*, 212.1*, 214.1*, 234.1*, 426.1, 428.1, 429.1, 430.1*, 431.1*, 431.2* 2. 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.) 3. 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). \begin_inset Separator latexpar\end_inset 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 ## Solutions to Lecture 1 problems ### 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) ui(A) > ui(B) > ui(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 nA other players choosing A, nB other players choosing B, and nC other players choosing C. Of course, it must be that nA + nB + nC = 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 (nA + 1)/(100)ui(A) + (nB)/(100)ui(B) + (nC)/(100)ui(C). Indeed, notice that if player i votes A, then there are nA + 1 players voting A, which means that Ais chosen with probability (nA + 1)/(100), • the payoff from strategy B is (nA)/(100)ui(A) + (nB + 1)/(100)ui(B) + (nC)/(100)ui(C), • the payoff from strategy C is (nA)/(100)ui(A) + (nB)/(100)ui(B) + (nC + 1)/(100)ui(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 (nA + 1)/(100)ui(A) + (nB)/(100)ui(B) + (nC)/(100)ui(C) − (nA)/(100)ui(A) + (nB + 1)/(100)ui(B) + (nC)/(100)ui(C) = (1)/(100)(ui(A) − ui(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 is swicthes her vote from SA to C. ## Solutions to Lecture 2 problems ### 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 si < a, and si > 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 1. strategy si = a is strictly dominated by a + 1,\begin_inset Separator latexpar\end_inset 1. strategy si = 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 si = 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 si = a + 1 is equal to ma + 1 + ... + m10 = M − (m0 + ... + ma). 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 ma + 1 + ... + m10 > (M)/(2). Thus, playing si = 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 si = a is equal to m0 + ... + ma, • the number of votes received from playing si = a + 1 is equal to (M)/(2), • because a < n*, the definition of the median voter n* implies that m0 + ... + ma < (M)/(2). Thus, playing si = a + 1 leads to a strictly higher payoff. • Suppose that s − i > a + 1. Then, switching from strategy si = a to a + 1 allows player i to gain (1)/(2)mk 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 si = 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 si = 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 ni ≠ 5. • Suppose that n − i ≠ 5. Then, if player i chooses ni = 5, she wins the election. In any other case, she may lose or tie. Thus, i’s payoff is weakly higher if she chooses ni = 5. • Suppose that n − i = 5. Then, if player i chooses ni = 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 ni = 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 ### Textbook problem 59.2* In this problem, firm is payoffs are equal to πi(qi, q − i) = qi(α − c − qi − q − i) − f, if qi = 0, 0, otherwise. In particular, the payoffs are described by two different functions depending on whether the firm is active (qi > 0) or inactive (qi = 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*1 = q*2 = 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 qi > 0, its payoff is going to be equal to qi(α − c − qi) − f. The above expression is maximized by qmoni = (1)/(2)(α − c) (this can be derived from the standard first order conditions - notice that the above function is concave in qi) [A] [A] Notice that qmoni is equal to the optimal monopoly quantity., in which case, the payoff becomes equal to qmoni(α − c − qmoni) − f = (1)/(4)(α − c)2 − 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)2 − f ≤ 0. • Case 2: Only firm i is active, qi > 0, q − i = 0. In such a case, the (active) best response of firm i (as calculated above) is qmoni = (1)/(2)(α − c). The active quantity is a best response if qmoni(α − c − qmoni) − f = (1)/(4)(α − c)2 − f ≥ 0. The inactive payoff of firm − i is equal to 0. If firm − i became active with quantity q2 > 0, her payoff would be equal to q2(α − c − qmon1 − q2) − f = q2(1)/(2)(α − c) − q2 − f. The above expression is maximized at qFollower − 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 qFollower2(1)/(2)(α − c) − qFollower2 − f = (1)/(16)(α − c)2 − f. Thus, the inactive strategy of firm − i is an equillibrium if (1)/(16)(α − c)2 − 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 qCournoti = (1)/(3)(α − c). The payoffs of both firms are equal to qCournoti(α − c − qCournoti − qCournot − i) − f = (1)/(9)(α − c)2 − f. The active quantitites are equilibrium if (1)/(9)(α − c)2 − f ≥ 0. ### Voluntary public good provision Part (a). There are N players. Actions Ai = {pi:pi ≥ 0}. Payoffs ui(pi, p − i) = 20000(p1 + … + pN)/(50)1 ⁄ 2 = 20(p1 + ... + pN) − pi. 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(p1 + ... + pN)) − 1 = 0. This implies that p1 + ... + pN = 100, or that pi = max(100 − (p1 − ... − pi − 1 − pi + 1 − ...pN), 0). = max(100 − P − i, 0). Here, P − i = p1 − ... − pi − 1 − pi + 1 − ...pN is the total contribution of all players but i. We use the maximum to take into account that the optimal action pi = 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*1 + ... + 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 Hopt = (Nt*)/(50) = 2N2. 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 > ci − 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 pi = p − i + 1 − ϵ for some small ϵ > 0. Thus, if p − i > ci − 1, then compute max(pi − ci)(p − i − pi + 1) st. pi ≥ p − i − 1. The first order conditions imply that that the best response is equal to pBRi(p − i) = maxp − i − 1, (1)/(2)(1 + p − i + ci). If p − i ≤ ci − 1, then any price pi ≥ p − i + 1 is best response (and it leads to 0 profits). Part (b). Suppose that c2 > 3 + c1. Let p*1 = c2 − 1, p*2 = c2. This is an equilibrium given the above characterization of best responses.(We need to check that p*1 − 1 > (1)/(2)(1 + p*2 + c1) 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 c2 > 3 + c1. (How?) ## Solutions to Lecture 5 problems ### 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 L0.5R0.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 U4 ⁄ 5D1 ⁄ 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 ### Coins Part (1). Strategies of player 1: • σ1( Ø) = 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( Ø) = 1, σ1(11) = 2 • σ1( Ø) = 2, σ1(11) = 1 • σ1( Ø) = 2, σ1(11) = 2 Strategies of player 2: • σ2(1) = 1, σ2(2) = 1, • σ2(1) = 1, σ2(2) = 2, • σ2(1) = 2, σ2(2) = 1, • σ2(1) = 2, σ2(2) = 2, Part (2). Strategy σ1( Ø) = 1, σ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( Ø) = 1, σ1(11) = 2 for player 1 and any of the following two strategies of player 2 constitute the subgame perfect equilibrium: • σ2(1) = 1, σ2(2) = 2, • σ2(1) = 2, σ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*1 < α − c can be played player 1 in some Nash equilibrium. Indeed, consider strategy q*1for player 1 and strategy q*2(q1) = (α − c − q*1)/(2) if q1 = q*1 α − c otherwise Then, strategy profile (q*1, q*2(.)) is a Nash equilibrium. • We check that player 1 is best responding. If player 1 chooses q*1, he receives payoff α − c − q*1 − (α − c − q*1)/(2)q*1 = (α − c − q*1)/(2)q*1 > 0. If he chooses any other quantity q1 ≥ 0, he gets \strikeout off\uuline off\uwave off (α − c − q1 − (α − c))q1 = ( − q1)q1 ≤ 0. • We check that player 2 is best responding. Indeed, if player 1 chooses quantity q*1, then (α − c − q*1)/(2) is player 2’s best response Notice that the above strategy profile is not subgame perfect. ## Solutions to Lecture 7 problems ### 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(eA, eS) 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)((ei) + (e − i)) − e2i. The best response level of effort maximizes the above expression. By taking the first order conditions, we find that (1)/(4(ei)) − 2ei = 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, 1 − δ1) Part (3). (1 − δ2(1 − δ1), δ2(1 − δ1)). Part (4). Player 1 offers 1 − δ2 + δ1δ2 − δ1δ22 + δ21δ22 − ... + δk1δk2 for himself and δ2 − δ1δ2 + δ1δ22 − δ21δ22 + ... − δk1δk2 for player 2 and the offer is accepted. # Extras ## Plurality voting 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 a9b20c20. 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 a20b9c20. 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 anabnbcnc, where na + nb + nc = N − 1 = 49. To emphasize, na 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 na 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 = na > n’b = nb, n’c = nc + 1) na > nc + 1, nb A (n’a = na + 1 > n’b = nb, n’c = nc) AB na = nb > nc + 1 A ABC na = nb = nc + 1 A AC na = nc + 1 > nb A B nb > na, nc + 1 AB or B BC nb = nc + 1 > na AB or B C nc + 1 > na, nb does not matter In all cases, it is either better to vote for a than c or there is no effect. QED. ## Bubble game There are N ≥ 2 players. Each player chooses an action ai = 0, ..., 100 and recives payoff equal to ui(ai, a − i) = ai, if ai < maxj ≠ iaj − 10 maxj ≠ iaj − 10 − 20(ai − (maxj ≠ iaj − 10)) if ai ≥ maxjiaj − 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 maxj ≠ i we took maxj, 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 Ani = {0, ..., 100 − 10n}. For each n > 10, Ani = {0}. See the proof below. Before that, two comments: 1. 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., wehn you learn about Nash equilibrium, you can check that this game has a unique Nash eqyuilibrium in which everyone is playing 0. But, as we have seen in class, the behavior in the real world may look very different. 2. 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 A0i = {0, ...100} is the initial set of actions. Suppose that Ani = {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 aj ≤ 100 − 10n are going to be used by other players. In particular, maxj ≠ iaj − 10 ≤ 100 − 10n − 10 = 100 − 10(n + 1). Define a*i = 100 − 10(n + 1). For each ai > a*i = 100 − 10(n + 1), the penalty for ai is exactly 20(ai − a*i) > 0: this is the payoff decrease relative to playing a*i. It follows that ai is strictly domnated by a*i. Hence, An + 1i = {0, 1, .., 100 − 10(n + 1)}. ## Hotelling model of politics Game: • Players: i = 1, 2 - two (opportunitst) politicians, • Actions: ai = 1, ..., Ṁ - two candidates choose locations on the political spectrum - they choose their platforms a1, a2 = 1, 2, ..., M. We assume that M is even and M ≥ 4. • Payoffs: the number of votes received. Each one of each locations is inhabitated by exactly one voter. Each voter votes ofr the closer candidate. If two candidates equally close, votes are split equally. The payoffs are equal to ui(ai, a − i) = ai + (1)/(2)((a − i − 1) − ai), if ai < a − i M ⁄ 2, if ai = a − i, M − a − i + (1)/(2)((ai − 1) − a − i), if ai > 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), Aki = {k + 1, ..., M − k}. Proof. By induction on k. Suppose that the claim holds for k. Then, only actions Aki = {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 Recall that in Cournot duopoly, there are two firms, i = 1, 2 that simultaneously choose quantities qi ≥ 0 and receive profits: πi(qi, q − i) = (α − c − (qi + q − i))qi. The best response function for each i is given by bi(q − i) = max0, (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 bi([x, y]) = [bi(y), bi(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 A0i = [0, ∞) be the set of actions in the original game. Suppose that Ak. be the set of actions that survived the first k stages of elimination. Let Ak + 1i = bi(Ak − 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, Ak + 1i is the set of actions of player i that survied the first k + 1 stages of elimination. Claim 1. For each k ≥ 0, there exists 0 ≤ xk < yk such that the set of actions that survive the iterated elimination in k stages is equal to the interval Aki = [xki, yki]. Moreover we have xk + 2i = bi(b − i(xki)), yk + 2i = bi(b − i(yki)). Proof. We proceed by induction. Indeed, notice that the inductive claim holds for k = 0 with x0i = 0 and y0i = ∞. If the inductive claim holds for 1, ..., k, then Ak + 1 − i = b − i(Aki) = b − i([xki, yki]) = [b − i(yki), b − i(xki)], which implies that the inductive claim holds for k + 1 as well with xk + 1 − i = b − i(yk − ), yk + 1 − i = b − i(xki). Notice that the above values do not depend on i because the best response functions for both players are the same, bi = b − i. Moreover, Ak + 2i = [xk + 2i, yk + 2i] = bi([xk + 1 − i, yk + 1 − i]) = [bi(yk + 1 − i), bi(xk + 1 − i)] = [bi(b − i(xki)), bi(b − i(yki))]. QED. Claim 2. xk → (1)/(3)(α − c) . Proof. Notice first that for each k ≥ 1, 0 < xki < yki < (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, xk + 2i = (1)/(2)α − c − (1)/(2)(α − c − xki) = (1)/(4)(α − c) + (1)/(4)xki. Thus, (1)/(3)(α − c) − xk + 2 = (1)/(3)(α − c) − (1)/(4)(α − c) − (1)/(4)xk = (1)/(12)(α − c) − (1)/(4)xk = (1)/(4)(1)/(3)(α − c) − xk. Thus, if k is even, then the repeated application of the above equality shows that (1)/(3)(α − c) − xk + 2 = (1)/(4)(1)/(3)(α − c) − xk = (1)/(4)2(1)/(3)(α − c) − xk − 2 = ... = (1)/(4)k ⁄ 2 + 1(1)/(3)(α − c) − x0 = (1)/(4)k ⁄ 2 + 1(1)/(3)(α − c). In the last line, we used the fact that x0 = 0. Similarly, when k is odd, we get xk + 2 − (1)/(3)(α − c) = (1)/(4)xk − (1)/(3)(α − c) = (1)/(4)(k − 1) ⁄ 2x1 − (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 x1 = (1)/(2)(α − c). In both cases, ||xk − (1)/(3)(α − c)|| → 0 as k → ∞. Because a similar argument shows that yk → (1)/(3)(α − c), we conclude that Aki → (1)/(3)(α − c) as k → ∞. QED. ## Cournot duopoly with fixed costs In the Cournot dupoly with fixed costs, there are two firms, i = 1, 2 that simultaneously choose quantities qi ≥ 0 and receive profits: πi(qi, q − i) = (α − c − (qi + q − i))qi − f if qi > 0, 0, if qi = 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 qi = 0. In such a case, the profits of player i are equal to 0. • The best response is strictly positive, qi > 0. In such a case, the best response maximizes maxqiqi(α − c − (qi + 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)2 − f. The former case holds if the profits from choosing qi = 0 (i.e., 0) are larger than the maximal profits from choosing qi > 0 (i.e., (1)/(4)(α − c − q − i)2 − f). The latter case holds when (1)/(4)(α − c − q − i)2 − f ≥ 0. To summarize, the best response function is given by bi(q − i) = 0, if (1)/(4)(α − c − q − i)2 ≤ f, (1)/(2)(α − c − q − i), if (1)/(4)(α − c − q − i)2 ≥ 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:  q2 = 0 q2 > 0, q2 = (1)/(2)(α − c − q1) q1 = 0 Strategies: q1 = 0, q2 = 0 Pl.1 EC (1)/(4)(α − c − q2)2 ≤ f⟹(1)/(4)(α − c)2 ≤ f Pl.2 EC (1)/(4)(α − c − q1)2 ≤ f⟹(1)/(4)(α − c)2 ≤ f \strikeout off\uuline off\uwave off Strategies: q1 = 0, q2 = (1)/(2)(α − c) Pl.1 EC (1)/(4)(α − c − q2)2 ≤ f⟹(1)/(16)(α − c)2 ≤ f Pl.2 EC (1)/(4)(α − c − q1)2 ≥ f⟹(1)/(4)(α − c)2 ≥ f q1 > 0, q1 = (1)/(2)(α − c − q2) Strategies: q1 = (1)/(2)(α − c), q2 = 0 Pl.1 EC (1)/(4)(α − c − q2)2 ≥ f⟹(1)/(4)(α − c)2 ≥ f Pl.2 EC (1)/(4)(α − c − q1)2 ≤ f⟹(1)/(16)(α − c)2 ≤ f Strategies: q1 = (1)/(3)(α − c), q2 = (1)/(3)(α − c) Pl.1 EC (1)/(4)(α − c − q2)2 ≥ f⟹(1)/(9)(α − c)2 ≥ f Pl.2 EC (1)/(4)(α − c − q1)2 ≥ f⟹(1)/(9)(α − c)2 ≥ f For example, if (q1, q2) is an equilbirium wiht strictly positive quantities for both players, it must be that both players are best responding, u.e., qi = (1)/(2)(α − c − q − i). The unique solution is q1 = (1)/(3)(α − c), q2 = (1)/(3)(α − c). In order to ensure that none of the players wants to deviate to qi’ = 0, it must be that f ≤ (1)/(4)(a − c − q − i)2 = (1)/(4)a − c − (1)/(3)(α − c)2 = (1)/(4)(4)/(9)(α − c)2 = (1)/(9)(α − c)2. ## First attack There are two players i = 1, 2. The players choose when to attack, where player 1 chooses an odd period t1 = 1, 3, 5, 7, ..., and player 2 chooses an even period t2 = 2, 4, 6, .... • If player i attacks first, ti < t − i, she receives payoff equal to pi(ti). We interpret pi(ti) ∈ [0, 1] as a probability of winning and we assume that it is strictly increasing in the time of the first attack, pi(t) < pi(t + 2) for each t. • If player i does not attack first, player i wins with probabiliity 1 − p − i(t − i), (which is equal to the complement of the probability that − i wins. Proposition. If limt → ∞p1(t) + p2(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) pi(t*) + p − i(t* + 1) ≥ 1, pi(t*) + p − i(t* − 1) ≤ 1. Proof. First, in equilibrium, it must be that either t1 = t*2 + 1 or t*2 = t*1 + 1. Indeed, suppose that ti < t − i is . If t − i ≠ ti + 1, then player i would be able to attack first if she deviated to ti + 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 ti = t*, t − i = t* + 1 is an equilibrium, then it cannot be profitable for player i to deviate to ti’ ≥ t* + 2. If so, it must be that
pi(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 − pi(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) =  p1(t) + p2(t + 1),    if t is odd,         p2(t) + p1(t + 1),    if t is even.
Function f(t) is strictly increasing and limt → ∞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
pi(t*) + p − i(t* − 1)  =  f(t* − 1) ≤ 1,   and pi(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).