A Complete Characterization of Group-Strategyproof Mechanisms of Cost-Sharing

被引：1

作者：

Emmanouil Pountourakis

Angelina Vidali

机构：

[1] Northwestern University,Department of Electrical Engineering and Computer Science

[2] University of Vienna,Theory and Applications of Algorithms Research Group

来源：

Algorithmica | 2012年 / 63卷

关键词：

Cost Function; Budget Balance; Stable Pair; Consumer Sovereignty; Minimum Payment;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We study the problem of designing group-strategyproof cost-sharing mechanisms. The players report their bids for getting serviced and the mechanism decides a set of players that are going to be serviced and how much each one of them is going to pay. We determine three conditions: Fence Monotonicity, Stability of the allocation and Validity of the tie-breaking rule that are necessary and sufficient for group-strategyproofness, regardless of the cost function. Consequently, Fence Monotonicity characterizes group-strategyproof cost-sharing schemes closing an important open problem. Finally, we use our results to prove that there exist families of cost functions, where any group-strategyproof mechanism has arbitrarily poor budget balance.

引用

页码：831 / 860

页数：29

共 9 条

[1] Immorlica N.(2008)Limitations of cross-monotonic cost-sharing schemes ACM Trans. Algorithms 4 1-25
[2] Mahdian M.(1999)Incremental cost sharing: Characterization by coalition strategy-proofness Soc. Choice Welf. 16 279-320
[3] Mirrokni V.S.(1987)A necessary and sufficient condition for rationalizability in a quasi-linear context J. Math. Econ. 16 191-200
[4] Moulin H.(2001)Strategyproof sharing of submodular costs: budget balance versus efficiency Econ. Theory 18 511-533
[5] Rochet J.C.(2001)Algorithmic mechanism design Games Econ. Behav. 35 166-196
[6] Moulin H.(undefined)undefined undefined undefined undefined-undefined
[7] Shenker S.(undefined)undefined undefined undefined undefined-undefined
[8] Nisan N.(undefined)undefined undefined undefined undefined-undefined
[9] Ronen A.(undefined)undefined undefined undefined undefined-undefined

← 1 →