A complete characterization of group-strategyproof mechanisms of cost-sharing

Emmanouil Pountourakis, Angelina Vidali

Veröffentlichungen: Beitrag in FachzeitschriftArtikelPeer Reviewed


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.
Seiten (von - bis)831-860
FachzeitschriftAlgorithmica: an international journal in computer science
PublikationsstatusVeröffentlicht - 2012

ÖFOS 2012

  • 1020 Informatik


Untersuchen Sie die Forschungsthemen von „A complete characterization of group-strategyproof mechanisms of cost-sharing“. Zusammen bilden sie einen einzigartigen Fingerprint.