ECO326 Advanced Economic Theory: Game Theory

Fall 2017

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 Midterm↓ (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:

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.

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.

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 tie ac, 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, (na = na > nb = nb, nc = nc + 1) na > nc + 1, nb A (na = na + 1 > nb = nb, nc = 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, ..., Ṁ - 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.