  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.
