Designing Mechanisms for Scheduling

makespan. 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.

In this talk, I will present some recent improvements of the lower bound to 1+\sqrt{2} for three or more machines and to 1+\phi for many
machines.

I will also generalize a tool used in the proof of the 1+\sqrt{2} lower bound: I give a geometrical characterization of truthfulness for the case of three tasks, which I believe that might be useful for proving improved lower bounds and which provides a more complete understanding of truthfulness.

Since the gap between the lower bound of 2.618 and the upper bound of n is huge, I will also propose an alternative approach to the problem, which first attempts to characterize all truthful mechanisms and then study their approximation ratio. Towards this goal I will show that the class of truthful mechanisms for two players (regardless of approximation ratio) is very limited: tasks can be partitioned in groups allocated by affine minimizers (a natural generalization of the well-known VCG mechanism) and groups allocated by threshold mechanisms.