**Fall 2017**

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

**Class Location & Time**: *Tue, 11:00 AM - 1:00 PM;* IB240 and *Thu, 11:00 AM - 12:00 PM;* IB345

**Tutorials: ***Wed 5:00 PM- 6:00 PM*, IB250.

**Instructor: **Ilia Binder (ilia@math.toronto.edu), DH3026.

**Office Hours: ***Tue and Thu 10:00 AM-11:00 AM*

**Teaching Assistant: ** James Belanger, (james.belanger@mail.utoronto.ca).

**Office Hours: ** *Wed, 3.30-4.30pm; DH2027 (Math Help room).*

**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:* The introduction. Definition of an impartial combinatorial game. Impartial and partisan games. N- and P- positions.

**Homework.**

*Assignment #1, due September 20.*

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 27.*

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 4.*

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 18.*

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 8.*

Recommended problems (do not turn in!):
Ferguson, Part III, problems 1.6.1, 1.6.2; 2.5.4, 2.5.5, 2.5.6.

*Assignment #6, due November 15.*

Recommended problems (do not turn in!):
Ferguson, Part III, problems 3.5.1, 3.5.4, 3.5.6.

*Assignment #7, due November 22.*

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 29.*

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.

**Bonus Problems.**

- 2017.09.13
- The bonus problem about the winning positions in Misere Nim is solved.
- 2017.09.14
- The bonus problem about the mistake on the board is solved.
- 2017.10.04
- The bonus problem about the characterization of convex sets by convex combinations is solved.
- 2017.10.19
- The bonus problem about an unusual subtraction set is solved.

**Midterm Test. **There will be an in-class midterm test on Tuesday, October 24. 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, 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.

**Final exam. **
The final exam will be held on Saturday, December 9, 5-7pm, at IB110. 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:* Tuesday, December 5, 11 - 1. Location: DV-2094A.

*Additional office hours by TA:* Friday, December 8, 1 - 2 pm, DH2027 (Math Help room).

**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.

**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.