2006/06/30 by Tim Roughgarden, Mukund Sundararajan, Roughgarden, Tim +1
Computer Science · #Computer Science and Game Theory (cs.GT) #F.2.0 #FOS: Computer and information sciences #cs.GT
paper · pdf · doi:10.48550/arxiv.cs/0606127
latex source, 22 pages, 1 figure
arxiv created 2006/06/30 · arxiv updated 2009/12/01
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.