STAT 473 - Game Theory
University of Illinois at Chicago
Fall 2021

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
Time and location: T, R 9:30AM-10:45AM hybrid Taft Hall 207 and online
Instructor: Lev Reyzin, SEO 417
Instructor office hours: M 10:00AM-10:50AM in SEO 417, R 8:30AM-9:20AM online
Textbook: Anna Karlin and Yuval Peres Game Theory, Alive (also available free online)
Piazza: link
Gradescope: link

Exam Dates

Midterm exam: Tuesday, October 26th (scheduled for 9:30AM-10:45AM, during classtime)
note: midterm exam covers material pertaining to 2.1-2.5 and 4.1-4.6 of the textbook
Final exam: Wednesday, December 8th (scheduled for 10:30AM-12:30PM)

Problem Sets

problem set 1 due 9/21/21
problem set 2 due 10/14/21
problem set 3 due 11/9/21
problem set 4 due 11/23/21
problem set 5 due 12/2/21

Lectures and Readings

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

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

Lecture 2 (8/26/21)
covered material: introduction to zero-sum games, payoff guarantee inequality
reading: 2.1

Lecture 3 (8/31/21)
covered material: safety strategies, minimax theorem
reading: 2.2 - 2.3

Lecture 4 (9/2/21)
covered material: equalizing payoffs, domination
reading: 2.4.1 - 2.4.3

Lecture 5 (9/7/21)
covered material: proof of minimax theorem via linear programming (LP), video by Tim Roughgarden (asynchronous)
optional reading: 2.6

Lecture 6 (9/9/21)
covered material: submarine salvo, Nash equilibria in zero-sum games
reading: 2.4.4, 2.5

Lecture 7 (9/14/21)
covered material: general-sum games, Prisoner's dilemma, Stag hunt, other examples
reading: 4.1

Lecture 8 (9/16/21)
covered material: Nash's theorem and proof, video by Sanjoy Das (asynchronous)
optional reading: 5.1

Lecture 9 (9/21/21)
covered material: went over problem set 1

Lecture 10 (9/23/21)
covered material: Nash equilibria in general-sum games
reading: 4.2

Lecture 11 (9/28/21)
covered material: general-sum games with more than two players, Nash equilibria in many-player games
reading: 4.3

Lecture 12 (9/30/21)
covered material: potential games, with conjection game example
reading: 4.4

Lecture 13 (10/5/21)
covered material: evolutionary game theory, evolutionarily stable strategies, population invasion
reading: 7.1

Lecture 14 (10/7/21)
covered material: correlated equilibria, battle of the sexes, chicken revisited
reading: 7.2

Lecture 15 (10/12/21)
covered material: infinite games, tragedy of commons, market for lemons, assymetric information
covered material 4.5-4.6

Lecture 16 (10/14/21)
covered material: introduction to extensive form, line-item veto, mutually assured destruction
reading: begin 6.1

Lecture 17 (10/19/21)
covered material: backwards induction, subgame-perfect NE, behavioral strategies
reading: finish 6.1

Lecture 18 (10/21/21)
covered material: extensive-form games of imperfect information, chicken revisited, centepede
reading: 6.2

Lecture 19 (10/26/21)
covered material: midterm exam, no lecture

Lecture 20 (10/28/21)
covered material: went over midterm

Lecture 21 (11/2/21)
covered material:games of incomplete information, Bayesian games in extensive form, signaling
reading: 6.3.1 - 6.3.2

Lecure 22 (11/4/21)
covered material: signaling, zero-sum games in extensive form
reading: 6.3.2 - 6.3.4

Lecture 23 (11/9/21)
covered material: repeated games with discounting, Tit-for-Tat
reading: 6.4.1

Lecture 24 (11/11/21)
covered material: went over problem set 3

Lecture 25 (11/16/21)
covered material: intro to combinatorial games as sepcial case of extensive form games, subtraction game
reading: 1.1 up to (but not including) 1.1.1

Lecture 26 (11/18/21)
covered material: chomp, partisan games, tic-tac-toe, hex, strategy stealing again
reading: 1.2

Lecture 27 (11/23/21)
covered material: computational aspects of combinatorial games, AlphaGo
optional reading: a blog post by Demis Hassabis

Lecture 28 (11/30/21)
covered material: went over problem set 4

Lecture 29 (12/2/21)
covered material: went over problem set 5, final exam review