Truthful mechanism design via correlated tree rounding

• 成果类型: Article
• 署名作者: Azar, Yossi; Hoefer, Martin; Maor, Idan; Reiffenhaeuser, Rebecca; Voecking, Berthold
• 署名单位: Tel Aviv University; Max Planck Society; Saarland University; RWTH Aachen University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1068-5
• 发表日期: 2017
• 页码: 445-469
• 关键词: approximation algorithms; randomized mechanisms; Lower bounds

摘要

A powerful algorithmic technique for truthful mechanism design is the maximal-in-distributional-range (MIDR) paradigm. Unfortunately, many such algorithms use heavy algorithmic machinery, e.g., the ellipsoid method and (approximate) solution of convex programs. In this paper, we present a correlated rounding technique for designing mechanisms that are truthful in expectation. It is elementary and can be implemented quickly. The main property we rely on is that the domain offers fractional optimum solutions with a tree structure. In auctions based on the generalized assignment problem, each bidder has a publicly known knapsack constraint that captures the subsets of items that are of value to him. He has a private valuation for each item and strives to maximize the value of assigned items minus payment. For this domain we design a truthful 2-approximate MIDR mechanism for social welfare maximization. It avoids using the ellipsoid method or convex programming. In contrast to some previous work, our mechanism achieves exact truthfulness. In restricted-related scheduling with selfish machines, each job comes with a public weight, and it must be assigned to a machine from a public job-specific subset. Each machine has a private speed and strives to maximize payments minus workload of jobs assigned to it. Here we design a mechanism for makespan minimization. This is a single-parameter domain, but the approximation status of the optimization problem is similar to unrelated machine scheduling: The best known algorithm obtains a (non-truthful) 2-approximation for unrelated machines, and there is 1.5-hardness. Our mechanism matches this bound with a truthful 2-approximation.