Mechanism Design and Approximation
|Picasso's Bull, December 1945 -- January 1946.
By Jason D. Hartline
Copyright © 2011-2016
The text Mechanism Design and Approximation is based on a
graduate course that has been developed at Northwestern over the past
five years. It presents the classical theory of economic mechanism design and
introduces a new theory of approximation for mechanism design.
1-8.pdf] [chapters 9-10 coming soon; material from Bayesian Mechanism Design survey; chapters 6-7]
The reader may download
and make one copy of the text for personal use only, and not for
further distribution or posting elsewhere. You may link to this page: http://jasonhartline.com/MDnA/.
- 01/19/16: There is a new chapter on the design of optimal mechanisms for agents with multi-dimensional and non-linear preferences. It will be inserted between chapters 6 and 7 of the first-draft of April 2012 (becoming Chapter 8). [chapters 1-8.pdf] [ch8.pdf]
- 12/10/14: There is a new chapter on design and analysis of Bayes-Nash mechanisms (a.k.a., the price of anarchy). It will be inserted between chapters 5 and 6. [chX.pdf]
- 09/02/14: The second draft of Chapter 6 is available for download; Chapters 7-9 are coming soon. [chapters 1-6.pdf]
- 08/25/14: I will be teaching Econ 2099: Mechanism Design and Approximation at Harvard U. this Fall. Cambridge and Boston area students are encouraged to attend. Monday, Wednesday; 2:30-4pm; beginning Sept. 3.
- 07/27/14: I will be presenting a tutorial Bayesian Mechanism Design at AAAI in Quebec on the afternoon of July 28. It will cover Chapters 2-5.
[Part I: Classic BMD]
[Part II: Approximation in BMD]
- 10/01/13: Questions and feedback are helpful for improving the manuscript. Please provide feedback and ask questions through this form.
- 10/01/13: The second draft of Chapters 1-5 are available for download; Chapters 6-9 are coming soon.
- 09/23/13: An online self-study course based on this textbook is
running from September 23, 2013 to December 8, 2013.
- 09/01/13: The first draft (from April, 2012) of Chapters 1-8 can be found here.
Excerpt from Chapter 1: [ch1.pdf]
Our world is an interconnected collection of economic and
computational systems. Within such a system, individuals optimize
their actions to achieve their own, perhaps selfish, goals; and the
system combines these actions with its basic laws to produce an
outcome. Some of these systems perform well, e.g., the national residency
matching program which assigns medical students to residency programs
in hospitals, e.g., auctions for online advertising on Internet search
engines; and some of these systems perform poorly, e.g., financial
markets during the 2008 meltdown, e.g., gridlocked transportation
networks. The success and failure of these systems depends on the
basic laws governing the system. Financial regulation can prevent
disastrous market meltdowns, congestion protocols can prevent gridlock
in transportation networks, and market and auction design can lead to
mechanisms for allocating and exchanging goods or services that yield
higher profits or increased value to society.
This text focuses on a combined computational and economic theory for
the study and design of mechanisms. A central theme will be the
tradeoff between optimality 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 theory provided does not necessarily suggest
mechanisms that should be deployed in practice, instead, it pinpoints
salient features of good mechanisms that should be a starting point
for the practitioner.
- Chapter 1: Mechanism Design and Approximation [ch1.pdf]
mechanism design, approximation, first-price auction, second-price auction, lottery, posted pricings.
- Chapter 2: Equilibrium [ch2.pdf]
Bayes-Nash equilibirum, dominant strategy equilibrium, single-dimensional agents, revenue equivalence, revelation principle, incentive compatibility.
- Chapter 3: Optimal Mechanisms [ch3.pdf]
single-dimensional mechanism design, surplus-optimal mechanism (VCG), revenue-optimal mechanism, revenue curves, virtual values, ironing, marginal revenue, revenue linearity, Lagrangian virtual values
- Chapter 4: Bayesian Approximation [ch4.pdf]
reserve pricing, posted pricing, prophet inequality, correlation gap, matroid set systems, greedy algorithms, monotone hazard rate distributions.
- Chapter 5: Prior-independent Approximation [ch5.pdf]
Bulow-Klemperer theorem, single sample mechanism, digital goods.
- Chapter 6: Bayes-Nash Approximation [chX.pdf]
geometry of best response, revenue covering approximation, simultanious composition, surplus and revenue analysis in BNE, reserve prices in BNE, greedy approximation algorithms.
- Chapter 7: Prior-free Approximation [ch6.pdf]
Chapter 8: Multi-dimensional and Non-linear Preferences [ch8.pdf]
envy-free pricing (benchmark), random sampling auction, profit extraction, lower bounds
revenue linearity, interim feasibility, unit-demand agents, agents with budgets, optimal mechanisms as convex optimization, matching markets.
- Chapter 9: Multi-dimensional and Non-linear Approximation
posted pricing, approximate revenue linearity, single-dimensional representative environments
- Chapter 10: Computational Tractability
approximation algorithms, greedy-by-value, BIC blackbox reductions, payment computation.