An optimal lower bound for anonymous scheduling mechanisms

ABSTRACT

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.

REFERENCES

• 1: Gagan Aggarwal , Amos Fiat , Andrew V. Goldberg , Jason D. Hartline , Nicole Immorlica , Madhu Sudan, Derandomization of auctions, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060682]
• 2: A. Archer , É. Tardos, Truthful Mechanisms for One-Parameter Agents, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.482, October 14-17, 2001
• 3: George Christodoulou , Elias Koutsoupias , Angelina Vidali, A Characterization of 2-Player Mechanisms for Scheduling, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_25]
• 4: George Christodoulou, Elias Koutsoupias, and Annamária Kovács. Mechanism design for fractional scheduling on unrelated machines. In ICALP'07.
• 5: George Christodoulou , Elias Koutsoupias , Angelina Vidali, A lower bound for scheduling mechanisms, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1163-1170, January 07-09, 2007, New Orleans, Louisiana
• 6: Constantinos Daskalakis , Christos Papadimitriou, Computing Equilibria in Anonymous Games, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.83-93, October 21-23, 2007 [doi>10.1109/FOCS.2007.19]
• 7: Constantinos Daskalakis , Christos H. Papadimitriou, Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.25-34, October 25-28, 2008 [doi>10.1109/FOCS.2008.84]
• 8: Peerapong Dhangwatnotai , Shahar Dobzinski , Shaddin Dughmi , Tim Roughgarden, Truthful Approximation Schemes for Single-Parameter Agents, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.15-24, October 25-28, 2008 [doi>10.1109/FOCS.2008.71]
• 9: Shahar Dobzinski , Mukund Sundararajan, On characterizations of truthful mechanisms for combinatorial auctions and scheduling, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA [doi>10.1145/1386790.1386798]
• 10: Elias Koutsoupias and Angelina Vidali. A lower bound of 1 phi for truthful scheduling mechanisms. In MFCS'07.
• 11: Ron Lavi , Ahuva Mu'alem , Noam Nisan, Towards a Characterization of Truthful Combinatorial Auctions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.574, October 11-14, 2003
• 12: Ron Lavi , Chaitanya Swamy, Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250947]
• 13: Ahuva Mu'alem , Michael Schapira, Setting lower bounds on truthfulness: extended abstract, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1143-1152, January 07-09, 2007, New Orleans, Louisiana
• 14: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 15: Michael Saks , Lan Yu, Weak monotonicity suffices for truthfulness on convex domains, Proceedings of the 6th ACM conference on Electronic commerce, p.286-293, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064040]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Theory

Keywords:
incentive compatibility, scheduling