Game Theory

Game theory is the study of strategic interaction. It has been applied to every scientific discipline -- most notably economics, but also political science, business, military, biology, and many others. Recently it has been a major area of research in computer science, as the field of artificial intelligence, which initially studied settings with a single agent, is expanding its scope to domains with multiple strategic (and potentially adversarial) agents. Topics will include game representations, solution concepts, imperfect information, repeated games, learning, auctions, and voting. There will be a project to pursue an application (or theoretical topic) of interest. The class could be of interest to students in computer science, mathematics, physical sciences, business, social sciences, engineering, and life sciences (including medicine). It would be helpful to have familiarity with mathematical proofs, and some problems will involve computational implementation.

**Professor**: Sam Ganzfried

Game Theory by Michael Maschler, Eilon Solan, and Shmuel Zamir (main textbook)

Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations by Yoav Shoham and Kevin Leyton-Brown

Game Theory with Engineering Applications by Dario Bauso

**Background**: Students should be familiar with all the material in this document on mathematical proofs. The most closely related course is the Coursera Game Theory class (though this course will be very different). Students unsure of their background should register for that course (which can be done for free) and browse several of the lecture videos. Several of the exercises will use the Gambit and Game Theory Explorer software packages, and potential students are encouraged to explore them in advance as well.

**Project**: Students can apply a topic from the class to an application of interest (e.g., formulating a problem game-theoretically and computing/analyzing equilibrium strategies), study a new theoretical topic, or present a novel survey and discussion of recent literature on a topic (e.g., opponent modeling in security games, or medical applications of equilibrium computation). Ambitious original projects are encouraged even if they are not complete or successful. **Evaluation**: homeworks (every two weeks), midterm exam, final exam, class project

**Outline**:

1) Strategic-form games and solution concepts

-- pure vs. mixed strategies, dominance, best response, Nash equilibrium,

zero-sum games, minimax/maximin, evolutionarily stable strategies

2) Extensive-form games

-- game trees, relationship to strategic-form games, imperfect information,

perfect vs. imperfect recall, behavior strategies, Kuhn’s Theorem, sequence form

3) Algorithms/complexity

-- P/NP/PPAD, linear programming, two-player zero-sum formulation, Lemke-

Howson algorithm, support enumeration, Gambit and Game Theory Explorer

4) Equilibrium refinements

-- Subgame perfect equilibrium, backwards induction, trembling-hand perfect

equilibrium, sequential equilibrium, proper equilibrium

5) Repeated games

-- Finitely and infinitely repeated games, solution concepts, Folk Theorem

6) Learning in games

-- Fictitious play, no-regret algorithms, counterfactual regret minimization, robust

responses, opponent modeling and exploitation

7) Alternative solution concepts

-- Strategy commitment, Stackelberg equilibrium, correlated equilibrium

8) Generalized game representations

-- Stochastic games, continuous games, Bayesian games

9) Auctions

-- English/Dutch/sealed-bid/Vickrey auctions, equilibria, mechanism design

10) Social choice (voting)

-- Arrow’s Impossibility Theorem, Gibbard-Satterthwaite Theorem, majority/

Borda/Condorcet rules, range voting

11) Stable matching

-- Gale-Shapley algorithm, application to National Resident Matching Program

12) Applications to education, security, and medicine.

**Lectures:**

Lecture 1 (1/10)

-- assignment: read proof review document and Chapter 1 from Maschler textbook

Lecture 2 (1/12)

-- video, slides

-- assignment: read Ch. 4.1-4.7 from Maschler textbook

Lecture 3 (1/17)

-- assignment: read Ch. 4.8-4.15 from Maschler textbook

Lecture 4 (1/19)

-- video, slides

-- assignment: HW1 out due 1/31 (corrected on 1/28), read Ch. 5 from Maschler textbook

Lecture 5 (1/24)

-- video, slides

-- assignment: read Ch. 3 from Maschler textbook

Lecture 6 (1/26)

-- video, slides

-- assignment: read Ch. 4 from Shoham textbook

Lecture 7 (1/31)

-- video, slides

-- assignment: read Ch. 5 from Shoham textbook

Lecture 8 (2/7)

-- video, slides

-- assignment: read Game Theory Explorer document and slides,

and von Stengel and my surveys of equilibrium computation algorithms (optional)

Lecture 9 (2/9)

-- video, slides

-- assignment: HW2 out (due 2/21), read document on Gambit software

Lecture 10 (2/14)

-- video, slides

-- assignment: read Ch. 7 from Maschler textbook

Lecture 11 (2/16)

-- video, slides

-- assignment: read Ch. 13 from Maschler textbook

Lecture 12 (2/21)

-- video, slides

-- assignment: HW3 out (due 3/2), read Ch. 7 from Shoham textbook

Lecture 13 (2/23)

-- video, slides

Lecture 14 (3/2)

-- video, slides

Lecture 15 (3/7)

-- video, slides

Lecture 16 (3/9)

-- video, slides

-- assignment: Final Project out (due 4/20)

Lecture 17 (3/21)

-- video, slides

Lecture 18 (3/23)

-- video, slides

-- assignment: read Ch. 8 from Maschler textbook

Lecture 19 (3/28)

-- video, slides

-- assignment: read Ch. 4 from Bauso textbook, paper on algorithms and complexity of computing Stackelberg equilibrium, and survey of security games

Lecture 20 (3/30)

-- video, slides

-- assignment: read Ch. 10 from Bauso textbook, Ch. 6 from Shoham textbook,

and article on stochastic games

Lecture 21 (4/4)

-- video, slides

-- assignment: HW4 out (due 4/13), read Ch. 12 from Maschler textbook, papers on

application of equilibrium computation to medical treatment and on CFR-BR algorithm

Lecture 22 (4/6)

-- video, slides

-- assignment: read Ch. 21 from Maschler textbook

Lecture 23 (4/11)

-- video, slides

-- assignment: read Ch. 22 from Maschler textbook

Lecture 24 (4/13)

-- video, slides

-- assignment: read paper on National Resident Matching Program

Lecture 25 (4/18) (Project presentations: Abdullah, Harold, Daniel)

-- video, slides

Lecture 26 (4/20) (Project presentations: Mario, Amir, Efrain, Farzana, Mai, Bingqian)

-- video, slides