English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  A Complete Characterization of Group-strategyproof Mechanisms of Cost-sharing

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-15DF-F Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-2C2B-9
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Pountourakis, Emmanouil1, Author
Vidali, Angelina2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 20102010
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 536792
DOI: 10.1007/978-3-642-15775-2_13
URI: http://dx.doi.org/10.1007/978-3-642-15775-2_13
Other: Local-ID: C1256428004B93B8-453E3EDE938E1609C125781B00423C77-Vidali2010
 Degree: -

Event

show
hide
Title: 18th Annual European Symposium on Algorithms
Place of Event: Liverpool, UK
Start-/End Date: 2010-09-06 - 2010-09-08

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms - ESA 2010
  Subtitle : 18th Annual European Symposium. Pt. I
  Abbreviation : ESA 2010
Source Genre: Proceedings
 Creator(s):
de Berg, Mark1, Editor
Meyer, Ulrich2, Editor           
Affiliations:
1 External Organizations, ou_persistent22            
2 Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 146 - 157 Identifier: ISBN: 978-3-642-15774-5

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 6346 Sequence Number: - Start / End Page: - Identifier: -