作者: Konstantinos Georgiou , Chaitanya Swamy
关键词: Facility location problem 、 Mathematics 、 Mechanism design 、 Binary logarithm 、 Network planning and design 、 Monotone polygon 、 Minification 、 Scheduling (computing) 、 Vickrey–Clarke–Groves auction 、 Mathematical optimization
摘要: We consider the design of strategyproof cost-sharing mechanisms. give two simple, but extremely versatile, black-box reductions, that in combination reduce mechanism-design problem to algorithmic finding a minimum-cost solution for set players. Our first reduction shows any truthful, α-approximation mechanism social-cost minimization (SCM) satisfying technical no-bossiness condition can be morphed into truthful achieves an O(α log n)-approximation where prices recover cost incurred. Thus, we decouple task truthfully computing outcome with near-optimal social from problem. This is fruitful since mechanism-design, especially single-dimensional problems, relatively well-understood and manageable task. second nicely complements one by showing LP-based ρ-approximation min-cost players yields no-bossy, (ρ + 1)-approximation SCM (and hence, 1)log n-approximation mechanism).These reductions find slew applications, yielding, as corollaries, or improved polytime mechanisms variety problems. For example, our coupled celebrated VCG (with monotone function) obtain O(log Other applications include for: survivable network facility location (FL) problems including capacitated connected FL minimum-makespan scheduling on unrelated machines. results demonstrate contrast current understanding group-strategyproof acyclic mechanisms, strategyproofness allows ample flexibility enabling effectively leverage various results.