Instructor: Bo Waggoner
Time: Tu/Th 11:00-12:15
Location: Discovery Learning Center 1B20 (in-person modality)
Office hours: Thu 10:00-11:00, 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 |
|
| Resources | ||
| Thu, Jan 23 | Online no-regret learning |
|
| Resources | Penn lecture notes on Polynomial Weights (skip page 1); 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 |
| Resources | ||