Mechanism Design: Classic & Computational


Contents
Overview
Reading
Lecture Notes
Links

Home

Overview
Mechanism design is the problem of designing a distributed protocol that will implement a particular objective despite the self-interest of individual agents. Chapters 2 and 3 of my dissertation, with links below, review classic mechanism design and computational mechanism design. In computational mechanism design the idea is to maintain useful economic properties but also achieve useful computational properties.
Reading
[PS] [PDF] Parkes 01 David Parkes. Classic Mechanism Design.
Chapter 2, Iterative Combinatorial Auctions: Achieving Economic and Computational Efficiency Ph.D. dissertation, Univesity of Pennsylvania, May, 2001.

This chapter provides a brief introduction to game theory, and then introduces important concepts in mechanism design. The revelation principle, the Vickrey-Clarke-Groves mechanisms, and important Impossibility and Possibility results are all discussed at some length.

[PS] [PDF] Parkes 01 David Parkes. Computational Mechanism Design.
Chapter 3, Iterative Combinatorial Auctions: Achieving Economic and Computational Efficiency Ph.D. dissertation, Univesity of Pennsylvania, May, 2001.

The focus of this chapter is on the Generalized Vickrey Auction, and combinatorial allocation problems. In particular, I consider approaches to address the computational complexity of winner determination, the valuation complexity of participation in an auction, and the communication costs of different mechanisms.

[PDF] DJP03 Rajdeep Dash, Nicholas Jennings and David Parkes. Computational-Mechanism Design: A Call to Arms
in IEEE Intelligent Systems, November 2003, pages 40-47 (Special Issue on Agents and Markets).

An overview of computational mechanism design, designed for researchers in multi-agent systems. Suggests future research directions.


Lecture Notes
Combinatorial Auctions & Cost-sharing Mechanisms
Game Theory
Mechanism Design I
Mechanism Design II
Mechanism Design III
Auction Theory

Links
Computational Mechanism Design, Harvard CS 286r, Spring 2002.