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 |
|
| Tue, Feb 25 | Imperfect information; elicitation |
|
| Resources | ||
| Thu, Feb 27 | Information elicitation |
HW03 due; HW04a posted |
| Resources | blog posts on property elicitation and finite properties |
|
| Tue, Mar 4 | Elicitation continued |
HW04b posted |
| Resources | blog posts on property elicitation and finite properties |
|
| Thu, Mar 6 | Prediction Markets |
|
| Resources | blog post on prediction markets and cost-function markets |
|
| Tue, Mar 11 | Prediction Markets, continued |
HW04 due |
| Thu, Mar 13 | Information and Common Knowledge |
Project proposals due |
| Resources | Notes on information structures, Common knowledge post from Aaronson |
|
| Tue, Mar 18 | Mechanism design, auctions, VCG |
|
| Resources | Hartline Ch. 1, Ch. 3 |
|
| Thu, Mar 20 | Incentive compatibility, revelation, truthfulness |
HW05a posted |
| Resources | Hartline Ch. 2, Ch. 3 |
|
| Tue, Apr 1 | Single-paramter settings |
|
| Resources | Hartline Ch. 2, Ch. 3 |
|
| Thu, Apr 3 | Revenue, Myerson auction |
Project update due |
| Resources | Hartline Ch. 3 |
|
| Thu, Apr 3 | Bayesian approximation, smoothness, PoA |
|
| Resources | Hartline Ch. 4 |
|
| Tue, Apr 8 | Prior-free approximation, Bulow-Klemperer |
Hw05 due |
| Resources | Hartline Ch. 5 |
|