Schedule of Lectures
- 9/7:
- 9/12,14 :
- 9/19:
-
Lecture: Linear programming and duality, von Neumann's minimax theorem.
-
Reading: Handout on linear programming (Sections 8-10. Optional: Sections 7, 11-13). Our treatment of strong duality follows these notes more closely.
- 9/21, 9/26:
-
Lecture: Online learning and the Hedge algorithm; alternative proof of von Neumann's minimax theorem.
-
Reading: Week 1 and week 2 of Bobby Kleinberg's lecture notes.
- 9/28:
-
Lecture: Convergence to coarse correlated equilibria. Swap-regret minimization.
-
Reading: Section 4.4.3 and 4.5 of Avrim Blum and Yishay Mansour's survey (Chapter 4 of the book Algortihmic Game Theory).
-
Optional: Survey on the Hedge Algorithm by Sanjeev Arora, Elad Hazan and Satyen Kale.
10/3, 10/5:
10/10:
-
Lecture: Basic auctions, VCG mechanisms
-
Reading: Section 1.3 of Introduction to Mechanism Design (for Computer Scientists)
-
Optional reading: The Lovely but Lonely Vickrey Auction by Lawrence Ausubel and Paul Milgrom for a discussion of disadvantages of the VCG mechanisms in practice.
10/12:
10/17:
10/19:
10/24: No lecture.
10/26:
10/31:
-
Lecture: Ironing.
-
Reading:
My notes. (Section 3 is optional)
11/2, 11/7, 11/9:
-
Lecture: Revenue curves. Interim feasibility.
-
Reading:
For Border's inequalities, read
my notes.
For introduction to submodular functions, read Section 1 of
notes by Jan Vondrak.
For submodular minimization, read Section 1.1 and 1.2 of
notes by Jan Vondrak.
11/14:
-
Lecture: Ex post implementation, the greedy algorithm for polymatroids. Price of anarchy.
-
Reading: Section 3 of
my notes.
Chapter 17 of the AGT book. (The parts after 17.2.1 are optional.)
11/16:
-
Lecture: Price of anarchy, congestion games, PoA of first price auctions.
-
Reading:
Chapter 17 of the AGT book. (The parts after 17.2.1 are optional.)
11/21:
-
Lecture: Smooth games, extension theorem.
-
Reading:
My notes. (Sections 3, 5 and 6 are optional.)
Optional: Survey by Tim Roughgarden, Vasilis Syrgkanis and Eva Tardos.
11/23, 11/28:
-
Lecture: Prophet inequalities. Matroid basics.
-
Reading:
Survey by Brendan Lucier, Sections 1-3 and Section 4.2.
For basic matroid theory, read
Lecture notes by Michel Goemans.