Approximately Efficient Cost-Sharing Mechanisms

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
latex source, 22 pages, 1 figure

Keywords

Computer Science and Game Theory, F.2.0

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/112338

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0606127
 http://arxiv.org/abs/cs/0606127

Collections

arXiv