News Archives

[Colloquium] Mechanism Design: Truthful and Frugal Auctions

November 10, 2006

Watch Colloquium: 

AVI (361 Meg) 
Quicktime (157 Meg) 


  • Date: Friday, November 10th, 2006 
  • Time: 1 pm — 2:15 pm 
  • Place: ME 218

David Kempe 
University of Southern California

Abstract Due to the increasing interaction of users in networks, and the ability to conduct economic transactions and auctions easily and frequently, there has been a recent development of interest in the boundary between computation and game theory. Among the important developments has been a focus on computational aspects of auctions, and on the design of auctions with desirable properties, such as providing disincentives to lying or cheating, and maximizing the seller’s revenue (or minimizing the buyer’s costs). In this talk, specifically, we study mechanisms for auctions in which the auctioneer is trying to hire a team of agents to perform a complex task, and paying them for their work. As common in the field of mechanism design, we assume that the agents are selfish and will act in such a way as to maximize their profit, which in particular may include misrepresenting their true incurred cost. Our first contribution is a new and natural definition of the frugality ratio of a mechanism, measuring the amount by which a mechanism “overpays”, and extending previous definitions to all set systems without monopolies.

After reexamining several known results in light of this new definition, we proceed to study in detail shortest path auctions and “r-out-of-k sets” auctions. We show that when individual set systems (e.g., graphs) are considered instead of worst cases over all instances, these problems exhibit a rich structure, and the performance of different mechanisms previously considered comparable may be vastly different. In particular, we show that the well-known VCG mechanism may be far from optimal in these settings, and we propose and analyze a mechanism that is always within a constant factor of optimal.

This talk represents joint work with Anna Karlin and Tami Tamir.

Bio: David Kempe received his Ph.D. from Cornell University in 2003, and has been on the faculty in the computer science department at USC since the Fall of 2004. His primary research interests are in computer science theory and the design and analysis of algorithms, with a particular emphasis on social networks, distributed network algorithms, and game theoretic and pricing questions. He is a recipient of the NSF CAREER award.