Mechanism Design and Approximation
By Jason D. Hartline
Copyright © 2011-2020

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.

Picasso's Bull
Picasso's Bull, December 1945 -- January 1946.

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:


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.