362 Politics and the Theory of Games

Fall 2007

Note: this course differs markedly from another course of the same title, Poli Sci 4621, taught in Fall 2005 by Prof. Sened. You can receive credit for both courses.

Brief topics outline

Course requirements and textbooks

• Avinash Dixit and Susan Skeath, Games of Strategy, 2nd edition (hardback; ISBN 0-393-92499-8). W.W. Norton, 2004. Price now up to $138, for which I apologize. Used copies should be available. Don't buy the first edition, since it does not list the same problems and exercises.
• William Poundstone, Prisoner's Dilemma (paperback; ISBN 0-385-41580-X). Anchor Books division of Random House, 1992. About $16.

Your course grade will be determined by the following activities:

• Problem sets, every week or two -- to contribute 40% of course grade.
• Late paper penalty: problem sets turned in by the next class period (for example, due Monday but turned in during class on Wednesday) will be penalized 10% of the points possible. Those turned in later than that will be penalized 40%.
• Help Sessions:
  • Sundays 4:00-5:00 Eads 116: will meet 9/9/07
  • Monday or Tuesday evening -- TBA
• Two exams -- to contribute 25% of course grade EACH.
  • In-class; 2nd exam is last day of classes.
  • Mainly problem-solving
• Laboratory exercises, to be conducted in class or on the internet -- 10% of course grade.
  • You will receive "payoffs" from playing games like the ones we consider in the course, and these will contribute toward your course grade, based on game theoretic predictions of what you ought to be able to earn.
  • This part of the grade is primarily calibrated to encourage (1) your participation in the labs and (2) your serious effort to make good decisions in them.
  • This portion of your grade will be computed in absolute terms, NOT curved or otherwise related to other students' payoffs. In other words, you need to worry about getting a high payoff for yourself, NOT about getting a HIGHER payoff than other students.

back to top

Course Outline and Assignments

Subject to revision during the semester; details to be specified. Watch this space.

I. What is Strategy?

1. Games and Decisions [read Dixit and Skeath chapters 1, 2; skim appendix to 7]
   1. Introduction and General Principles
   2. Decisions and Interactive Decisions

   Problems for Wednesdsay Sept. 5
   NOT TO HAND IN, but think about, and we'll discuss, questions 1, 3, and 4 at the end of Chapter 2.

2. Simple Strategy [Dixit & Skeath: section 4-1, 4-3]
   1. Games with Simultaneous Moves
      • Example: the Primary Campaign Game (pdf file)
   2. Dominated Strategies
   3. Solution in Dominant Strategies
   4. Solution by Successive Elimination of Dominated Strategies
      • Examples: dominant and dominated strategies (pdf file)
      • Additional notes on dominated strategies and successive elimination (pdf file)
      • Slides on successive elimination

   Problems due Monday Sept. 10
   Dixit and Skeath, pp. 114-120: #1, 4 (ignore "Nash equilibrium");
   Also: Solve the following game through successive elimination of strictly dominated strategies:
   
   
   

   	A	B	C	D
   A'	1, 2	4, 6	0, 5	1, 7
   B'	1, 1	2, 2	0, 4	1, 0
   C'	2, 4	3, 2	2, 1	2, 3
   D'	0, 1	2, 3	9, 2	0, 0

   
   

3. Games whose players take turns [Dixit & Skeath: Chapter 3]
   1. Games with Sequential Moves
      • Slides: Examples of sequential-move games from Dixit & Skeath
      • Slides: Exercises on sequential-move games from Dixit & Skeath
   2. Rollback Analysis
      • Slides: Game trees and simple rollback analysis
      • Rollback analysis of Checkers article in Science
   3. Rollback Analysis when Players are Indifferent between Two or More Actions
   4. Rollback Analysis with Moves by Chance
      • Slides: Rollback analysis with complications

   Problems due Monday Sept. 17
   Dixit and Skeath, pp. 79-81, #3 (a-c), 7, 9
   

4. Equilibrium in Games with Simultaneous Moves
   1. Rational Game Play in General: Anticipated Strategies and Best Responses
      • Dixit & Skeath figures on best response and equilibrium
   2. Rationalizable Strategies [Dixit and Skeath: section 5-4(A)]
      • Dixit & Skeath figures on rationalizability
   3. Nash Equilibrium [Dixit & Skeath: section 4-2, 4-4, 4-6]
      • An Experiment
      • Dixit & Skeath figures on best response and equilibrium
   4. Note on zero-sum games [not assigned: Dixit & Skeath section 4-5]
   5. "Coordination" in games with more than one Nash equilibrium [Dixit & Skeath: section 4-7]
      • Results from Schelling's Coordination Test

   Problems due Monday Sept. 24
   Dixit and Skeath:

   • p. 153, #6
   • pp. 114-120, #3 (a-d), 5, 10(a and b only)
     

5. Elaborations on Equilibrium in Simultaneous-Move Games
   1. Randomizing in Simultaneous-move Games: "mixed strategies" [Dixit & Skeath: Chapter 7; and sections 8.1-8.4]
      • penalty kick video:
        • Ballack's penalty kicks
        • Beckham's penalty kick
        • amateurs practice penalty kicks
   2. Continuous Strategies [Dixit & Skeath: section 5.1 B]
   3. Discussion and Evidence [Dixit & Skeath: sections 5.2-5.3]
      • Recommended but not required reading: two empirical studies of the use of mixed strategies in soccer penalty kicks:
        • Ignacio Palacios-Huerta, "Professionals Play Minimax." Review of Economic Studies vol 70 issue 2 (April 2003), pp. 395-415. . To obtain the full article, use the menu at upper right to click on "Full Text HTML" or "Full Text PDF".
        • P.-A. Chiappori, S. Levitt, and T. Groseclose, "Testing Mixed-Strategy Equilibria When Players Are Heterogeneous: The Case of Penalty Kicks in Soccer." American Economic Review Vol. 92, No. 4. (Sept. 2002), pp. 1138-1151.

   Problems due Monday Oct. 1
   Dixit and Skeath:
   

   • Chapter 4, problem 9 (p. 118)
   • Chapter 8, problems 1, 4, 6 (pp. 258-259)

   Problems due Monday Oct. 8
   Dixit and Skeath:
   

   • 1. Chapter 5, problem 1 (p. 151-152)
   • 2. Chapter 8, problem 2 (p. 258)
   • Two additional problems, described below:

   3. For the following revised version of the "team project" game, find all Nash equilibria in pure strategies:
   • As before, Players X and Y simultaneously choose to devote x and y hours, respectively, to the project.
   • Unlike the version of the game solved in class, however, Player X is more experienced than Player Y, so X's work is understood by both players to contribute less to their overall grade. Specifically,
     • X's payoff from (x,y) is (x/2)(1 + y - x)
     • Y's payoff from (x,y) is y(1 + x/2 - y)
     Calculate the best response function for each player, and use them to identify any Nash equilibria.

     (Hint: as in the game solved in class, you can find the best response either: using calculus to maximize each player's payoff function; or using algebra, based on the fact that each player's payoff is a quadratic function of that player's effort (treating the other player's effort as a constant). In the latter approach, set the payoff function equal to zero and solve the resulting quadratic equation; then note that the maximum of that payoff occurs halfway between the two solutions.)

   
   4. For the following simultaneous-move game, find all Nash equilibria in pure and mixed strategies:
   
   

   	A	B	C
   A'	1, 1	0, 0	0, 0
   B'	0, 0	1, 1	0, 0
   C'	0, 0	0, 0	1, 1

   
   (Hint: aside from the pure-strategy equilibria, you should be able to find four mixed-strategy equilibria.)
   
   
6. Combining Sequential and Simultaneous Moves [Dixit & Skeath: Chapter 6]
   1. Simultaneous-move Turns in Sequential games
   2. Strategic Form of a Sequential-move Game [section 6-3(B)]
   3. Subgame-perfect Equilibrium
   4. slides on sequential and simultaneous moves

   Problems due Monday Oct. 15
   

   • 1. Dixit and Skeath chapter 6, exercise 3 (p. 181)
   • 2. Write down the equivalent simultaneous-move form for the game in chapter 3, exercise 2(b) (p. 79), and find all its pure-strategy Nash equilibria.
   • 3. Dixit and Skeath chapter 6, exercise 9 (p. 183)

Review for Midterm Exam -- come to class with questions

Midterm exam Wednesday Oct. 17

back to top

II. Strategy in Democratic Politics

Readings: from Dixit and Skeath, chapter 15

• skim sections 1, 2, 4, 6
• read carefullly subsection 4B and all of section 6

• 1. and 2.: Dixit and Skeath Chapter 15 exercises 1 and 2 (pp. 532-533)
• 3. Recall that a "sequential" agenda is one in which alternatives are voted upon one at a time in a predetermined order; as soon as any alternative gains a majority, the voting ends and that alternative is the winner. (If no alternative gains a majority, the status quo of no bill prevails.) In such agenda, "sincere voting" would consist of voting for an alternative if and only if one prefers it to the status quo. Consider the following voting situation:
  • Voting is to follow a sequential agenda in which three different versions of a bill are voted upon in the order A, then B, then C.
  • A majority of members prefers version A to version B; a majority prefers version B to version C; and a majority prefers version A to version C.
  • A majority of members prefers C to the status quo.
  • A majority prefers the status quo to A.
  • A majority prefers the status quo to B.
  For this voting situation,
  1. explain what would be the outcome if all members vote sincerely
  2. draw the voting tree and use it to determine what will happen if all members vote sophisticatedly.
  
  
• 4. Recall that a "king-of-the-hill" agenda is one in which alternatives are voted upon one at a time in a predetermined order; each alternative that wins a majority of votes case becomes the "standing decision" against which the next alternative in the agenda is pitted. (At the beginning of the agenda, the "standing decision" is the status quo of no bill.) Consider the following voting situation:
  • A majority prefers alternative A to alternative B
  • Some majorities prefer B to alternatives C and D.
  • Some majority prefers B to the status quo.
  • Some majorites prefer C and D to A.
  • Some majority prefers the status quo to A.
  For this voting situation,
  1. Design an order of voting on the alternatives in a king-of-the-hill agenda in which, if all members vote sophisticatedly, alternative A will be chosen.
  2. Sincere voting in a king-of-the-hill agenda consists in voting for an alternative if and only if one prefers it to the current "standing decision." Is there any order of voting on A, B, C, and D in a king-of-the-hill procedure in which A will be chosen if all members vote sincerely?
  
  
• 5. In a three-candidate, plurality election among candidates A, B, and C, suppose there are six voters, one having each of the six possible strict preference rankings of the three candidates. Each voter receives a payoff of 5 if her favorite candidate wins, 3 if her second-favorite candidate wins, and 0 if her least-favored candidate wins; there is no cost to voting. Any tie election will be broken by random choice with equal probabilities among the leading vote-getters. A tie outcome is valued by a voter according to the expected utility of the ultimate outcome. For each candidate, describe a pure-strategy Nash equilibrium, with no voter using a weakly dominated strategy, in which that candidate wins the election outright.

1. Committee voting and agenda design
   • Article on agenda procedures for the 1998 campaign finance bill. The outcome of that vote is reported in Katz, Jeffrey L. and Carroll J. Doherty. "CAMPAIGN FINANCE: Campaign Finance Gets Day in the Sun, But Senate's Shadow Is Looming." CQ Weekly Online (August 8, 1998): 2173-2174. .
   • recommended only for further reading on amendment voting in Congress: Stanley Bach, "Parliamentary Strategy and the Amendment Process: Rules & Case Studies of Congressional Action." Polity Vol. 15, No. 4 (Summer, 1983), pp. 573-592. Click here to download via JSTOR.
   
   
   
2. Electoral competition
   • recommended only for further reading on mixed-strategy voter equilibrium in a two-candidate election:
     • Thomas R. Palfrey and Howard Rosenthal, "A Strategic Calculus of Voting." Public Choice Vol 41 (1983), pp. 7-53. PDf file downloadable from this table of contents.
     • Palfrey and Rosenthal, "Voter Participation and Strategic Uncertainty." American Political Science Review Vol. 79, No. 1. (Mar., 1985), pp. 62-78. Click here to download via JSTOR.

• 1. Suppose an election is to pit two candidates against one another, with each candidate taking a position on a one-dimensional issue scale measured from -5 to 5, on which voters have ideal points and each voter chooses the candidate whose position is closest to his or her ideal. Indifferent voters cast, in effect, one-half of an expected vote for each candidate. Voter ideal points are located as follows:
  • 2 voters' ideals are at -5
  • 4 voters' ideals are at -4
  • 5 voters' ideals are at -3
  • 5 voters' ideals are at -2
  • 6 voters' ideals are at -1
  • 5 voters' ideals are at 0
  • 5 voters' ideals are at 1
  • 5 voters' ideals are at 2
  • 3 voters' ideals are at 3
  • 2 voters' ideals are at 4
  • 1 voter's ideal is at 5
  
  (a.) What is the position of the median voter?
  
  One candidate is an incumbent; her position is already fixed by her previous decisions while in office. The second candidate, the challenger, is to choose a position. Under each of the following conditions, tell what is the highest PAYOFF the challenger could receive and specify ALL the positions that would yield that payoff level to the challenger:
  
  (b.) The challenger receives a payoff of 1 for getting more expected votes than the incumbent, 0 for getting fewer, and 1/2 for getting the same number of expected votes. The incumbent is located at 2.
  
  (c.) The challenger receives a payoff equal to his total number of expected votes; the incumbent is located at -3.
  
  (d.) As in part (c), but the incumbent is located at -1.
  
  
• 2. At the end of chapter 15 in Dixit and Skeath, (p. 536), do exercise 10.
  • One extra hint: get started by drawing a picture of the issue space, showing the distribution of voter ideal points and the other candidates' positions; and then calculate what vote share you would get from each of the three different third-candidate locations Dixit and Skeath suggest. Notice that a challenger in the "middle" position would get the support of half the voters whose ideals are between x and 1-y.
  • Another extra hint: in part (c), it won't matter whether you allow candidates to take any position on the line (using arbitrarily tiny distances), or require them to locate only at a finite set of discrete positions, such as {0, .01, .02, ..., 1.00}. Think about it either way; the answer will be the same.

III. The Politics of Game Theory

Readings: in advance of class, as follows:

• For Monday 11/12: Chapters 1, 3 (pp. 37-44, 61-64 only), 4. (You might skim chapter 2; but we won't be spending a lot of time on von Neumann's biography.)
• For Wednesday 11/14: Chapters 5, 7, 8; chapter 9 (pp. 179-189 only).
• To guide your reading, here are some discussion questions on the assigned portions of the Poundstone book.
• Written Assignment to turn in Wednesday 11/14
  • Write a short essay (one page or less) summarizing what Poundstone has to say about: (1) where game theory came from, and (2) the role of game theorists in the second World War.

For further information: Some websites on the intellectual history of game theory

• History of Economic Thought web page on game theory lists many predecessors and mid-20th century discoveries, including:
• Auguste Cournot (1801-1877) presented what we now call Cournot (quantity) competition in Recherche sur les principes mathematiques de la theorie de richesses ("Researches into the mathematical principles of the theory of wealth," 1838)
• Ernst Zermelo (1871-1953) "Uber eine Anwendung der Mengenlehre auf die theorie des Schachspiele", 1913, Proceedings of Fifth International Congress of Mathematicians. ("On an application of set theory to the theory of chess games."). In game theory's first theorem, argues that a game of chess with rational players could be solved trivially by an algorithm.
• Emile Borel (1871-1956) work in 1920s with English translations in Econometrica 1953. Introduced the abstract notion of a "strategic game" and formulated concept of a "mixed strategy".
• John von Neumann first published a proof of the minimax theory in "Zur Theorie der Gessellshaftspiele" ("The Theory of Chess Games"), 1928, Mathematische Annalen.
• John F. Nash (1928-)
  • "Equilibrium points in N-Person Games", 1950, Proceedings of NAS.
  • "The Bargaining Problem", 1950, Econometrica.
  • "A Simple Three-Person Poker Game", with L.S. Shapley, 1950, Annals of Mathematical Statistics.
  • "Non-Cooperative Games", 1951, Annals of Mathematics.
  • "Two-Person Cooperative Games", 1953, Econometrica.
• The first paper published in the American Political Science Review using game theory was Lloyd S. Shapley and Martin Shubik, "A method for evaluating the distribution of power in a committee system." American Political Science Review, Vol. 48, 1954, pgs. 787--792. Click here to obtain via JSTOR.

For further information: Some websites on the cold war, arms race, and arms limitation agreements:

• National Resources Defense Council Archive of Nuclear Data -- great statistics
• Federation of American Scientists index & details on Arms Control Agreements
• Websites on 1946 Operation Crossroads (Bikini Atoll tests), with photos:
  • Atomic archive
  • Atomic Veterans Photo Album

IV. How can People Cooperate?

1. The Prisoner's Dilemma: experiments, applications
   • For Monday 11/19 read Poundstone: Chapters 6; Chapter 11 (especially pp. 221-230)
   • Slides from a talk on cooperation in PDs in laboratory experiments
   
   
2. For Monday 11/26 & Wednesday 11/28: Repeated games. Reading assignments:
   • Poundsone Ch. 12
   • Robert Axelrod, "Effective Choice in the Prisoner's Dilemma." Journal of Conflict Resolution vol. 24, no. 1 (Mar., 1980), pp. 3-25. Click here to obtain on line via JSTOR.
   • Robert Axelrod, "More Effective Choice in the Prisoner's Dilemma." Journal of Conflict Resolution vol. 24, no.3 (Sep., 1980), pp. 379-403. Click here to obtain on line via JSTOR.
   
   
3. Visual aids and simulations:
   • Click here to download a copy of the spreadsheet on best responses to Tit-for-Tat.
   • Click here to download a copy of the spreadsheet showing a simple PD tournament with ecological analysis.
   • Click here to download a copy of the graph showing results of Axelrod's actual ecological analysis.
   
   
4. Problems due Monday 12/3:
   
   Answer the questions below concerning an indefinitely repeated prisoner's dilemma game in which the stage-payoffs are as follows:

   	C	D
   C	2, 2	0, 3
   D	3, 0	1, 1

   
   Let d be the discount factor, the probability of continuing to one more repetition of the stage game. For these questions, you will need to make use of the basic formula for adding up an infinite stream of discounted future payoffs: assuming the first payoff is not discounted,
   
   

   SUM [from t = 0 to infinity] of (d)t = 1 / (1 - d)

   
   
   1. Suppose that payoffs in the repeated game are summed up using discount factor 0.9 for each player. What is the total repeated-game payoff to the row player in the following strategy profiles?
   1. Row Cooperates in all odd-numbered periods, beginning with the first, and Defects on all even-numbered periods. Column does the opposite: Defect in odd periods, Cooperate in even.
   2. Column plays Tit-for-Tat (TFT), beginning with Cooperation in the initial period. Row's strategy is to begin by Defecting, and to continue defecting until her opponent Defects; thereafter, Row Cooperates twice and then continues by playing TFT forever.
   2. Suppose Row uses the strategy TFT. Either unconditional cooperation (ALL C) or unconditional defection (ALL D) is a best response for Column. What is the smallest value of d for which ALL C is a best response?
   3. Suppose the payoff in the stage game from mutual cooperation is changed from 2 to 2.5, all the other payoffs remaining the same. Now it is also possible for DCDC... to be a best response against TFT.
      1. What condition on d makes DCDC... a better response than ALL C?
      2. What condition on d makes DCDC... a better response than ALL D?
   
   
   
5. Optional additional reading:
   • Dixit and Skeath Chapter 11, "The Prisoner's Dilemma and Repeated Games."
   • Specifically, you can review the ideas of infinitely repeated games with dicounting of future payoffs, and the algebra of discounting itself, in Chapter 11: Section 2 and Appendix.
   • Robert Axelrod, "The Emergence of Cooperation among Egoists." American Political Science Review vol. 75 issue 2 (June 1981), pp. 306-318. Click here to obtain via JSTOR.
   
   
6. (if time:) Cooperation in larger groups
   
   

The Course evaluation website is now open. Please visit it sometime near the end of the semester. Your responses will help guide the future design of the course.

back to top

V. Why is There War?

1. Games with sequential moves and "incomplete information"
   
   
2. A simple crisis game: war with regrets
   
   
3. A crisis game with two-sided incomplete information
   • Slides: game tree showing information structure of the game
     
   • Spreadsheet: calculating parameter values that yield valid mixed-strategy equilibria
   
   
4. Problems for Wednesday 12/5
   • You need NOT turn in this homework; we will discuss it in class on Wednesday, and there may be such a problem on the exam.
   • Click here to download the problems (one game and a few questions concerning it) as a PDF file. Corrections made as per my 12/5 email.
     
     

back to top

Optional review session: Friday Dec. 7 3:00-5:00 PM in Eliot 213.

Second exam: in class, Monday Dec. 10.

This exam will cover all material since the first midterm. There will be no separate final exam.

back to top

This page written by Randall Calvert © 2007
Email comments and questions to calvert at wustl.edu