A DETERMINISTIC TRUTHFUL PTAS FOR SCHEDULING RELATED MACHINES

作者：Christodoulou George^*; Kovacs Annamaria

来源：SIAM Journal on Computing, 2013, 42(4): 1572-1595.

DOI：10.1137/120866038

• algorithmic game theory
• algorithmic mechanism design
• truthful scheduling mechanisms
• related machine scheduling

Scheduling on related machines (Q||C-max) is one of the most important problems in the field of algorithmic mechanism design. Each machine is controlled by a selfish agent and her valuation function can be expressed via a single parameter, her speed. Archer and Tardos [Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV, 2001, pp. 482-491] showed that, in contrast to other similar problems, a (nonpolynomial) allocation that minimizes the makespan can be truthfully implemented. On the other hand, if we leave out the game-theoretic issues, the complexity of the problem has been completely settled-the problem is strongly NP-hard, while there exists a polynomial-time approximation scheme (PTAS) [D. S. Hochbaum and D. B. Shmoys, SIAM J. Comput., 17 (1988), pp. 539-551, and L. Epstein and J. Sgall, Algorithmica, 39(1) (2004), pp. 43-57]. This problem is the most well studied in single-parameter algorithmic mechanism design. It gives an excellent ground to explore the boundary between truthfulness and efficient computation. Since the work of Archer and Tardos, quite a lot of deterministic and randomized mechanisms have been suggested. Recently, a breakthrough result [P. Dhangwatnotai, S. Dobzinski, S. Dughmi, and T. Roughgarden, Proceedings of the 49th IEEE Symposium of Foundations of Computer Science, Philadelphia, 2008, pp. 15-24] showed that a randomized, truthful-in-expectation PTAS exists. On the other hand, for the deterministic case, the best known approximation factor is 2.8 [A. Kovacs, Algorithms-ESA 2005, 13th Annual European Symposium, 2005, pp. 616-627, and A. Kovacs, J. Discrete Algorithms, 7 (2009), pp. 327-340]. It has been a major open question whether there exists a deterministic truthful PTAS, or whether truthfulness has an essential, negative impact on the computational complexity of the problem. In this paper we give a definitive answer to this important question by providing a truthful deterministic PTAS.

• 出版日期2013