Black-box reductions for cost-sharing mechanism design

Konstantinos Georgiou and Chaitanya Swamy

Games and Economic Behavior, 2019, vol. 113, issue C, 17-37

Abstract: 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, α-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(αlog⁡n)-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 ρ-approximation for the problem of finding a min-cost solution for a set of players yields a truthful, no-bossy, (ρ+1)-approximation for the SCM problem (and hence, a truthful (ρ+1)log⁡n-approximation cost-sharing mechanism). These reductions yield the first, or improved, polytime cost-sharing mechanisms for a variety of problems.

Keywords: Algorithmic mechanism design; Cost-sharing mechanisms; Linear programming; Approximation algorithms; Black-box reductions (search for similar items in EconPapers)
JEL-codes: C61 D61 D71 D82 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899825613001292
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:113:y:2019:i:c:p:17-37

DOI: 10.1016/j.geb.2013.08.012

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().