| In a cost-sharing problem, several participants with unknown preferences vie to receive some good or service, and each possible outcome has a known cost. A cost-sharing mechanism is a protocol that decides which participants are allocated service and at what prices. Three desirable properties of a cost-sharing mechanism are: incentive-compatibility, meaning that participants are motivated to bid their true private value for receiving the good; budget-balance, meaning that the mechanism recovers its incurred cost with the prices charged; and economic efficiency, meaning that the cost incurred and the value to the participants are traded off in an optimal way. These three goals have been known to be mutually incompatible for thirty years. Nearly all the work on cost-sharing mechanism design by the economics and computer science communities has focused on achieving two of these goals while completely ignoring the third. In contrast, we ask: How well can incentive-compatible, budget-balanced mechanisms approximate economic efficiency?;We make three contributions. First, we investigate the efficiency loss of Moulin mechanisms, the only known framework for designing incentive-compatible, budget-balanced cost-sharing mechanisms. We prove simultaneous approximate budget-balance and approximate efficiency guarantees for mechanisms for a wide range of cost-sharing problems, including all submodular, metric facility location, and Steiner tree problems. Our key technical tool is an exact characterization of worst-case efficiency loss in Moulin mechanisms.;Second, we propose acyclic mechanisms, a new framework for designing truthful and approximately budget-balanced cost-sharing mechanisms. Acyclic mechanisms strictly generalize Moulin mechanisms and offer the following advantages. It is easier to design acyclic mechanisms than Moulin mechanisms: many classical primal-dual algorithms naturally induce a non-Moulin acyclic mechanism with good performance guarantees. Further, for important classes of cost-sharing problems, acyclic mechanisms have exponentially better budget-balance and economic efficiency than Moulin mechanisms.;Third, we establish a lower bound on the efficiency loss that applies to all incentive compatible, budget-balanced cost-sharing mechanisms, including randomized mechanisms that are only truthful in expectation, and only beta-budget-balanced in expectation. Our lower bound applies even to the simple and central special case of the excludable public good problem, and establishes that there exists a simple mechanism that is worst-case optimal (up to constant factors) for a very general class of cost-sharing problems, i.e., those with monotone cost functions. This mechanism, unfortunately, does not have a poly-time implementation. However, there do exist poly-time acyclic mechanisms that are worst-case optimal (up to constant factors) for a wide-variety of cost-sharing problems including submodular cost, metric facility location and set cover problems. |
