Truthful mechanism design for multidimensional scheduling via cycle monotonicity

• 成果类型: Article; Proceedings Paper
• 署名作者: Lavi, Ron; Swamy, Chaitanya
• 署名单位: Technion Israel Institute of Technology; University of Waterloo
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2008.08.001
• 发表日期: 2009
• 页码: 99-124

摘要

We consider the makespan-minimization problem Oil unrelated machines in the context of algorithmic mechanism design. No truthful mechanisms with non-trivial approximation guarantees are known for this multidimensional domain. We study a well-motivated special case (also a multidimensional domain), where the processing time of a job on each machine is either low or high. We give a general technique to convert any c-approximation algorithm (in a black-box fashion) to a 3c-approximation truthful-in-expectation mechanism. Our construction uses fractional truthful mechanisms as a building block, and builds upon a technique of Lavi and Swamy [Lavi, R., Swamy, C., 2005. Truthful and near-optimal mechanism design via linear programming. In: Proc. 46th FOCS, pp. 595-604]. When all jobs have identical low and high values, we devise a deterministic 2-approximation truthful mechanism. The chief novelty of our results is that we do not utilize explicit price definitions to prove truthfulness. Instead we design algorithms that satisfy cycle monotonicity [Rochet, J., 1987. A necessary and sufficient condition for rationalizability in a quasilinear context. J. Math. Econ. 16, 191-200], a necessary and sufficient condition for truthfulness in multidimensional settings; this is the first work that leverages this characterization. (C) 2008 Elsevier Inc. All rights reserved.