CS364B: Frontiers in Mechanism Design (Winter 2014)
Roughgarden (Office hours: After class and by appointment.)
- Okke Schrijvers
(Office hours: Tuesdays 3-5 PM, in Gates 463A.
Email: okkes "at" stanford.edu)
2:15-5 PM on Wednesdays in Hewlett 103.
Piazza site: here
Advanced topics in mechanism design. Possible topics include
ascending auctions and other indirect mechanisms; Bayes-Nash
equilibrium analysis; the price of anarchy in simple auctions;
correlated and interdependent valuations; black-box reductions in
algorithmic mechanism design; revenue maximization in multi-parameter
All students are required to complete weekly exercise sets, which fill
in details from lecture.
Students taking the course for a letter grade are also required to
complete a course project, which involves synthesizing recent research
papers and/or working on open research problems (details TBA).
No late assignments accepted.
Lecture videos and notes
Schedule and references:
PART I: WELFARE MAXIMIZATION: TRACTABLE SPECIAL CASES AND ASCENDING
- Lecture 1 (Wed 1/8): Ascending auctions. EPIC vs. DSIC implementations.
- Lecture 2 (Wed 1/8): Unit-demand bidders.
Walrasian equilibria. Characterization of VCG payments.
- Lecture 3 (Wed 1/15):
Crawford-Knoer auction for unit-demand bidders. Convergence to smallest
Walrasian equilibrium. EPIC guarantee.
- Lecture 4 (Wed 1/15):
Multi-unit auctions with downward-sloping valuations.
Ausubel's clinching auction.
- Lecture 5 (Wed 1/22):
Gross substitutes: definition, examples, and existence of Walrasian
- Lecture 6 (Wed 1/22):
Walrasian equilibria exist if and only if the configuration LP
relaxation is exact. Representations of valuation functions.
Polynomial-time welfare maximization with gross substitutes
- Bonus Lecture (Fri 2/7):
Gross substitutes valuations and greedy algorithms.
PART II: DSIC APPROXIMATION MECHANISMS FOR NP-HARD CASES
- Lecture 7 (Wed 1/29):
Final comments on gross substitutes valuations (see last section of
the Lecture 5 notes).
Introduction to and goals for Part II of the course.
Welfare maximization with submodular valuations.
- Lecture 8 (Wed 1/29):
and maximal-in-distributional-range (MIDR) mechanisms.
Multi-unit auctions with general monotone valuations.
with multiple copies of each item.
- AGT book, Section 12.3.
- Dughmi, Randomization and Computation in Strategic Settings, PhD Thesis, 2011,
Sections 3.3.1, 3.3.2, 3.4.1, 3.4.2.
- Nisan, Algorithmic Mechanism Design:
Through the lens of Multi-unit auctions, 2014, Section 5.3.
Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs, Combinatorica, 1987. (See Section 4.)
- Lecture 9 (Wed 2/5):
MIDR mechanisms via scaling algorithms. DSIC (1-epsilon)-approximation
for general valuations with logarithmic supply.
- Lecture 10 (Wed 2/5):
MIDR mechanisms via convex rounding. DSIC .63-approximation
for converage valuations.
PART III: BETTER GUARANTEES FOR WEAKER SOLUTION CONCEPTS
- Lecture 11 (Wed 2/12):
Brief comments on impossibility results for DSIC implementations
(see Lecture 10 notes).
The shrinking auction for single-value unknown multi-minded bidders.
- Lecture 12 (Wed 2/12):
Finish analysis of the shrinking auction (see Lecture 11 notes).
Bayes-Nash equilibria and Bayesian incentive compatible mechanisms.
Introduction to black-box reductions (see Lecture 13 notes).
- Lecture 13 (Wed 2/19):
Black-box reduction from BIC mechanism design to
approximation algorithm design.
PART IV: THE PRICE OF ANARCHY IN SIMPLE AUCTIONS
- Lecture 14 (Wed 2/19):
Simultaneous second-price auctions with submodular and XOS valuations.
- Lecture 15 (Wed 2/26):
The Bayes-Nash POA of simultaneous second-price auctions.
- Lecture 16 (Wed 2/26):
The Bayes-Nash POA of first-price auctions.
- Lecture 17 (Wed 3/5):
The Bayes-Nash POA of uniform-price auctions with downward-sloping
valuations. Subadditive valuations and bypassing smoothness arguments.
PART V: MULTI-PARAMETER REVENUE MAXIMIZATION
- Lecture 18 (Wed 3/5):
Recap of single-parameter revenue-maximization. Multi-parameter
challenges. A linear programming formulation of the optimal mechanism.
- Lecture 19 (Wed 3/12):
Interim allocation rules and Border's theorem.
- Lecture 20 (Wed 3/12):
Structure of optimal multi-parameter mechanisms.