Fall 2014
Web page: http://www.math.toronto.edu/ilia/MAT406.2014Fall/.
Class Location & Time: Tue, 11:00 AM - 12:00 PM and Thu, 01:00 PM - 03:00 PM; DV 1104
Tutorials: Wed 15:00 - 16:00 IB 200
Instructor: Ilia Binder (ilia@math.toronto.edu), Deerfield 3026.
Office Hours: Tue 13.00-14.00, Thu 11.00-12.00
Teaching Assistant: Charles Tsang (ctsang@math.toronto.edu).
Office Hours: by appointment.
Prerequisites: MAT102H5, MAT223H5, STA256H5.
Prerequisites will be checked, and students not meeting them will be removed from the course by the end of the second week of classes. If a student believes that s/he does have the necessary background material, and is able to prove it (e.g., has a transfer credit from a different university), then s/he should submit a 'Prerequisite/Corequisite Waiver Request Form'.
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 9: Introduction.
September 11: Combinatorial games. The games of Chomp! and Nim. Peres, section 2.1; Ferguson, sections I.1, I.2.
September 16: The games of Nim and misere Nim. The Nim-sum. Bouton's Theorem. Ferguson, section I.2.
September 18: Sprague-Grundy function. Sum of combinatorial games. Sprague-Grundy theorem. Examples of using Sprague-Grundy function. Ferguson, sections I.3, I.4.
September 23: Partisan Games. Zero-sum games: examples and definition. Peres, sections 2.2, 3.1; Ferguson, sections II.1.1, II.1.2
September 25: Zero-sum games: strategic form, geometric properties of the set of mixed strategies, von Neumann Theorem. Saddle points. Full analysis of the 2x2 games. Ferguson, sections II.1.3, II.1.4, II.2.1, II.2.2.
September 30: Proof of von Neumann Theorem. Peres, section 3.2.
October 2: 2xm and nx2 games. Domination. Symmetric games. The Principle of Indifference. Ferguson, sections II.2.3, II.2.4, II.3.1, II.3.5; Peres, section 3.3.
October 7: The Principle of Indifference. Diagonal and triangular games. Ferguson, sections II.3.2, II.3.3.
October 9: Use of symmetry. Extensive form of a game. Converting extensive form to strategic. Ferguson, sections II.3.6, II.5; Peres, section 3.4.
October 14: 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.
October 16: Mixed Nash equilibria. Finding Nash equilibria for 2x2 games. Brower fixed point theorem. No retraction Theorem. Ferguson, sections III.2.2; Peres, sections 4.2, 4.6.
October 21: Midterm review.
October 23: Midterm test.
October 28: Proofs of Sperner's Lemma, Brouwer fixed point theorem, and Nash Theorem. Peres, section 4.6
October 30: Proof of Nash Theorem (conclusion). Models of duopoly. Peres, section 4.6, Ferguson, section III.3.
November 4: Feasible solutions for cooperative games. Ferguson, section III.4.1.
November 6: Cooperative games : solution for TU games, Nash solution of NTU games. Ferguson, sections III.4.2, III.4.3.
November 11: Shapley λ-transfers solution of NTU games. Ferguson, section III.4.3.
November 13: Games in Coalitional form. Relation to the strategic form. Constant sum games. Imputations and core. Ferguson, sections IV.1, IV.2.1, IV.2.3.
November 18: Essential games. Shapley Value: uniqueness. Ferguson, sections IV.2.2, IV.3.1, IV.3.2.
November 20: An Alternative form of Shapley value. Simple games. The Shapley-Shubik power index. Social choice and Arrow Theorem. Ferguson, sections IV.3.3, IV.3.4; Peres, sections 8.1, 8.2.
November 25: Arrow Theorem: examples and the proof. Peres, section 8.3.
November 27: Arrow Theorem: the proof. Final review. Peres, section 8.3.
Homework.
Assignment #1, due September 24.
Recommended problems (do not turn in!):
Ferguson, Part I, problems 1.5.1, 1.5.4, 1.5.8a, 2.6.2, 2.6.3.
Assignment #2, due October 1.
Recommended problems (do not turn in!):
Ferguson, Part I, problems 3.5.2, 3.5.3, 3.5.8; 4.5.1, 4.5.3.
Assignment #3, due October 8.
Recommended problems (do not turn in!):
Ferguson, Part II, problems 1.5.2, 1.5.3; 2.6.1, 2.6.2, 2.6.8.
Assignment #4, due October 15.
Recommended problems (do not turn in!):
Ferguson, Part II, problems 2.6.4, 2.6.9; 3.7.2, 3.7.4, 3.7.8.
Assignment #5, due November 5.
Recommended problems (do not turn in!):
Ferguson, Part III, problems 1.6.1, 1.6.2; 2.6.4, 2.6.5, 2.6.6.
Assignment #6, due November 12.
Recommended problems (do not turn in!):
Ferguson, Part III, problems 3.5.1, 3.5.4, 3.5.6, 4.5.1, 4.5.2.
Assignment #7, due November 19.
Recommended problems (do not turn in!):
Ferguson, Part III, problems 4.5.3, 4.5.4, 4.5.5, 4.5.6.
Assignment #8, due November 26.
Recommended problems (do not turn in!):
Ferguson, Part IV, problems 1.5.1, 1.5.4, 2.5.1, 2.5.8, 3.5.3.
Midterm Test. There will be an in-class midterm test on Thursday, 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.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. The final exam is on December 8, 9-11 am, at Gym A/B. 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.3.5.2, IV.3.5.7.
Spring Final Exam.
Additional office hours: Thursday, December 4, 10-12.
Grading. Grades will be based on eight homework assignments (4% each), Midterm test (30%), and Final exam (38%). 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 is due but 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.
Academic Integrity.
Honesty and fairness are fundamental to the University of Toronto’s mission. Plagiarism is a form of academic fraud and is treated
very seriously. The work that you submit must be your own and cannot contain anyone elses work or ideas without proper
attribution. You are expected to read the handout How not to plagiarize (http://www.writing.utoronto.ca/advice/using-sources/hownot-
to-plagiarize) and to be familiar with the Code of behaviour on academic matters, which is linked from the UTM calendar under
the link Codes and policies.