Abstract | ||
---|---|---|
A cost sharing scheme is a set of rules defining how to share the cost of a service (often computed by solving a combinatorial optimization problem) amongst serviced customers. A cost sharing scheme is cross-monotonic if it satisfies the property that everyone is better off when the set of people who receive the service expands. Cross-monotonic cost sharing schemes are used to define group-strategyproof mechanisms. In this paper, we investigate the limitations imposed by the cross-monotonicity property on cost-sharing schemes for several combinatorial optimization games including edge cover, vertex cover, set cover, metric facility location, maximum flow, arborescence packing, and maximum matching. We develop a novel technique based on the probabilistic method for proving upper bounds on the budget-balance factor of cross-monotonic cost sharing schemes, deriving tight or nearly-tight bounds for each game that we study. For the set cover game, which generalizes many of the above games, we show that no cross-monotonic cost sharing scheme can recover more than a O(1/n) fraction of the total cost, respectively, and thus we can not hope to use a set-cover cost sharing scheme as a black box for the cost sharing schemes of covering games. For the vertex cover game, we show no cross-monotonic cost sharing scheme can recover more than a O(n-1/3), demonstrating that cross-monotonicity is strictly harder to achieve than the core property (vertex cover games have a solution in the core that is 1/2-budget balanced). For the facility location game, we show that there is no cross-monotonic cost sharing scheme that recovers more than a third of the total cost. This result together with a recent 1/3-budget-balanced cross-monotonic cost sharing scheme of Pál and Tardos [16] closes the gap for the facility location game. Finally, we study the implications of our results on the existence of group-strategyproof mechanisms. We observe that the definition of group-strategyproofness does not exclude trivial mechanisms that recover all the cost. However, with extra assumptions, we show that group-strategyproof mechanisms give rise to cross-monotonic cost sharing schemes and therefore our upper bounds hold.
|
Year | DOI | Venue |
---|---|---|
2005 | 10.5555/1070432.1070516 | SODA: Symposium on Discrete Algorithms |
DocType | ISBN | Citations |
Conference | 978-0-89871-585-9 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nicole Immorlica | 1 | 1636 | 100.87 |
Mohammad Mahdian | 2 | 2689 | 226.62 |
VAHAB S. MIRROKNI | 3 | 4309 | 287.14 |