CS-ECON Seminar Series

Mechanism design; Auctions and Scheduling

Speaker:Angelina Vidali
Department of Computer Science, Duke University
Date: Friday, September 21, 2012
Time: 12:00pm - 1:00pm
Location: D344 LSRC, Duke
Lunch will be served.


I will give an introduction and present some of my recent results in one of the most fundamental problems in algorithmic game theory and mechanism design: the problem of scheduling unrelated machines to minimize the makespan. I will emphasize the connection between this problem and the problem of designing truthful auctions for selling multiple items. I will also present a geometrical characterization of truthfulness and also some very recent work on strongly truthful mechanisms.

We assume that the machines behave like selfish players: they have to get paid in order to process the tasks, and would lie about their processing times if they could increase their utility in this way. The problem was proposed thirteen years ago in the seminal paper of Nisan and Ronen, where it was shown that the approximation ratio of mechanisms is between $2$ and $n$. I improve this to $1+\sqrt{2}$ for three or more machines and to $1+\varphi$ for many machines. I also characterize the class of truthful mechanisms for the case of two players (regardless of approximation ratio) and for the case of Smon and continuous n-player mechanisms and show how the result can be used as a black box to obtain characterizations for other domains.


Angelina Vidali is a postdoc in the Department of Computer Science, Duke University.