Synopsis:
The text Mechanism Design and Approximation is based on a
graduate course that has been developed at Northwestern over the past
decade. It presents the classical theory of economic mechanism design and
introduces a new theory of approximation for mechanism design.
Manuscript:[chapters
1-8.pdf] [chapter 10 coming soon; material from Bayesian Mechanism Design survey; chapters 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/.
07/18/17: I gave two lectures in the
Jerusalem
Summer School in Economic Theory. These lectures covered the
recently updated Chapters 8 and 9 on mechanism design and
approximation for multi-dimensional and non-linear agents. Part I
(video)
covered reductions from multi-agent mechanism design to single-agent
mechanism design and Part II
(video)
covered single agent mechanism design. Tim Roughgarden gave two
excellent lectures on the price of anarchy in auctions (video 1, video 2), and Stephen
Morris delivered the Arrow Lecture (video) on informational assumptions in
mechanism design.
07/05/17: The second draft of Chapter 9 is available for
download; Chapter 8 was slightly revised in the
process. [ch8.pdf][ch9.pdf]
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][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:30-4pm; beginning Sept. 3.
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.
Contents:
Chapter 1: Mechanism Design and Approximation [ch1.pdf]
geometry of best response, revenue covering approximation, simultanious composition, surplus and revenue analysis in BNE, reserve prices in BNE, greedy approximation algorithms.