Instructor: Bo Waggoner
Time: Tu/Th 11:00-12:15
Location: Discovery Learning Center 1B20 (in-person modality)
Office hours: Thu 12:15-13:30, ECCS 111 (knock loudly).
Summary: This advanced graduate-level course will cover foundations and select advanced topics in Algorithmic Economics and Algorithmic Game Theory. Likely topics include game theory, equilibrium, algorithms for game playing and computational complexity thereof, mechanism design and auction theory, voting theory and computational social choice.
Prerequisites: The course will be theoretical, mathematical, and proof-based. Preprequisites strongly encouraged include multivariable calculus, linear algebra, and probability; as well as undergraduate algorithms and complexity theory. No economic prerequisites are assumed, but some familiarity with game theory and/or microeconomics is beneficial.
| Tue, Jan 14 | Introduction, utility theory, game theory |
|
| Resources | Notes on decision theory; Notes on game theory; Osborne and Rubinstein Ch 1; Ch 2.1-2.3; vN+M utility theorem discussed in class; risk aversion |
|
| Thu, Jan 16 | Solution concepts, computing equilibria, PPAD |
HW01-01, HW01-02 |
| Resources | Notes on game theory; Osborne and Rubinstein Ch 3.1-3.2, Ch 4; Roughgarden notes; Lipton, Markakis, Mehta |
|
| Tue, Jan 21 | Best-response dynamics and congestion games |
HW01-03 |
| Resources | ||
| Thu, Jan 23 | Online no-regret learning |
|
| Resources | lecture notes on no-regret learning; Arora, Hazan, Kale. The Multiplicative Weights Update Method:A Meta-Algorithm and Applications. Theory of Comp., 2012 (survey paper). |
|
| Tue, Jan 28 | Zero-sum games |
HW01 due on Gradescope, HW02a assigned |
| Resources | ||
| Thu, Jan 30 | Correlated equilibria and learning |
HW02b assigned |
| Resources | Penn lecture notes on correlated equilibrium and relation to online learning |
|
| Tue, Feb 04 | Calibrated predictions and online learning |
|
| Resources | ||
| Thu, Feb 06 | Blackwell approachability |
|
| Resources | MIT lecture notes on approachability; Kroer lecture notes, Abernethy lecture notes |
|
| Tue, Feb 11 | Blackwell approachability, cont'd |
HW02 due |
| Thu, Feb 13 | Extensive-form games |
HW03a assigned |
| Resources | Osborne and Rubinstein Ch. 6.1 and 6.2; Kroer lecture notes; Chen slides |
|
| Tue, Feb 18 | Extensive-form games and repeated games |
HW03b assigned |
| Resources | Osborne and Rubinstein Ch. 8.6; Leyton-Brown slides |
|
| Thu, Feb 20 | Extensive-form games of imperfect information |
|
| Resources | Osborne and Rubinstein Ch. 11.1, 11.2; Chen slides |
|