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 +√ 2 ≈ 2.41 by Christodoulou, Kotsoupias, and Vidali, and then to 1+φ≈ 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-δ, for every constant δ>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+√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+√ 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.