Game Theory (W4210) Course Notes - Columbia University

1 This is page i Printer: Opaque this Game Theory ( w4210 ). Course Notes Macartan Humphreys September 2005. ii ABSTRACT These Notes are written to accompany my class Political Science w4210 in the political science program at Columbia University . They are in progress. Please send comments and corrections to me at: This is page iii Printer: Opaque this Contents 1 Getting Started 1. Reading these Notes .. 1. Reading the Readings .. 1. Anticipatory reading .. 1. Pictures and Programs .. 2. Writing .. 3. Dictionary .. 3. Sources and Resources .. 3. Books on the Syllabus .. 3. Recommended Books Not on the Syllabus .. 4. Recommended On-Line Resources .. 4. Notation Refresher .. 5. Logic Symbols .. 5. Necessary and Su cient Conditions .. 5. Set Operations .. 6. Some (fairly standard) symbols for particular sets.

2 6. Convexity and Concavity .. 6. Preference Relations %, R .. 7. 2 General Approaches to the Problem of Group Action 9. No Predictions Possible?: Arrow's Theorem .. 9. SWF, Axioms and Statement of the Theorem .. 10. Formal Statement and Proof .. 12. iv Contents Examples of SWFs and Consequences of Axiom Vi- olation .. 13. Freedom to Trade and Precise and Pleasant Predictions .. 14. Freedom of Action and Precise but Pessimistic Predictions . 16. Sen: On the Impossibility of a Paretian Liberal .. 19. Note on readings for next week .. 20. 3 How to Prove it I: Strategies of Proof 21. By Example / by Counterexample .. 21. Direct Proof .. 23. Proof by Contradiction .. 25. Establishing Monotonicity .. 27. Establishing Uniqueness .. 28. Turning the Problem on Its Head .. 28. Style .. 29. 4 How to Prove It II: Useful Theorems 33.

3 Existence I: Maximum and Intermediate Values .. 33. Existence II: Fixed Point Theorems .. 34. Application: Existence of Nash Equilibrium .. 37. Theorems to Establish Uniqueness .. 39. Methods to Make Results More General: Genericity .. 40. General functional forms and implicit function theorems .. 41. Methods to Make Proof-writing Easier (Without Loss of ) .. 46. Readings for Next Week .. 47. 5 What to Prove I: First Define your game 49. Normal Form games ( games in Strategic Form) .. 49. Definition .. 49. Pure and Mixed Strategies .. 51. Illustrating normal form games .. 51. Extensive Form games .. 52. Defining Extensive Form games of Complete Infor- mation .. 52. Defining Extensive Form games of Incomplete Infor- mation .. 53. Behavioral Strategies .. 54. Illustrating Extensive Form games .. 55. Coalitional games .

4 57. Coalitional games with non-transferable utility .. 57. Coalitional games with Transferable Utility .. 58. 6 What to Prove II: Making Assumptions, Making Points 59. Weak Assumptions, Strong Theories .. 59. Contents v Solution Concepts .. 63. I've solved the game, what now? .. 64. 7 Representing Preferences: A Menu 67. Represenation: Preferences and Utility Functions .. 67. Representation: Von Neumann-Morgenstern Utility Functions 68. Utility over a Single Dimension .. 71. Attitudes to Risk .. 71. Functional Forms .. 72. Preferences over many Dimensions With No Satiation .. 73. Preferences in the Spatial Theory .. 75. Strongly Spatial Models .. 77. Weakly Spatial Models .. 81. Intertemporal Preferences .. 83. The Discounted Utility Model .. 83. Representing time preferences in a prize-time space. 84.

5 Alternatives to the DU Model .. 86. Readings for Next Week .. 86. 8 Information 87. Bayes' Rule .. 87. Bayes' Rule with Discrete Type and Action Spaces . 87. Bayes' Rule with Continuous Type and Action Spaces 91. Interactive Epistemology .. 92. Information Partitions .. 92. Common Knowledge .. 95. Agreeing to disagree .. 100. Rationalizability and Common Knowledge of Ratio- nality .. 102. 9 Solution Concepts for Normal Form games 105. Iterated Elimination of Strictly Dominated Strategies .. 105. Iterated Elimination of Weakly Dominated Strategies .. 106. Rationalizable Strategies .. 107. Nash Equilibrium .. 108. Locating Nash Equilibria in games with Continuous Action Spaces .. 110. Nash Equilibrium with Mixed Strategies .. 110. Locating Mixed Strategy Nash Equilibria .. 111. Mixing Over Continuous Pure Strategy Sets.

6 112. Are Mixed Strategy Equilibria Believable? .. 115. Correlated Equilibria .. 116. Focal Equilibria and Pareto Dominance .. 117. Strong equilibrium .. 119. vi Contents Coalition Proof equilibrium .. 120. Perfect Equilibrium (Trembling Hand Perfection) .. 120. Proper equilibrium .. 121. 10 Solution Concepts for Evolutionary games 123. Resistance, Risk Dominance and Viscosity .. 124. Identifying Risk Dominant strategy profiles .. 126. Evolutionarily Stable Strategies .. 126. Stochastically Stable Equilibria .. 128. Readings for the week after next .. 133. 11 Solution Concepts for Extensive Form games 135. The Problem With Nash Equilibrium in Extensive Form games .. 135. Subgames and Subgame Perfection .. 136. When Subgame perfection is not enough .. 137. 12 Solving Extensive Form games 139. Backwards Induction.

7 139. Procedures and Properties .. 139. Backwards Induction with Continuous Action Spaces 140. Identifying Subgame Perfect Nash Equilibria .. 142. Generalized Backwards Induction .. 142. The One Stage Deviation Principle .. 143. The Principle of Optimality .. 145. Repeated games .. 147. Identifying Nash Equilibria in Repeated games .. 147. Nash Equilibrium (Folk theorem) .. 148. Subgame Perfect Nash Equilibrium (Folk theorem) . 150. 13 Solving Extensive Form games of Incomplete Information153. Identifying Equilibrium in Bayesian Extensive games .. 153. Applications .. 158. An Application with Continuous Actions and Dis- crete Types: A Two Period Bargaining Model .. 158. An Application with Discrete Actions and Continu- ous Types: A Model of Strategic Auditing .. 161. An Exercise with Continuous Action and Type Spaces: Bargaining Again.

8 167. Refinements .. 169. Extensive Form Trembling Hand Perfection .. 170. Sequential Equilibrium .. 175. 14 Solution Concepts for Cooperative games 179. Randomization and the Negotiation Set .. 179. Contents vii The Nash Bargaining Solution .. 181. The Nash Program .. 185. The Core .. 185. The Core in Voting games : Plott's Theorem .. 186. The Shapley Value .. 192. 15 Turning Game Theory on Its Head: Mechanism Design 197. Manipulation and Voting: The Gibbard-Satterthwaite The- orem .. 198. The Revelation Principles .. 200. Monotonicity .. 202. Incentive Compatibility .. 206. Application: The Revenue Equivalence Theorem .. 208. Application II: Bargaining (Myerson-Satterthwaite) .. 209. viii Contents This is page 1. Printer: Opaque this 1. Getting Started Reading these Notes These Notes will be given out in parts to accompany the first seven weeks of class.

9 The Notes do not replace the readings but should help with the lectures and should summarize some key information in a single place. The Notes will also contain the exercises associated with di erent parts of the Course , these are marked in the text as Exercise # and are associ- ated with the lectures from a given week. In all cases they are due at the beginning of class on the following week. There are also problems marked in the text as Problem #. These do not need to be handed in, rather they are typically simple problems that are worth working through as you read through the Notes . The numbering in the text follows the week numbers in the syllabus. Reading the Readings Anticipatory reading The readings for the Course are relatively few in number but you are ex- pected to read them very very closely.

10 The recommended approach might be what's called anticipatory reading.. 2 1. Getting Started 1. First read the first few pages or the conclusion, or skim through enough to find out what the general problem is. ! Now, before going further, write down a wish list of the types of propositions / theorems that you would like to see answered in the article (really write down the form of the propositions as formally as you can). 2. Read on to see what kind of results are in fact obtained. ! Compare these with your wish list: are the results: Stronger? More general? Deeper? Surprising? Disappointing? ! Try to satisfy yourself that the results in the text are true: think of examples and try to think of counterexamples. 3. Write down a proposed strategy of proof. 4. Try to prove the propositions yourself. ! If you fail, try to prove a weaker version of the propositions.