We make three different types of contributions to cost-sharing: First, weidentify several new classes of combinatorial cost functions that admitincentive-compatible mechanisms achieving both a constant-factor approximationof budget-balance and a polylogarithmic approximation of the social costformulation of efficiency. Second, we prove a new, optimal lower bound on theapproximate efficiency of every budget-balanced Moulin mechanism for Steinertree or SSRoB cost functions. This lower bound exposes a latent approximationhierarchy among different cost-sharing problems. Third, we show that weakeningthe definition of incentive-compatibility to strategyproofness can permitexponentially more efficient approximately budget-balanced mechanisms, inparticular for set cover cost-sharing problems.
Blogged with Flock