Strategyproof Sharing of Submodular Access Costs: Budget Balance Versus Efficiency

A given set of users share the submodular cost of access to a network (or, more generally, the submodular cost of any idiosyncratic binary good). We compare strategyproof mechanisms that serve the efficient set of users (but do not necessarily balance the budget) with those that exactly cover costs (but are not necessarily efficient). Under the requirements of individual rationality (guaranteeing voluntary participation) and consumer sovereignty (an agent will obtain access if his willingness to pay is high enough), we find: i) a unique strategyproof and efficient mechanism (a variant of the familiar pivotal mechanism) dubbed the marginal contribution mechanism (MC); ii) a whole class of strategyproof and budget-balanced mechanisms, each one corresponding to a certain cost sharing formula; these mechanisms, unlike MC, are immune to manipulations by coalitions. Within the second class, the mechanism associated with the Shapley value cost sharing formula is characterized by the property that its worst welfare loss is minimal. We compare the budget imbalances of MC with the welfare losses of the Shapley value mechanism. Application of these methods to the case of a tree network without congestion is also discussed.