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/.

News:

• 09/20/21: Releasing revisions to Chapters 1-7.
• 07/13/20: I gave a four-part Tutorial on the Foundations of Non-Truthful Mechanism Design at the 2020 ACM Conference on Economics and Computation. Video is available.
• 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.
• 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.

Contents:

• 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 [ch6.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 [ch7.pdf]
  envy-free pricing (benchmark), random sampling auction, profit extraction, lower bounds
• Chapter 8: Multi-dimensional and Non-linear Preferences [ch8.pdf] (update coming soon)
  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 [ch9.pdf] (update coming soon)
  unit-demand agents, additive agents, posted pricing, approximate revenue linearity, the marginal revenue mechanism, single-dimensional representative environments.
• Chapter 10: Computational Tractability (update coming soon)
  approximation algorithms, greedy-by-value, BIC blackbox reductions, payment computation.