## 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

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

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

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

Lecture 4 (9/2/21)
covered material: equalizing payoffs, domination

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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