ECON 473 / 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.

Basic Information

Syllabus: pdf (due to COVID-19, classes and office hours have moved online and the final exam is now take-home)
Time and Location: T, R 9:30-10:45am A003 Lecture Center A (LCA) moved online due to COVID-19
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 moved online due to COVID-19
TA: Alexander Berenbeim
TA Office Hours: T 12:00-1:00 PM in MSLC, R 2:00-3:00 PM in SEO 609 moved online due to COVID-19
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 open-book take-home exam due to COVID-19. It will be given by end of day 5/4 and due by end of day 5/6.

Take-Home Final Exam

final exam due by 11:59pm (CDT) on 5/6/20.

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
problem set 4 due 4/17/20
problem set 5 due 5/1/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
optional reading: 5.1
note: students are not responsible for this material

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

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

Online Lecture 22 (4/2/20)
covered material: games of imperfect information
reading: 6.2

Online Lecture 23 (4/7/20)
covered material: Bayesian games of incomplete information, signaling
reading: 6.3 through the end of 6.3.2

Online Lecture 24 (4/9/20)
covered material: zero-sum extensive form games, repeated games
reading: finish 6.3, 6.4.1

Online Lecture 25 (4/14/20)
covered material: introduction to evolutionary game theory, evolutionarily stable strategies, population invasion
reading: 7.1
optional reading: Effective and More Effective Choice in the Prisoner's Dilemma by Robert Axelrod

Online Lecture 26 (4/16/20)
covered material: correlated equilibria, battle of the sexes, chicken revisited
reading: 7.2

Online Lecture 27 (4/21/20)
covered material: detailed solutions to problem set 4

Online Lecture 28 (4/23/20)
covered material: the price of anarchy, selfish routing, and the Braess paradox
optional reading: 8.1

Online Lecture 29 (4/28/20)
covered material: social choice, Arrow's theorem, and Vickrey (second-price) auctions
optional reading: 13 (up to Thm 13.3.1), 14.2

Online Lecture 30 (4/30/20)
covered material: final exam review
other: a reminder that the final (take-home) exam will be given by 5/4 (end of day) and due by end of day on 5/6