### Transcription of 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.