MAT406H5F Mathematical Introduction to Game Theory

Fall 2019

Web page: http://www.math.toronto.edu/ilia/MAT406.2019/.

Class Location & Time: Tue, 11 AM - 1 PM; Thu, 11 AM - 12 PM; DH4001

Tutorials: Wed 5 PM- 6 PM, IB385

Instructor: Ilia Binder (ilia@math.toronto.edu), DH3026.
Office Hours: Tue and Thu, 10 AM-11 AM

Teaching Assistant: Eric Ramalheiro, (eric.ramalheiro@mail.utoronto.ca).
Office Hours:  Tue 3-4 PM, DH2034.

Required Text: Anna R. Karlin and Yuval Peres. Game Theory, Alive.  American Mathematical Society, 2017).

Thomas S. Ferguson. Game Theory. http://www.math.ucla.edu/~tom/Game_Theory/Contents.html

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. We will also carefully discuss the Sprague-Grundy value. After a brief discussion of partisan combinatorial games, we will talk about 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 5: An introduction: preview of "coming attractions".
September 10: Impartial and partisan games. N- and P- positions. The games of Chomp! and Nim. Nim-sum.Bouton's Theorem. Karlin-Peres, section 1.1.1; Ferguson, sections I.1, I.2.1, I.2.2.
September 13: Bouton's theorem. Misere Nim. Sprague-Grundy function. Karlin-Peres, section 1.1.2; Ferguson, sections I.2, I.3.
September 17: Sum of combinatorial games. Sprague-Grundy theorem. Lasker's game. Partisan games. Ferguson, section I.4.
September 19: Partizan games. The game of Hex. Karlin-Peres, section 1.2.1.
September 24: Zero-sum games: examples and definition, strategic form, geometric properties of the set of mixed strategies. Von Neumann Theorem, response to a fixed strategy. Karlin-Peres, sections 2.1, 2.2, 2.3; Ferguson, sections II.1.1, II.1.2, II.1.3, II.1.4.
September 26: Saddle points. Proof of von Neumann Theorem for 2x2 games. Karlin-Peres, sections 2.3, 2.4.1; Ferguson, sections II.2.1, II.2.2.
October 1: The Separation Theorem. Von Neumann Theorem: proof of the 2x2 case and in general. 2xm and nx2 games. Domination. Karlin-Peres, sections 2.4.3, 2.6; Ferguson, sections II.2.3, II.3.5, II.2.3, II.2.4.
October 3: Domination. Symmetric games. The Principle of Indifference. Karlin-Peres, section 2.4.3; Ferguson, sections II.2.3, II.3.1, II.3.5.
October 8: The Principle of Indifference. Use of symmetry. Poker-like games. Kuhn tree. Converting games given in Extensive form to matrix form. Karlin-Peres, sections 2.4.3, 2.4.4; Ferguson, sections II.3, II.5.
October 10: Converting Poker-like games to the strategic form. Ferguson, section II.5.
October 22: General sum games: definition, strategic and extensive form, safety levels, Nash equilibrium. Mixed Nash equilibria. Finding Nash equilibria for 2x2 games. Ferguson, sections III.1, III.2.1, III.2.2; Karlin-Peres, sections 4.1, 4.2.
October 24: Midterm review.
October 29: Midterm.
October 31: Proof of Brouwer Fixed point theorem using Game of Hex. Karlin-Peres, section 5.1.
November 5: Proof of Nash Theorem for two players. Methods for finding Nash Equilibria. Cournot's model of Duopoly. Ferguson, sections III.2.3, III.2.4, III.3.1; Karlin-Peres, section 5.1.
November 7: Bertrand and Stackeleberg models of Duopoly. Cooperative games: feasible payoffs. Pareto-optimal payoffs. Ferguson, sections III.3.2, III.3.3, III.4.1.
November 12: Solving TU games, Nash solution of NTU games. Ferguson, sections III.4.2, III.4.3.
November 14: Shapley λ-transfers solution of NTU games. Ferguson, section III.4.3.
November 19: Games in Coalitional form. Relation to the strategic form. Constant sum games.Imputations and core. Essential games. Karlin-Peres, section 12.1, 12.2; Ferguson, sections IV.1, IV.2.
November 21: Shapley Value. Karlin-Peres, section 12.3; Ferguson, sections IV.3.
November 26: Shapley Value. Shapley-Shubik power index. Voting mechanisms. Arrow's fairness criteria. Arrow Theorem: examples. Karlin -Peres, sections 12.3, 13.1, 13.2, 13.3, 13.6; Ferguson, section IV.3.
November 28: Arrow Theorem: the proof. Karlin-Peres, section 13.7.
December 3: Proof of Arrow Theorem. Final review. Karlin-Peres, section 13.7.

Homework.

Assignment #1, due September 18.
Recommended problems (do not turn in!): Ferguson, Part I, problems 1.5.1, 1.5.4, 1.5.8a, 2.6.2a,b, 2.6.3.

Assignment #2, due September 25.
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 2.
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 9.
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 October 23.
Recommended problems (do not turn in!): Ferguson, Part II, problems 3.7.5, 3.7.11, 3.7.13, 5.9.2, 5.9.4.

Assignment #8, due November 28.
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.

Assignment #6, due November 13.
Recommended problems (do not turn in!): Ferguson, Part III, problems 2.6.4, 2.6.9, 3.5.1, 3.5.4, 3.5.6, 3.7.2, 3.7.4, 3.7.8.

Assignment #7, due November 20.
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 27.
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 a two-hour in-class midterm test on Tuesday, October 29. No aides are allowed for this test.
The test will cover combinatorial games, zero-sum games, and the basic theory of general sum games. The material roughly corresponds to the first two chapters, as well as sections III.1.1-1.5, III.2.1-3 of the Ferguson textbook.
Recommended preparation (do not turn in): all homework problems, including the recommended 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, III.1.6.1, III.1.6.2,III.2.5.5.

Final exam. The final exam will be held on Tuesday, December 10, 9-11 am, at GYM C. 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.
Last year Final Exam.
Additional office hours: Thursday, December 5, 1 - 2 pm. Location: DH4001.
Additional TA office hours: Monday, December 9, 10 am - 12 pm. Location: DH2034.

Grading. Grades will be based on eight homework assignments (3% each), Midterm test (31%), and Final exam (45%). 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.

E-mail policy.
E-mails must originate from a utoronto.ca address and contain the course code MAT406 in the subject line. Please include your full name and student number in your e-mail.

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/how-not-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.