skip to main content
research-article

Mechanism design for fractional scheduling on unrelated machines

Published:06 April 2010Publication History
Skip Abstract Section

Abstract

Scheduling on unrelated machines is one of the most general and classical variants of the task scheduling problem. Fractional scheduling is the LP-relaxation of the problem, which is polynomially solvable in the nonstrategic setting, and is a useful tool to design deterministic and randomized approximation algorithms.

The mechanism design version of the scheduling problem was introduced by Nisan and Ronen. In this article, we consider the mechanism design version of the fractional variant of this problem. We give lower bounds for any fractional truthful mechanism. Our lower bounds also hold for any (randomized) mechanism for the integral case. In the positive direction, we propose a truthful mechanism that achieves approximation 3/2 for 2 machines, matching the lower bound. This is the first new tight bound on the approximation ratio of this problem, after the tight bound of 2, for 2 machines, obtained by Nisan and Ronen. For n machines, our mechanism achieves an approximation ratio of n+1/2.

Motivated by the fact that all the known deterministic and randomized mechanisms for the problem assign each task independently from the others, we focus on an interesting subclass of allocation algorithms, the task-independent algorithms. We give a lower bound of n+1/2, that holds for every (not only monotone) allocation algorithm that takes independent decisions. Under this consideration, our truthful independent mechanism is the best that we can hope from this family of algorithms.

References

  1. Andelman, N., Azar, Y., and Sorani, M. 2005. Truthful approximation mechanisms for scheduling selfish related machines. In Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS). 69--82. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. Archer, A. 2004. Mechanisms for discrete optimization with rational agents. Ph.D. thesis, Cornell University. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. Archer, A., Papadimitriou, C. H., Talwar, K., and Tardos, É. 2003. An approximate truthful mechanism for combinatorial auctions with single parameter agents. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 205--214. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. Archer, A., and Tardos, É. 2001. Truthful mechanisms for one-parameter agents. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS). 482--491. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. Babaioff, M., Lavi, R., and Pavlov, E. 2005. Mechanism design for single-value domains. In Proceedings of the 20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference (AAAI). 241--247. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Bartal, Y., Gonen, R., and Nisan, N. 2003. Incentive compatible multi unit combinatorial auctions. In Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK). 72--87. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. Bikhchandani, S., Chatterji, S., Lavi, R., Mu'alem, A., Nisan, N., and Sen, A. 2006. Weak monotonicity characterizes deterministic dominant strategy implementation. Econometrica 74, 4, 1109--1132.Google ScholarGoogle ScholarCross RefCross Ref
  8. Briest, P., Krysta, P., and Vöcking, B. 2005. Approximation techniques for utilitarian mechanism design. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC). 39--48. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. Christodoulou, G., Koutsoupias, E., and Kovács, A. 2007. Mechanism design for fractional scheduling on unrelated machines. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP). 40--52. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. Christodoulou, G., Koutsoupias, E., and Vidali, A. 2007. A lower bound for scheduling mechanisms. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 1163--1170. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. Dobzinski, S., Nisan, N., and Schapira, M. 2005. Approximation algorithms for combinatorial auctions with complement-free bidders. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC). 610--618. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. Dobzinski, S., Nisan, N., and Schapira, M. 2006. Truthful randomized mechanisms for combinatorial auctions. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC). 644--652. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. Gui, H., Müller, R., and Vohra, R. V. 2005. Dominant strategy mechanisms with multidimensional types. In Computing and Markets.Google ScholarGoogle Scholar
  14. Kovács, A. 2005. Fast monotone 3-approximation algorithm for scheduling related machines. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA'05). 616--627. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. Kovács, A. 2007. Fast algorithms for two scheduling problems. Ph.D. thesis, Universität des Saarlandes.Google ScholarGoogle Scholar
  16. Lavi, R., Mu'alem, A., and Nisan, N. 2003. Towards a characterization of truthful combinatorial auctions. In Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS). 574--583. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. Lavi, R., and Swamy, C. 2005. Truthful and near-optimal mechanism design via linear programming. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 595--604. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. Lavi, R., and Swamy, C. 2007. Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity. In Proceedings of the ACM Conference on Electronic Commerce (EC). Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. Lenstra, J., Shmoys, D., and Tardos, É. 1990. Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 1, 259--271. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. Mu'alem, A., and Schapira, M. 2007. Setting lower bounds on truthfulness. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1143--1152. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. Myerson, R. B. 1981. Optimal auction design. Math. Oper. Res. 6, 1, 58--73.Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. Nisan, N., and Ronen, A. 1999. Algorithmic mechanism design (extended abstract). In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC). 129--140. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. Nisan, N., and Ronen, A. 2001. Algorithmic mechanism design. Games Econom. Behav. 35, 166--196.Google ScholarGoogle ScholarCross RefCross Ref
  24. Saks, M. E., and Yu, L. 2005. Weak monotonicity suffices for truthfulness on convex domains. In Proceedings of the 6th ACM Conference on Electronic Commerce (EC). 286--293. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Mechanism design for fractional scheduling on unrelated machines

        Recommendations

        Comments

        Login options

        Check if you have access through your login credentials or your institution to get full access on this article.

        Sign in

        Full Access

        • Published in

          cover image ACM Transactions on Algorithms
          ACM Transactions on Algorithms  Volume 6, Issue 2
          March 2010
          373 pages
          ISSN:1549-6325
          EISSN:1549-6333
          DOI:10.1145/1721837
          Issue’s Table of Contents

          Copyright © 2010 ACM

          Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

          Publisher

          Association for Computing Machinery

          New York, NY, United States

          Publication History

          • Published: 6 April 2010
          • Accepted: 1 January 2009
          • Revised: 1 May 2008
          • Received: 1 June 2007
          Published in talg Volume 6, Issue 2

          Permissions

          Request permissions about this article.

          Request Permissions

          Check for updates

          Qualifiers

          • research-article
          • Research
          • Refereed

        PDF Format

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader