Cooperative Cost Sharing via Incremental Mechanisms
Please always quote using this URN:urn:nbn:de:0296-matheon-6434
- For many fundamental cooperative cost sharing games, especially when costs are supermodular, it is known that Moulin mechanisms inevitably suffer from poor budget balance factors. Mehta, Roughgarden, and Sundararajan recently introduced acyclic mechanisms, which achieve a slightly weaker notion of group-strategyproofness, but leave more flexibility to improve upon the approximation guarantees with respect to budget balance and social cost. In this paper, we provide a very simple but powerful method for turning any rho-approximation algorithm for a combinatorial optimization problem into a rho-budget balanced acyclic mechanism. Hence, we show that there is no gap between the best possible approximation guarantees of full-knowledge approximation algorithms and weakly group-strategyproof cost sharing mechanisms. The applicability of our method is demonstrated by deriving mechanisms for scheduling and network design problems which beat the best possible budget balance factors of Moulin mechanisms. By elaborating our framework, we provide means to construct weakly group-strategyproof mechanisms with approximate social cost. The mechanisms we develop for completion time scheduling problems perform surprisingly well by achieving the first constant budget balance and social cost factors.
Author: | Janina Brenner, Guido Schäfer |
---|---|
URN: | urn:nbn:de:0296-matheon-6434 |
Referee: | Martin Skutella |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2009/07/31 |
Release Date: | 2009/07/31 |
Tag: | |
Institute: | Technische Universität Berlin |
Preprint Number: | 650 |