A New Lower Bound for Deterministic Truthful Scheduling
share
We study the problem of truthfully scheduling m tasks to n selfish unrelated machines, under the objective of makespan minimization, as was introduced in the seminal work of Nisan and Ronen [STOC'99]. Closing the current gap of [2.618,n] on the approximation ratio of deterministic truthful mechanisms is a notorious open problem in the field of algorithmic mechanism design. We provide the first such improvement in more than a decade, since the lower bounds of 2.414 (for n=3) and 2.618 (for n→∞) by Christodoulou et al. [SODA'07] and Koutsoupias and Vidali [MFCS'07], respectively. More specifically, we show that the currently best lower bound of 2.618 can be achieved even for just n=4 machines; for n=5 we already get the first improvement, namely 2.711; and allowing the number of machines to grow arbitrarily large we can get a lower bound of 2.755.
READ FULL TEXT