Fall 2012
Web page: http://www.math.toronto.edu/ilia/MAT406.2012/.
Class Location & Time: Tue, 01:00 PM - 03:00 PM IB 395; Thu, 02:00 PM - 03:00 PM IB 235
Tutorials: Fr 14:00- 15:00 IB 390
Instructor: Ilia Binder (ilia@math.toronto.edu), William G. Davis Bldg. 4038, Phone: (905) 569-4381.
Office Hours: Th 10-11 and 1-2.
Teaching Assistant: Charles Tsang (ctsang@math.toronto.edu).
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.
September 11: Introduction. Definition of a combinatorial game. Impartial and partisan games. N- and P- positions. Ferguson, section I.1.
September 13: The games of Chomp! and Nim. The Nim sum. Peres, section 2.1; Ferguson, section I.2.
September 18: Bouton's theorem. The sum of combinatorial games. Sprague-Grundy function and theorem. Ferguson, sections I.2, I.3, I.4.
September 20: Examples of using Sprague-Grundy function. Ferguson, section I.4.
September 25: Partisan Games. Zero-sum games: examples, definitions, geometric properties of the set of mixed strategies. Peres, sections 2.2, 3.1; Ferguson, section II.1, Straffin, section 3
September 27: Zero-sum games: von Neumann Theorem, Saddle point, complete solution of 2x2 games. Ferguson, sections II.2.1, II.2.2, Straffin, section 2
October 2: 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.
October 4: Domination. Symmetric games. The Principle of Indifference. Ferguson, sections II.3.1, II.3.5.
October 9: 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, sections 3.2, 3.3; Straffin, section 5.
October 11: Converting extensive form to strategic. General sum games - introduction. Ferguson, sections II.5.4, II.5.5, II.5.6; Peres, sections 3.4, 4.1; Straffin, section 7.
October 16: General sum games: definition, strategic and extensive form, Safety levels, Nash equilibrium. Existence of Nash equilibrium for 2x2 games. Ferguson, sections III.1, III.2.1; Peres, sections 4.1, 4.2; Straffin, sections 11, 12.
October 18: Midterm review.
October 23: Midterm.
October 25: Proof of Sperner Lemma for n=1, 2. Peres, section 4.6.
October 30: Proofs of Sperner Lemma, Brower fixed point theorem, and Nash Theorem. Models of duopoly. Peres, section 4.6, Ferguson, section III.3.
November 1: Models of duopoly. Feasible solutions for cooperative games. Ferguson, sections III.3.3, III.4.1.
November 6: Cooperative games : solution for TU games, Nash and Shapley solutions of NTU games. Ferguson, sections III.4.2, III.4.3.
November 8: Games in Coalition form. Relation to the strategic form. Ferguson, sections IV.1.1, IV.1.2.
November 13: Constant sum games. Imputations and core. Essential game. Shapley value. Ferguson, sections IV.1.3, IV.2.1, IV.2.2, IV.2.3, IV.2.4, IV.3.1.
November 15: An Alternative form of Shapley value. Simple games. Ferguson, sections IV.3.2, IV.3.3, IV.3.4.
November 20: The Shapley-Shubik power index. Nucleolus. Ferguson, sections IV.3.4, IV.4.1.
November 22: Properties and computation of Nucleolus. Ferguson, sections IV.4.2, IV.4.3.
November 27: Social choice and Arrow Theorem. Peres, sections 8.1, 8.2.
November 29: Proof of Arrow Theorem. Auctions.Peres, sections 8.3, 7.1.
Homework.
Assignment #1, due September 20: Ferguson, page I-6, problems 1, 2, 4, 5, 8a.
Hint for problem 5: you can always split an even number into a sum of two odd numbers, but if you split an odd number, one of the summands will be even.
Assignment #2, due September 27: Ferguson, page I-12, problem 3; page I-18, problem 2; page I-19, problems 3, 8; page I-26, problem 3.
Assignment #3, due October 4: Straffin, page 12, problems 3 (no need to draw the movement diagrams, just find the saddle points), 5; page 21, problem 2; Ferguson, page II-14, problems 1,2;
Assignment #4, due October 11: Ferguson, page II-14, problems 4, 5, 6; page II-15, problems 8,9.
Assignment #5, due November 1: Ferguson, page II-55, problems 2,3 (in both of the problems, also find the equivalent strategic form and solve the games); page III-6, problems 1, 2, 3.
Assignment #6, due November 8: Ferguson, page III-13, problems 1; page III-14, problems 5, 6; page III-23, problems 1, 4.
Assignment #7, due November 15: Ferguson, page III-23, problems 6; page III-39, problems 2 (there are two problems with this number - do the first of them), 3b, 4 ; page III-40, problem 5.
Assignment #8, due November 27 (the extension given because a technical glitch lead to unavailability of the assignment before November 18): Ferguson, page IV-5, problems 1, 3; page IV-6, problem 4; page IV-10, problem 4; page IV-18, problem 7.
Midterm Test. There will be an in-class midterm test on Tuesday, October 23. 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.2, I.3.5.1, I.3.5.3, I.4.5.8, II.2.6.10, II.3.7.1, II.3.7.3, II.3.7.14, II.5.9.3, II.5.9.4
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, III.4.5.7, IV.1.5.2, IV.2.5.2, IV.2.5.8, IV.3.5.2, IV.3.5.4, IV.4.4.2, IV.4.4.8.
2008 Final Exam.
Extra office hours for the final: Wednesday, December 19, 2.30-4.30. Location: DV2068B
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 10% per day.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.