论文标题
确定性真实安排的新下限
A New Lower Bound for Deterministic Truthful Scheduling
论文作者
论文摘要
正如Nisan和Ronen的开创性作品所介绍的那样，我们研究了将$ m $任务当成$ n $自私的机器的实际问题，即$ n $自私的机器。在确定性真实机制的近似值上缩小$ [2.618，n] $的当前差距是算法机制设计领域的臭名昭著的开放问题。我们在十多年内提供了第一个这样的改进，因为Christodoulou等人的下限$ 2.414 $（$ n = 3 $）和$ 2.618 $（对于$ n \ to \ infty $）。 [Soda'07]和Koutsoupias和Vidali [MFCS'07]。更具体地说，我们表明，即使仅在$ n = 4 $机器上，目前最佳的$ 2.618 $的下限也可以实现；对于$ n = 5 $，我们已经获得了第一个改进，即$ 2.711 $;并允许机器的数量任意生长，我们可以获得$ 2.755 $的下限。
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\to\infty$) 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$.
