
Picasso's Bull, December 1945  January 1946. 
Mechanism Design and Approximation
By Jason D. Hartline
Copyright © 20112016
Synopsis:
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.
Manuscript: [chapters
18.pdf] [chapters 910 coming soon; material from Bayesian Mechanism Design survey; chapters 67]
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/.
News:
 01/19/16: There is a new chapter on the design of optimal mechanisms for agents with multidimensional and nonlinear preferences. It will be inserted between chapters 6 and 7 of the firstdraft of April 2012 (becoming Chapter 8). [chapters 18.pdf] [ch8.pdf]
 12/10/14: There is a new chapter on design and analysis of BayesNash 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 79 are coming soon. [chapters 16.pdf]
[ch6.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:304pm; 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 25.
[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 15 are available for download; Chapters 69 are coming soon.
 09/23/13: An online selfstudy 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 18 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.
Contents:
 Chapter 1: Mechanism Design and Approximation [ch1.pdf]
mechanism design, approximation, firstprice auction, secondprice auction, lottery, posted pricings.
 Chapter 2: Equilibrium [ch2.pdf]
BayesNash equilibirum, dominant strategy equilibrium, singledimensional agents, revenue equivalence, revelation principle, incentive compatibility.
 Chapter 3: Optimal Mechanisms [ch3.pdf]
singledimensional mechanism design, surplusoptimal mechanism (VCG), revenueoptimal 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: Priorindependent Approximation [ch5.pdf]
BulowKlemperer theorem, single sample mechanism, digital goods.
 Chapter 6: BayesNash 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: Priorfree Approximation [ch6.pdf]
envyfree pricing (benchmark), random sampling auction, profit extraction, lower bounds
 Chapter 8: Multidimensional and Nonlinear Preferences [ch8.pdf]
revenue linearity, interim feasibility, unitdemand agents, agents with budgets, optimal mechanisms as convex optimization, matching markets.
 Chapter 9: Multidimensional and Nonlinear Approximation
posted pricing, approximate revenue linearity, singledimensional representative environments
 Chapter 10: Computational Tractability
approximation algorithms, greedybyvalue, BIC blackbox reductions, payment computation.