Computer Science – Computer Science and Game Theory
Scientific paper
2010-01-12
Computer Science
Computer Science and Game Theory
29 pages
Scientific paper
We study the problem of designing group-strategyproof cost-sharing mechanisms. The players report their bids for getting serviced and the mechanism decides which players are going to be serviced and how much each one of them is going to pay. We determine three conditions: \emph{Fence Monotonicity}, \emph{Stability} of the allocation and \emph{Validity} of the tie-breaking rule that are necessary and sufficient for group-strategyproofness, regardless of the cost function. Fence Monotonicity puts restrictions only on the payments of the mechanism and stability only on the allocation. Consequently Fence Monotonicity characterizes group-strategyproof cost-sharing schemes. Finally, we use our results to prove that there exist families of cost functions, where any group-strategyproof mechanism has unbounded approximation ratio.
Pountourakis Emmanouil
Vidali Angelina
No associations
LandOfFree
A complete characterization of group-strategyproof mechanisms of cost-sharing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A complete characterization of group-strategyproof mechanisms of cost-sharing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A complete characterization of group-strategyproof mechanisms of cost-sharing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-459384