Today I read a paper titled “Approximately Efficient Cost-Sharing Mechanisms”
The abstract is:
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.