Informatik, TU Wien

Designing Truthful Mechanisms

In this talk I will present my work on many different aspects of one of the most fundamental problems in algorithmic game theory, the problem of scheduling unrelated machines to minimize the makespan.

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.