de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

A Complete Characterization of Group-strategyproof Mechanisms of Cost-sharing

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45669

Vidali,  Angelina
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Pountourakis, E., & Vidali, A. (2010). A Complete Characterization of Group-strategyproof Mechanisms of Cost-sharing. In M. de Berg, & U. Meyer (Eds.), Algorithms - ESA 2010 (pp. 146-157). Berlin: Springer. doi:10.1007/978-3-642-15775-2_13.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-15DF-F
Abstract
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.