Black-box reductions for cost-sharing mechanism design

• 成果类型: Article
• 署名作者: Georgiou, Konstantinos; Swamy, Chaitanya
• 署名单位: University of Waterloo
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2013.08.012
• 发表日期: 2019
• 页码: 17-37
• 关键词: Algorithmic mechanism design; Cost-sharing mechanisms; linear programming; Approximation algorithms; Black-box reductions

摘要

We consider the design of strategyproof cost-sharing mechanisms. We give two simple, but extremely versatile, black-box reductions, that in combination reduce the cost-sharing mechanism-design problem to the algorithmic problem of finding a min-cost solution for a set of players. Our first reduction shows that any truthful, alpha-approximation mechanism for the social-cost minimization (SCM) problem satisfying a technical no-bossiness condition can be morphed into a truthful mechanism that achieves an O(alpha logn)-approximation where the prices recover the cost incurred. Thus, we decouple the approximation and cost-recovery objectives. Our second reduction nicely complements the first one by showing that any LP-relative rho-approximation for the problem of finding a min-cost solution for a set of players yields a truthful, no-bossy, (rho + 1)-approximation for the SCM problem (and hence, a truthful (rho+1) logn-approximation cost-sharing mechanism). These reductions yield the first, or improved, polytime cost-sharing mechanisms for a variety of problems. (C) 2013 Elsevier Inc. All rights reserved.