Floragasse 7 – 5th floor, 1040 Vienna


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.

This Website uses Cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.