October 19, 2011: Talk Announcement - David Kempe: "Mechanism Design: Truthful and Frugal Auctions"

Talk Announcement

Mechanism Design: Truthful and Frugal Auctions

David Kempe
Thursday October 20, 2011
11:00 a.m., 1000 SEO


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.

After a gener-audience introduction to auctions and mechanism design, 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 auctions for shortest paths and vertex covers in graphs. Surprisingly, vertex covers turn out to be a useful primitive for designing auctions in other scenarios, including paths, flows, and cuts. 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 mechanisms that are in fact optimal.

This talk represents joint work with Anna Karlin, Tami Tamir, Mahyar Salek, and Cris Moore, and is based on papers from FOCS 2005 and FOCS 2010. No prior expertise on game theory or mechanism design will be assumed.

Host: Professor Tanya Berger-Wolf

Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
Helping Women Faculty Advance
Funded by NSF