STAT 473 - Game Theory
University of Illinois - Chicago
Spring 2020

This course serves as a rigorous introduction to game theory. We will cover static and dynamic games, pure and mixed strategies, and and situations with perfect and imperfect information. We will cover the foundationa theorems, including the celebrated von Neumann's minimax and Nash's equilibrium theorems. We will also consider economic, political, and biological applications.

This course is cross-listed with ECON 473.

Basic Information

Syllabus: pdf
Time and Location: T, R 9:30-10:45am, A003 Lecture Center A (LCA) moving online
Instructor: Lev Reyzin, SEO 418, (312)-413-3745
Instructor Office Hours: T 11:00-11:50 AM, F 1:00-1:50 PM in SEO 418 moving online
TA: Alexander Berenbeim
TA Office Hours: T 12:00-1:00 PM in MSLC, R 2:00-3:00 PM in SEO 609 moving online
Textbook: Anna Karlin and Yuval Peres Game Theory, Alive (also available free online)

Exam Dates

Midterm: Thursday, March 12th, 9:30 AM - 10:45 AM
Final Exam: Wednesday, May 6th, 10:30 AM - 12:30 PM

Problem Sets

problem set 1 due 1/31/20
problem set 2 due 2/14/20 2/17/20
problem set 3 due 3/10/20

Lectures and Readings

Note: lectures will have material not covered in the readings.

Lecture 1 (1/14/20)
covered material: intro to the course, discussion of what are games
reading: preface

Lecture 2 (1/16/20)
covered material: begin combinatorial ganes, impartial games, subtraction game and chomp, strategy stealing
reading: 1.1 upto (but not including) 1.1.1

Lecture 3 (1/21/20)
covered material: partisan games, tic-tac-toe, hex, strategy stealing again
reading: 1.2 upto the end of 1.2.1

Lecture 4 (1/23/20)
covered material: introduction to zero-sum games, payoff guarantee inequality
reading: 2.1

Lecture 5 (1/28/20)
covered material: mixed strategies and expected payoffs, example of expected payoff guarantee
reading: 2.2

Lecture 6 (1/30/20)
covered material: safety strategies, minimax theorem, dominating strategies
reading: 2.3, begin 2.4

Lecture 7 (2/4/20)
covered material: saddle points, equalizing payoffs, Nash equilibria, paradox of extra information
reading: finish 2.4, 2.5

Lecture 8 (2/6/20)
covered material: proof of von Neumann's minimax theorem
optional reading: 2.6

Lecture 9 (2/11/20)
covered material: the Gale-Shalpley algorithm and properties of stable matchines (guest lecture by Anastasios Sidiropoulos)
reading: 10.1 - 10.3

Lecture 10 (2/13/20)
covered material: Nash Equilibria for general-sum games, principle of indifference
reading: 4.1, begin 4.2

Lecture 11 (2/18/20)
covered material: more examples of general-sum games
reading: finish 4.2

Lecture 12 (2/20/20)
covered material: introduction to general-sum games with more than two players
reading: begin 4.3

Lecture 13 (2/25/20)
covered material: Nash equilibria in general-sum games, symmetric games and equilibria
reading: finish 4.3 (including 4.3.1)

Lecture 14 (2/27/20)
covered material: the conjestion game and potential games
reading: 4.4

Lecture 15 (3/3/20)
covered material: consensus game, tragedy of commons, market for lemons
reading: 4.5, 4.6

Lecture 16 (3/5/20)
covered material: complexity of computing approximate Nash equilibria (guest lecture by Anastasios Sidiropoulos)
optional reading: this paper by Daskalakis et al. (2008)

Lecture 17 (3/10/20)
covered material: midterm review
other: a reminder that the midterm exam is on Thursday!

Lecture 18 (3/12/20)
midterm exam: no lecture

(Cancelled) Lecture 19 (3/17/20)
cancelled due to COVID-19: proof of Nash's theorem (students are not responsible for this material)
optional reading: 5.1

(Cancelled) Lecture 20 (3/19/20)
cancelled due to COVID-19: fixed point theorems (students are not responsible for this material)
optional reading: 5.2

(Online) Lecture 21 (3/31/20)
covered material: introduction to extensive form games
reading: 6.1