ECON 2099: Mechanism Design and Approximation
|Picasso's Bull, December 1945 -- January 1946.
Autumn, 2014, Harvard U.
Required Textbook: Hartline, Mechanism Design and Approximation, manuscript, 2014.
Lectures: MW 2:30-4pm, Sever Hall, room 202.
Instructor: Jason D. Hartline
Office Hours: Littauer 315, TBA.
Announcements and Discussion: http://piazza.com/harvard/fall2014/econ2099/home.
This course studies the design of mechanisms to mediate the
interaction of strategic individuals so that desirable outcomes are
attained. A central theme will be the tradeoff between optimality of
an objective such as revenue or welfare and other desirable properties
such as simplicity, robustness, computational tractability, and
practicality. This tradeoff will be quantified by a theory of
approximation which measures the loss of performance of a simple,
robust, and practical approximation mechanism in comparison to the
complicated and delicate optimal mechanism. The class focuses on
techniques for performing this analysis, economic conclusions, and
consequences for practice. The class will follow the textbook
manuscript at: http://jasonhartline.com/MDnA/.
Prerequisites: Prior experience with algorithms or
game theory is recommended.
Grading: 60% problem sets, 40% research project, 10% classroom participation (bonus).
Homework Policy: Homeworks are to be done in
pairs. Both students must contribute to the solution of all
problems. One copy of the assignment should be turned in with the
names of both students on it. Both students will receive the same
grade. You may consult the text book and course notes when answering
homework questions; you must not consult the Internet or research
- Week 1: Mechanism Design and Approximation Overview
- Topics: mechanism design, approximation, philosophy thereof, first-price auction, second-price auction, lottery, posted-pricings
- Reading: Chapter 1.
- Week 2: Equilibrium
- Topics: Bayes-Nash equilibirum, dominant strategy equilibrium, single-dimensional agents, BNE characterization, revenue equivalence, uniqueness, revelation principle, incentive compatibility.
- Reading: Chapter 2.
- Week 3: Optimal Mechanism Design
- Topics: single-dimensional mechanism design, surplus-optimal mechanism (VCG), revenue-optimal mechanism (Myerson), amortized analysis, virtual values, ironing, revenue curves, revenue linearity.
- Reading: Chapter 3.
- Week 4: Bayesian Approximation
- Topics: reserve pricing, posted pricing, prophet inequalities, correlation gap, matroids, monotone hazard rate distributions.
- Reading: Chapter 4.
- Week 5: Bayes-Nash Approximation
- Topics: first-price auction (asymmetric distributions), simultanious composiotion, "price of
anarchy", "smoothness" paradigms.
- Reading: TBA.
- Week 6: Prior-independent Approximation
- Topics: Bulow-Klemperer, single-sample mechanism, digital goods.
- Reading: Chapter 5.
- Week 7: Prior-free Approximation (Digital Goods)
- Topics: prior-free methodology, monopoly pricing, random sampling auction, profit extraction, lower bounds.
- Reading: Chapter 6, through Section 2.
- Week 8: Prior-free Approximation (General)
- Topics: envy-free pricing, reduction to digital goods, prior-free methodology, monopoly pricing, random sampling auction, profit extraction, lower bounds.
- Reading: Chapter 6, from Section 3.
- Week 9: Multi-dimensional Preferences (Optimization)
- Topics: single-agent pricing, revenue linearity, marginal revenue mechanism, interim feasibility, convex optimization.
- Reading: TBA.
- Week 10: Multi-dimensional Preferences (Approximation)
- Topics: unit-demand preferences, marginal revenue mechanism,
correlation gap, approximate revenue linearity, single-dimensional
representative environments, reduction to single-dimensional pricing.
- Reading: Chapter 7.
- Week 11: Computational Tractability
- Topics: approximation algorithms, greedy-by-value, BIC blackbox
reductions, payment computation.
- Reading: Chapter 8.