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 810. Optional: Sections 7, 1113). 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. Swapregret 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 13 and Section 4.2.
For basic matroid theory, read
Lecture notes by Michel Goemans.