Abstract
We study the mechanism design problem of scheduling tasks on n unrelated machines in which the machines are the players of the mechanism. The problem was proposed and studied in the seminal paper of Nisan and Ronen on algorithmic mechanism design, where it was shown that the approximation ratio of mechanisms is between 2 and n. We improve the lower bound to \(1+\sqrt{2}\) for 3 or more machines.
Article PDF
Similar content being viewed by others
References
Andelman, N., Azar, Y., Sorani, M.: Truthful approximation mechanisms for scheduling selfish related machines. In: 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 69–82 (2005)
Archer, A.: Mechanisms for discrete optimization with rational agents. Ph.D. thesis, Cornell University (January 2004)
Archer, A., Tardos, É.: Truthful mechanisms for one-parameter agents. In: 42nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 482–491 (2001)
Archer, A., Papadimitriou, C.H., Talwar, K., Tardos, É.: An approximate truthful mechanism for combinatorial auctions with single parameter agents. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 205–214 (2003)
Babaioff, M., Lavi, R., Pavlov, E.: Mechanism design for single-value domains. In: Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference (AAAI), pp. 241–247 (2005)
Bartal, Y., Gonen, R., Nisan, N.: Incentive compatible multi unit combinatorial auctions. In: Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK), pp. 72–87 (2003)
Briest, P., Krysta, P., Vöcking, B.: Approximation techniques for utilitarian mechanism design. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 39–48 (2005)
Christodoulou, G., Koutsoupias, E., Kovács, A.: Mechanism design for fractional scheduling on unrelated machines. In: Automata, Languages and Programming, 34th International Colloquium (ICALP), pp. 40–52 (2007)
Christodoulou, G., Koutsoupias, E., Vidali, A.: A lower bound for scheduling mechanisms. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1163–1169 (2007)
Dobzinski, S., Nisan, N., Schapira, M.: Approximation algorithms for combinatorial auctions with complement-free bidders. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 610–618 (2005)
Dobzinski, S., Nisan, N., Schapira, M.: Truthful randomized mechanisms for combinatorial auctions. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 644–652 (2006)
Gui, H., Müller, R., Vohra, R.V.: Dominant strategy mechanisms with multidimensional types. In: Computing and Markets (2005)
Hochbaum, D.S.: Approximation Algorithms for NP-Hard Problems. PWS, Boston (1996)
Kovács, A.: Fast monotone 3-approximation algorithm for scheduling related machines. In: Algorithms—ESA 2005: 13th Annual European Symposium, pp. 616–627 (2005)
Kovács, A.: Fast algorithms for two scheduling problems. Ph.D. thesis, Universität des Saarlandes (2007)
Lavi, R., Swamy, C.: Truthful mechanism design for multi-dimensional scheduling via cycle-monotonicity. In: Proceedings 8th ACM Conference on Electronic Commerce (EC) (2007)
Lavi, R., Mu’alem, A., Nisan, N.: Towards a characterization of truthful combinatorial auctions. In: 44th Symposium on Foundations of Computer Science (FOCS), pp. 574–583 (2003)
Lenstra, J.K., Shmoys, D.B., Tardos, É: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46(1), 259–271 (1990)
Mu’alem, A., Schapira, M.: Setting lower bounds on truthfulness. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1143–1152 (2007)
Myerson, R.B.: Optimal auction design. Math. Oper. Res. 6(1), 58–73 (1981)
Nisan, N., Ronen, A.: Algorithmic mechanism design (extended abstract). In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing (STOC), pp. 129–140 (1999)
Nisan, N., Ronen, A.: Algorithmic mechanism design. Games Econ. Behav. 35, 166–196 (2001)
Roberts, K.: The characterization of implementable choice rules. In: Aggregation and Revelation of Preferences, pp. 321–348 (1979)
Saks, M.E., Yu, L.: Weak monotonicity suffices for truthfulness on convex domains. In: Proceedings 6th ACM Conference on Electronic Commerce (EC), pp. 286–293 (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported in part by IST-15964 (AEOLUS) and the Greek GSRT.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License ( https://creativecommons.org/licenses/by-nc/2.0 ), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Christodoulou, G., Koutsoupias, E. & Vidali, A. A Lower Bound for Scheduling Mechanisms. Algorithmica 55, 729–740 (2009). https://doi.org/10.1007/s00453-008-9165-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-008-9165-3