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.
- 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 ScholarDigital Library
- Archer, A. 2004. Mechanisms for discrete optimization with rational agents. Ph.D. thesis, Cornell University. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Gui, H., Müller, R., and Vohra, R. V. 2005. Dominant strategy mechanisms with multidimensional types. In Computing and Markets.Google Scholar
- 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 ScholarDigital Library
- Kovács, A. 2007. Fast algorithms for two scheduling problems. Ph.D. thesis, Universität des Saarlandes.Google Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Lenstra, J., Shmoys, D., and Tardos, É. 1990. Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 1, 259--271. Google ScholarDigital Library
- 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 ScholarDigital Library
- Myerson, R. B. 1981. Optimal auction design. Math. Oper. Res. 6, 1, 58--73.Google ScholarDigital Library
- 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 ScholarDigital Library
- Nisan, N., and Ronen, A. 2001. Algorithmic mechanism design. Games Econom. Behav. 35, 166--196.Google ScholarCross Ref
- 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 ScholarDigital Library
Index Terms
Mechanism design for fractional scheduling on unrelated machines
Recommendations
Minimizing Flow-Time on Unrelated Machines
STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of ComputingWe consider some classical flow-time minimization problems in the unrelated machines setting. In this setting, there is a set of m machines and a set of n jobs, and each job j has a machine dependent processing time of pij on machine i. The flow-time of ...
An EPTAS for Scheduling on Unrelated Machines of Few Different Types
AbstractIn the classical problem of scheduling on unrelated parallel machines, a set of jobs has to be assigned to a set of machines. The jobs have a processing time depending on the machine and the goal is to minimize the makespan, that is, the maximum ...
An Almost Ideal Coordination Mechanism for Unrelated Machine Scheduling
Coordination mechanisms aim to mitigate the impact of selfishness when scheduling jobs to different machines. Such a mechanism defines a scheduling policy within each machine and naturally induces a game among the selfish job owners. The desirable ...
Comments