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's survey 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