Black-box reductions for cost-sharing mechanism design

作者: Konstantinos Georgiou , Chaitanya Swamy

DOI: 10.5555/2095116.2095188

关键词: Facility location problemMathematicsMechanism designBinary logarithmNetwork planning and designMonotone polygonMinificationScheduling (computing)Vickrey–Clarke–Groves auctionMathematical 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.

参考文章(51)
Sushil Bikhchandani, Shurojit Chatterji, Ron Lavi, Ahuva Mu'alem, Noam Nisan, Arunava Sen, Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation Econometrica. ,vol. 74, pp. 1109- 1132 ,(2006) , 10.1111/J.1468-0262.2006.00695.X
Roger B. Myerson, Optimal Auction Design Mathematics of Operations Research. ,vol. 6, pp. 58- 73 ,(1981) , 10.1287/MOOR.6.1.58
Yvonne Bleischwitz, Florian Schoppmann, New efficiency results for makespan cost sharing Information Processing Letters. ,vol. 107, pp. 64- 70 ,(2008) , 10.1016/J.IPL.2008.01.005
Jason D. Hartline, Azarakhsh Malekian, Robert Kleinberg, Bayesian incentive compatibility via matchings symposium on discrete algorithms. ,vol. 92, pp. 734- 747 ,(2011) , 10.5555/2133036.2133094
S. Leonardi, G. Schäfer, A. Gupta, J. Könemann, R. Ravi, An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem symposium on discrete algorithms. pp. 1153- 1162 ,(2007) , 10.5555/1283383.1283507
Hervé Moulin, Incremental cost sharing: characterization by coalition strategy-proofness Social Choice and Welfare. ,vol. 16, pp. 279- 320 ,(1999) , 10.1007/S003550050145
Michael Saks, Lan Yu, Weak monotonicity suffices for truthfulness on convex domains electronic commerce. pp. 286- 293 ,(2005) , 10.1145/1064009.1064040
Jason D. Hartline, Brendan Lucier, Bayesian algorithmic mechanism design Proceedings of the 42nd ACM symposium on Theory of computing - STOC '10. pp. 301- 310 ,(2010) , 10.1145/1806689.1806732
Yvonne Bleischwitz, Burkhard Monien, Fair cost-sharing methods for scheduling jobs on parallel machines Journal of Discrete Algorithms. ,vol. 7, pp. 280- 290 ,(2009) , 10.1016/J.JDA.2009.02.001
Theodore Groves, Incentives in Teams Econometrica. ,vol. 41, pp. 617- 631 ,(1973) , 10.2307/1914085