Approximately Efficient Cost-Sharing Mechanisms
| dc.creator | Roughgarden, Tim | |
| dc.creator | Sundararajan, Mukund | |
| dc.date | 2006-06-30 | |
| dc.date.accessioned | 2026-07-07T07:13:08Z | |
| dc.date.available | 2026-07-07T07:13:08Z | |
| dc.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. | |
| dc.description | latex source, 22 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/cs/0606127 | |
| dc.identifier | http://arxiv.org/abs/cs/0606127 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/112338 | |
| dc.subject | Computer Science and Game Theory | |
| dc.subject | F.2.0 | |
| dc.title | Approximately Efficient Cost-Sharing Mechanisms | |
| dc.type | text |