Universally truthful mechanisms for scheduling

Abstract

We consider universally truthful randomized mechanisms for the problem of scheduling $m$ jobs on $n$ unrelated machines. We prove a lower bound on the expected approximation ratio of every such mechanism whose probability distribution has discrete support. We show that no universally truthful randomized mechanism in this class can achieve approximation ratio smaller than $n/12-o(n)$ with respect to the optimal makespan. We match this, up to a constant factor, by a mechanism with approximation ratio $n/2+o(n)$.