Name
Abstract | ||
|---|---|---|
Assuming strict consumer sovereignty (CS*), when can costsharing mechanisms simultaneously be group-strategyproof (GSP) and β-budget-balanced (ß-BB)? Moulin mechanisms are GSP and 1-BB for submodular costs. We overcome the submodularity requirement and instead consider arbitrary--yet symmetric--costs: - Already for 4 players, we show that symmetry of costs is not sufficient for the existence of a GSP and 1-BB mechanism. However, for only 3 players, we give a GSP and 1-BB mechanism. - We introduce two-price cost-sharing forms (2P-CSFs) that define players' cost shares and present a novel mechanism that is GSP given any such 2P-CSF. For subadditive costs, we give an algorithm to compute 2P-CSFs that are √17+1/4 -BB (≈ 1.28). This result is then shown to be tight for 2P-CSFs. Yet, this is a significant improvement over 2-BB, which is the best Moulin mechanisms can achieve. We give applications to the minimum makespan scheduling problem. A key feature of all our mechanisms is a preference order on the set of players. Higher cost shares are always payed by least preferred players. |
Year | Venue | Keywords |
|---|---|---|
2007 | MFCS | subadditive cost,moulin mechanism,key feature,higher cost share,novel mechanism,cost share,minimum makespan scheduling problem,submodular cost,preference order,1-bb mechanism |
Field | DocType | Volume |
Monotonic function,Mathematical economics,Job shop scheduling,Computer science,Submodular set function,Moulin,Cost share,Subadditivity,Consumer sovereignty,Power of two | Conference | 4708 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-74455-X | 3 |
PageRank | References | Authors |
0.41 | 15 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yvonne Bleischwitz | 1 | 28 | 2.59 |
| Burkhard Monien | 2 | 2199 | 279.35 |
| Florian Schoppmann | 3 | 285 | 13.36 |
| Karsten Tiemann | 4 | 110 | 7.71 |