Description Harvard University
Computer Science Colloquium Series
33 Oxford St., Cambridge, MA 02138

Colloquium

Explorations in Computational Mechanism Design

David C. Parkes
School of Engineering and Applied Sciences
Harvard University

Monday, November 19, 2007
4:00PM
Maxwell Dworkin G115
(Refreshments at 3:30PM - Maxwell Dworkin Ground Floor outside G115)

Abstract
In this talk, I will introduce the area of computational mechanism design (CMD), which seeks to understand how to design games to induce desirable outcomes in multi-agent systems despite private information, self-interest and limited computational resources. CMD finds application in many settings, from allocating wireless spectrum and airport landing slots, to internet advertising, to expressive sourcing in the supply chain, to allocating shared computational resources. In meeting the demands for CMD in these rich domains, we need to bridge
from the classic theory of economic mechanism design to the practice of deployable, scalable mechanisms.

I will first provide a brief overview of the theory of economic mechanism design, and explain the idea of strategyproof mechanisms. In moving to CMD, I will highlight my contributions to the design of dynamic coordination mechanisms. Many interesting multi-agent systems are inherently uncertain and dynamic, with agents arriving and departing over time, and with individual agents facing dynamic local problems. We will see that the Vickrey-Clarke-Groves (VCG) mechanism can be generalized to these domains, albeit with an interesting change
in the solution concept, and usefully coupled with sample-based algorithms for solving (PO)MDPs. This opens up a new frontier of applications for CMD. Recognizing also that the computational challenges endemic to VCG mechanisms remain severe in some domains, I
outline a complementary direction in "computational ironing", which embraces heuristic, scalable algorithms and supports learning.

I will close with some brief comments about my related work in combinatorial markets and incentive-compatible social computing, and suggest a couple of new directions that my research group is currently pursuing.

Host: Professor Greg Morrisett

Web site:
Contact name:
Contact e-mail:
Contact phone:
Source Calendar: Computer Science Colloquium Series

[Close]