An optimal lower bound for anonymous scheduling mechanisms
By: Itai Ashlagi, Shahar Dobzinski, and Ron Lavi
Contributors: Dobzinski, Shahar; Lavi, Ron; Harvard Business School
Series: Working paper / Harvard Business School -- 09-070; Working paper (Harvard Business School) -- 09-070
Publisher: Harvard Business School
Published: 2008
Place of publication: Boston
Language: eng
Number of pages: 14
Description: We consider the problem of designing truthful mechanisms to minimize the makespan on m unrelated machines. In their seminal paper, Nisan and Ronen [14] showed a lower bound of 2, and an upper bound of m, thus leaving a large gap. They conjectured that their upper bound is tight, but were unable to prove it. Despite many attempts that yield positive results for several special cases, the conjecture is far from being solved: the lower bound was only recently slightly increased to 2.61 [5, 10], while the best upper bound remained unchanged. In this paper we show the optimal lower bound on truthful anonymous mechanisms: no such mechanism can guarantee an approximation ratio better than m. This is the first concrete evidence to the correctness of the Nisan-Ronen conjecture, especially given that the classic scheduling algorithms are anonymous, and all state-of-the-art mechanisms for special cases of the problem are anonymous as well.
Notes: "November 2008"--Publisher's web site.

Includes bibliographical references.