cs.GT
Improved Lower Bounds for Truthful Scheduling. The problem of scheduling unrelated machines by a truthful mechanism to minimize the makespan was introduced in the seminal "Algorithmic Mechanism Design" paper by Nisan and Ronen. Nisan and Ronen showed that there is a truthful mechanism that provides an approximation ratio of min(m,n) , where n is the number of machines and m is the number of jobs. They also proved that no truthful mechanism can provide an approximation ratio better than 2 . Since then, the lower bound was improved to 1 sqrt 2 approx 2.41 by Christodoulou, Kotsoupias, and Vidali, and then to 1 phi approx 2.618 by Kotsoupias and Vidali. Very recently, the lower bound was improved to 2.755 by Giannakopoulos, Hammerl, and Pocas. In this paper we further improve the bound to 3 delta , for every constant delta 0 . Note that a gap between the upper bound and the lower bounds exists even when the number of machines and jobs is very small. In particular, the known 1 sqrt 2 lower bound requires at least 3 machines and 5 jobs. In contrast, we show a lower bound of 2.2055 that uses only 3 machines and 3 jobs and a lower bound of 1 sqrt 2 that uses only 3 machines and 4 jobs. For the case of two machines and two jobs we show a lower bound of 2 . Similar bounds for two machines and two jobs were known before but only via complex proofs that characterized all truthful mechanisms that provide a finite approximation ratio in this setting, whereas our new proof uses a simple and direct approach.