Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

[Sequence announcement] Introduction to Mechanism Design

54 Post author: badger 30 April 2014 04:21PM

Mechanism design is the theory of how to construct institutions for strategic agents, spanning applications like voting systems, school admissions, regulation of monopolists, and auction design. Think of it as the engineering side of game theory, building algorithms for strategic agents. While it doesn't have much to say about rationality directly, mechanism design provides tools and results for anyone interested in world optimization.

In this sequence, I'll touch on

  • The basic mechanism design framework, including the revelation principle and incentive compatibility.
  • The Gibbard-Satterthwaite impossibility theorem for strategyproof implementation (a close analogue of Arrow's Theorem), and restricted domains like single-peaked or quasilinear preference where we do have positive results.
  • The power and limitations of Vickrey-Clarke-Groves mechanisms for efficiently allocating goods, generalizing Vickrey's second-price auction.
  • Characterizations of incentive-compatible mechanisms and the revenue equivalence theorem.
  • Profit-maximizing auctions.
  • The Myerson-Satterthwaite impossibility for bilateral trade.
  • Two-sided matching markets à la Gale and Shapley, school choice, and kidney exchange.

As the list above suggests, this sequence is going to be semi-technical, but my foremost goal is to convey the intuition behind these results. Since mechanism design builds on game theory, take a look at Yvain's Game Theory Intro if you want to brush up.

Various resources:

I plan on following up on this sequence with another focusing on group rationality and information aggregation, surveying scoring rules and prediction markets among other topics.

Suggestions and comments are very welcome.

Comments (12)

Comment author: Vulture 30 April 2014 09:00:11PM *  5 points [-]

Ooh, this is exciting. Mechanism design has always struck me as something worth studying for aspiring world-optimizers, since it seems like it's sort of the key mindset/framework that would facilitate designing e.g. a government

Comment author: cousin_it 30 April 2014 10:07:29PM 4 points [-]

I can't wait to read this. The first post is already really good.

Comment author: MattG 30 April 2014 09:07:27PM 3 points [-]

What type of information would be prerequisite to understanding this sequence?

Comment author: badger 30 April 2014 09:58:24PM 6 points [-]

Some exposure to game theory. Otherwise, tolerance of formulas and a little bit of calculus for optimization.

At least, I hope that's the case. I've been teaching this to economics grad students for the past few years, so I know common points of misunderstanding, but can easily take some jargon for granted. Please call me out on anything that is unclear.

Comment author: MarkL 01 May 2014 12:22:55PM 2 points [-]

Anyone do "mechanism design" in their day job? What are jobs that have aspects of this? (Besides implicitly, like every web startup ever, which is still interesting to think about.)

Comment author: badger 01 May 2014 01:17:15PM 3 points [-]

Aside from academic economists and computer scientists? :D Auction design has been a big success story, enough so that microeconomic theorists like Hal Varian and Preston McAfee now work at Google full time. Microsoft and other tech companies also have research staff working specifically on mechanism design.

As far as people that should have some awareness (whether they do or not): anyone implementing an online reputation system, anyone allocating resources (like a university allocating courses to students or the US Army allocating ROTC graduates to its branches), or anyone designing government regulation.

Comment author: Lumifer 01 May 2014 04:27:17PM 2 points [-]

What are jobs that have aspects of this?

Management, especially high-level management. This basically what CEOs of large companies are supposed to do.

Politicians (and, by implications, lobbyists, consultants, think tanks, etc.).

Comment author: cursed 04 May 2014 05:33:17AM 1 point [-]

It'd be nice if you could go over why you think you'd be a good candidate to cover the subject.

Comment author: badger 05 May 2014 11:33:52PM 1 point [-]

I'm a PhD student working in this field and have TA'd multiple years for a graduate course covering this material.

Comment author: cursed 06 May 2014 07:06:37AM 0 points [-]

I'm convinced! Checked out your first post, good stuff so far.

Comment author: IlyaShpitser 01 May 2014 12:14:24PM *  0 points [-]

I think that this is what we, as a civ, need to concentrate on if we are worried about inhuman unfriendly giants running around.

Comment author: asr 30 April 2014 07:41:24PM 0 points [-]

I would read this if written well.