Game Theory (W4210) Course Notes - Columbia …

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.

2 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 . 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.

3 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. Existence I: Maximum and Intermediate Values.

4 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 .

5 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 .. 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.

6 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. Alternatives to the DU Model .. 86. Readings for Next Week.

7 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.

8 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 .. 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.

9 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 .. 139. Procedures and Properties .. 139. Backwards Induction with Continuous Action Spaces 140.

10 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.