Schedule of Lectures
- 9/8:
- 9/13:
-
Lecture: Finishing von Neumann-Morgenstern Theorem.
Normal-form games. Basic solution concepts. Zero-sum games.
-
Reading: Chapter 1.1-1.4 of the AGT book.
- 9/15:
-
Lecture: Nash Equilibrium, correlated Nash. Examples.
-
Reading: Handout on linear programming.
- 9/20:
-
Lecture: Von Neumann's minimax theorem. Brief review of linear programming. Yao's minimax principle (if time allows).
-
Reading: Handouts on probability theory and probabilistic methods.
- 9/22:
-
Lecture: Mechanism design basics.
-
Reading: Chapter 9.1, 9.3 and 9.4 from the AGT book.
- 9/27:
-
Lecture: VCG mechanisms. Combinatorial auctions.
-
Reading: Chapter 11.1, 11.3, 11.5 from the AGT book.
- 9/29:
-
Lecture: Configuration LP. Walrasian equilibrium.
-
Reading: Handout on LP relaxations and integrality gap.
- 10/4:
- 10/6:
- 10/11:
10/13, 10/18, 10/20:
10/25:
10/27, 10/29, 11/1:
-
Lecture:
Characterization of BNE in single item auctions.
Revelation Principle.
Revenue equivalence.
Myerson's revenue optimal auctions for regular value distributions.
-
Reading: Chapter 3.2-3.3.3 of Jason Hartline's book.
-
Optional: Chapter 9.5.6, 9.6 of the AGT book.
In class, we derived the payment identity using the Envelope Theorem. If you had difficulty following that argument, you may refer to Chapter 9.5.6 of the AGT book, where an essentially equivalent proof is given.
For a careful treatment of the envelope theorem with rather relaxed assumptions on the smoothness of the functions involved, refer to this paper by Paul Milgrom and Ilya Segal.
11/3, 11/8:
-
Lecture: Revenue curves. Bulow and Roberts' interpretation of Myerson's auction.
-
Reading: Chapter 3.3.4, 3.3.5, 5.1, 5.2.1, 5.3.1 of Jason Hartline's book.
11/10:
-
Lecture: Bulow and Klemperer. Prior-indenpendent auctions. The Lookahead auction.
-
Reading: Chapter 5.1, 5.2.1, 5.3 of Jason Hartline's book.
11/15:
-
Lecture: Consequences of the lookahead auction: Second price auctions with lazy monopoly reserves; second price auction with randomly sampled reserves.
-
Reading: My lecture notes.
-
Optional: Chapter 4.1 of Jason Hartline's book.
11/17:
-
Lecture: Sequential Posted Pricings and Correlation Gap.
-
Reading: Chapter 5.3 of Jason Hartline's book.
11/22:
-
Lecture: Review Myerson, revenue curves and ironing. Concept of Price of anarchy. Utility games.
-
Reading:
My lecture notes.
Chapter 17 and Chatper 19.4 of the AGT book. (Chapters 17.2.2-17.2.4 and Chapter 19.4.5 are optional.)
11/24, 11/29:
-
Lecture: Finishing PoA for facility location games. Price of anarchy of first price auctions. Smooth games. Extension theorem.
-
Reading: My lecture notes.
12/1:
-
Lecture: Composability theorem. Simultaneous first price auctions for XOS and subadditive bidders. Its optimality among all auctions with subexponential communications (sketch).
-
Reading: Sections 5 and 6 of my updated lecture notes.
-
Optional: Tim Roughgarden's lecture notes on lower bounding the PoA of any auctions using subexponential communication.