Approximately Efficient Cost-Sharing Mechanisms
<|reference_start|>Approximately Efficient Cost-Sharing Mechanisms: We make three different types of contributions to cost-sharing: First, we identify several new classes of combinatorial cost functions that admit incentive-compatible mechanisms achieving both a constant-factor approximation of budget-balance and a polylogarithmic approximation of the social cost formulation of efficiency. Second, we prove a new, optimal lower bound on the approximate efficiency of every budget-balanced Moulin mechanism for Steiner tree or SSRoB cost functions. This lower bound exposes a latent approximation hierarchy among different cost-sharing problems. Third, we show that weakening the definition of incentive-compatibility to strategyproofness can permit exponentially more efficient approximately budget-balanced mechanisms, in particular for set cover cost-sharing problems.<|reference_end|>
@article{roughgarden2006approximately,
    title={Approximately Efficient Cost-Sharing Mechanisms},
    author={Tim Roughgarden (Stanford University) and Mukund Sundararajan
  (Stanford University)},
    journal={arXiv preprint arXiv:cs/0606127},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0606127},
    primaryClass={cs.GT}
}