Research Talk: Designing Truthful Mechanisms
May 10, 2011, 10am @ SBA: Designing Truthful Mechanisms
Angelina Vidali
In this talk I will present my work on many different aspects of one of the most fundamental problems in algorithmic game theory (and more specifically algorithmic mechanism design), the problem of scheduling unrelated machines to minimize the makespan and I will also explain its connection with the problem of designing truthful combinatorial auctions. 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 and studied in the seminal paper of Nisan and Ronen, where it was shown that the approximation ratio of mechanisms is between 2 and n.