Spring 2014
Web page: http://www.math.toronto.edu/ilia/MAT406.2014/.
Class Location & Time: Tue, 02:00 PM - 03:00 PM CC2130; Thu, 01:00 PM - 03:00 PM IB 260
Tutorials: Th 10:00- 11:00 DV 3131
Instructor: Ilia Binder (ilia@math.toronto.edu), William G. Davis Bldg. 4038, Phone: (905) 569-4381.
Office Hours: Tu, Th 11-12.
Teaching Assistant: Charles Tsang (ctsang@math.toronto.edu).
Office Hours: by appointment.
Required Text: Philip D. Straffin, Game Theory and Strategy; The Mathematical Association of America (1993).
Online books:
Prerequisites: MAT223H5, STA257H5.
Topics.
The course will discuss the mathematical aspects of the game theory, an important area of Mathematics/Probability with multiple applications to Economics, Political Science, and Evolutionary Biology, to name a few.
The course will start with the discussion of impartial combinatorial games: subtraction game, Nim, and Chomp, will discuss the Sprague-Grundy value. After a brief discussion of partisan combinatorial games, we will discuss the zero-sum games and von Neuman's minimax theorem. We will discuss various methods for solving such games. The next big topic will be the general sum games and Nash equilibrium. Other topics will include the coalition games and Shapley value, applications of Game theory to voting (such as Arrow theorem), auctions, and stochastic games.
Topics covered in class.
January 7: Introduction.
January 9: The games of Chomp! and Nim. The Nim sum. Bouton's theorem. Peres, section 2.1; Ferguson, sections I.1, I.2.
January 14: The games of Nim and misere Nim. Sprague-Grundy function. Ferguson, sections I.2, I.3.
January 16: Sum of combinatorial games. Sprague-Grundy theorem. Examples of using Sprague-Grundy function. Ferguson, sections I.3, I.4.
January 21: Partisan Games. Zero-sum games: examples and definition. Peres, sections 2.2, 3.1; Ferguson, sections II.1.1, II.1.2
January 23: Zero-sum games: further examples, geometric properties of the set of mixed strategies, von Neumann Theorem. Saddle points. Ferguson, sections II.1.3, II.1.4, II.2.1, Straffin, sections 2, 3.
January 28: Full analysis of the 2x2 games. Ferguson, section II.2.2; Straffin, section 3.
January 30: Proof of von Neumann Theorem. 2xm and nx2 games. Domination. Ferguson, sections II.2.3, II.2.4; Peres, sections 3.2, 3.3; Straffin, sections 2, 3.
February 4: Symmetric games. The Principle of Indifference. Ferguson, sections II.3.1, II.3.5.
February 6: The principle of indifference. Diagonal games. Use of symmetry. Extensive form of a game. Ferguson, sections II.3.2, II.3.3, II.3.6, II.5.1, II.5.2, II.5.3; Peres, section 3.4; Straffin, section 5.
February 11: Converting extensive form to strategic. Ferguson, sections II.5.4, II.5.5, II.5.6; Straffin, section 7.
February 13: General sum games: definition, strategic and extensive form, safety levels, Nash equilibrium. Ferguson, sections III.1, III.2.1; Peres, sections 4.1, 4.2; Straffin, sections 11, 12.
February 25: Midterm review.
March 4: Finding Nash Equilibria for 2x2 games. Ferguson, section III.2.2.
March 6: Proof of Nash Theorem in general case. Finding Nash equilibria. Carnot Duopoly. Ferguson, sections III.2.3, III.2.4, III.3.1, Appendix 3; Peres, section 4.5.
March 11: Models of duopoly. Feasible solutions for cooperative games. Ferguson, sections III.3.2, III.3.3; III.4.1.
March 13: Cooperative games : solution for TU games, Nash solution of NTU games. Ferguson, sections III.4.2; III.4.3.
March 18: Cooperative games : Shapley solution of NTU games, Coalition form of a game. Relation to the strategic form. Ferguson, sections III.4.3, IV.1.1, IV.1.2.
March 20: Constant sum games. Imputations and core. Essential games. Shapley value. Ferguson, sections IV.1.3, IV.2.1, IV.2.2, IV.2.3, IV.2.4, IV.3.1.
March 25: An Alternative form of Shapley value. Ferguson, sections IV.3.2, IV.3.3.
March 27: Simple games. The Shapley-Shubik power index. Social choice and Arrow Theorem. Ferguson, sections IV.3.4; Peres, sections 8.1, 8.2.
April 1: Proof of Arrow Theorem. Peres, section 8.3.
April 3: Auctions. Final review. Peres, sections 7.1, 7.2.
Homework.
Assignment #1, due January 23: Ferguson, page I-6, problems 1, 4, 8a; Page I-12, problems 2, 3.
Assignment #2, due January 30: Ferguson, page I-18, problem 2; page I-19, problems 3, 8; page I-26, problems 1, 3.
Assignment #3, due February 6: Straffin, page 12, problem 5; page 21, problem 2; Ferguson, page II-14, problems 1,2; page II-15, problem 8.
Assignment #4, due February 13: Ferguson, page II-14, problems 4, 5, 6; page II-15, problem 9; page II-31, problem 11.
Assignment #5, due March 13: Ferguson, page III-6, problems 1, 2, 3; page III-13, problems 1, 4.
Assignment #6, due March 20: Ferguson, page III-14, problems 5, 6; page III-23, problems 1, 4, 6.
Assignment #7, due March 27: Ferguson, page III-39, problems 2 (there are two problems with this number - do the first of them), 3b, 4 ; page III-40, problems 5, 7.
Assignment #8, due April 3: Ferguson, page IV-5, problems 1, 3; page IV-6, problem 4; page IV-10, problem 4; page IV-18, problem 4.
Midterm Test. There will be an in-class midterm test on Thursday, February 27. No aides are allowed for this test.
The test will cover combinatorial and zero-sum games, roughly the first two chapters of Ferguson.
Recommended preparation (do not turn in): all homework problems and the following problems from Ferguson: I.2.6.4, I.3.5.1, I.3.5.6, I.4.5.8, II.2.6.10, II.3.7.1, II.3.7.3, II.3.7.14, II.5.9.1, II.5.9.3.
Final exam. You will be allowed to use one one-sided letter-sized page of notes. Textbooks or calculators are not allowed for this exam.
Recommended preparation (do not turn in): all homework problems, practice problems for midterm, and the following problems from Ferguson: III.2.5.2, III.2.5.7, III.3.5.3, III.3.5.7, III.4.5.1, IV.1.5.2, IV.2.5.2, IV.2.5.8, IV.3.5.2, IV.3.5.7.
2012 Final Exam.
Extra office hours for the final: Friday, April 11 2 - 4 pm. Location: DV4038
Grading. Grades will be based on eight homework assignments (5% each), Midterm test (25%), and Final exam (35%). I will also occasionally assign bonus problems.
Late work. Extensions for homework deadlines will be considered only for medical reasons. Late assignments will lose 20% per day. Submission on the day the homework due after the tutorial is considered to be one day late. Special consideration for late assignments or missed exams must be submitted via e-mail within a week of the original due date. There will be no make-up midterm tests or final. Justifiable absences must be declared on ROSI, undocumented absences will result in zero credit.
Plagiarism and Academic Honesty.
Students are expected to adhere to the academic regulations of the University as outlined in the “Code of Behaviour on Academic Matters” which can be found in the UTM Calendar or on the web at http://www.utm.utoronto.ca/regcal/WEBGEN120.html.
The work you submit must be your own and cannot contain anyone else’s work or ideas without proper attribution. Plagiarism is a form of academic fraud and is treated very seriously. Please have a look at http://www.utoronto.ca/writing/plagsep.html.