
Abstract
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 nplayer mechanisms and show how the result can be used as a black box to obtain characterizations for other domains.
Biography
Angelina Vidali is a postdoc in the Department of Computer Science, Duke University.