Universally truthful mechanisms for scheduling

Georgios Anastasiadis, George Christodoulou, Elias Koutsoupias +2

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…