We study the cost sharing problem for cooperative games in situations where the cost function @math is not available via oracle queries, but must instead be derived from data, represented as tuples @math , for different subsets @math of players. We formalize this approach, which we call statistical cost sharing, and consider the computation of the core and the Shapley value, when the tuples are drawn from some distribution @math . Previous work by in this setting showed how to compute cost shares that satisfy the core property with high probability for limited classes of functions. We expand on their work and give an algorithm that computes such cost shares for any function with a non-empty core. We complement these results by proving an inapproximability lower bound for a weaker relaxation. We then turn our attention to the Shapley value. We first show that when cost functions come from the family of submodular functions with bounded curvature, @math , the Shapley value can be approximated from samples up to a @math factor, and that the bound is tight. We then define statistical analogues of the Shapley axioms, and derive a notion of statistical Shapley value. We show that these can always be approximated arbitrarily well for general functions over any distribution @math .
A cost sharing scheme is a set of rules defining how to share the cost of a service (often computed by solving a combinatorial optimization problem) amongst serviced customers. A cost sharing scheme is cross-monotonic if it satisfies the property that everyone is better off when the set of people who receive the service expands. Cross-monotonic cost sharing schemes are used to define group-strategyproof mechanisms. In this paper, we investigate the limitations imposed by the cross-monotonicity property on cost-sharing schemes for several combinatorial optimization games including edge cover, vertex cover, set cover, metric facility location, maximum flow, arborescence packing, and maximum matching. We develop a novel technique based on the probabilistic method for proving upper bounds on the budget-balance factor of cross-monotonic cost sharing schemes, deriving tight or nearly-tight bounds for each game that we study. For the set cover game, which generalizes many of the above games, we show that no cross-monotonic cost sharing scheme can recover more than a O(1 n) fraction of the total cost, respectively, and thus we can not hope to use a set-cover cost sharing scheme as a black box for the cost sharing schemes of covering games. For the vertex cover game, we show no cross-monotonic cost sharing scheme can recover more than a O(n-1 3), demonstrating that cross-monotonicity is strictly harder to achieve than the core property (vertex cover games have a solution in the core that is 1 2-budget balanced). For the facility location game, we show that there is no cross-monotonic cost sharing scheme that recovers more than a third of the total cost. This result together with a recent 1 3-budget-balanced cross-monotonic cost sharing scheme of Pal and Tardos [16] closes the gap for the facility location game. Finally, we study the implications of our results on the existence of group-strategyproof mechanisms. We observe that the definition of group-strategyproofness does not exclude trivial mechanisms that recover all the cost. However, with extra assumptions, we show that group-strategyproof mechanisms give rise to cross-monotonic cost sharing schemes and therefore our upper bounds hold. We develop a general method for turning a primal-dual algorithm into a group strategy proof cost-sharing mechanism. We use our method to design approximately budget balanced cost sharing mechanisms for two NP-complete problems: metric facility location, and single source rent-or-buy network design. Both mechanisms are competitive, group strategyproof and recover a constant fraction of the cost. For the facility location game our cost-sharing method recovers a 1 3rd of the total cost, while in the network design game the cost shares pay for a 1 15 fraction of the cost of the solution. We consider the problem of optimization from samples of monotone submodular functions with bounded curvature. In numerous applications, the function optimized is not known a priori, but instead learned from data. What are the guarantees we have when optimizing functions from sampled data? In this paper we show that for any monotone submodular function with curvature c there is a (1 - c) (1 + c - c^2) approximation algorithm for maximization under cardinality constraints when polynomially-many samples are drawn from the uniform distribution over feasible sets. Moreover, we show that this algorithm is optimal. That is, for any c < 1, there exists a submodular function with curvature c for which no algorithm can achieve a better approximation. The curvature assumption is crucial as for general monotone submodular functions no algorithm can obtain a constant-factor approximation for maximization under a cardinality constraint when observing polynomially-many samples drawn from any distribution over feasible sets, even when the function is statistically learnable. A service is produced for a set of agents. The service is binary, each agent either receives service or not, and the total cost of service is a submodular function of the set receiving service. We investigate strategyproof mechanisms that elicit individual willingness to pay, decide who is served, and then share the cost among them. If such a mechanism is budget balanced (covers cost exactly), it cannot be efficient (serve the surplus maximizing set of users) and vice-versa. We characterize the rich family of budget balanced and group strategyproof mechanisms and find that the mechanism associated with the Shapley value cost sharing formula is characterized by the property that its worst welfare loss is minimal. When we require efficiency rather than budget balance – the more common route in the literature – we find that there is a single Clarke-Groves mechanism that satisfies certain reasonable conditions: we call this the marginal cost pricing mechanism. We compare the size of the marginal cost pricing mechanism's worst budget surplus with the worst welfare loss of the Shapley value mechanism. Perhaps the strongest notion of truth-revealing in a cost sharing method is group strategyproofness. However, matters are not so clear-cut on fairness, and many different, sometimes even conflicting, notions of fairness have been proposed which have relevance in different situations. We present a large class of group strategyproof cost sharing methods, for submodular cost functions, satisfying a wide range of fairness criteria, thereby allowing the service provider to choose a method that best satisfies the notion of fairness that is most relevant to her application. Our class includes the Dutta-Ray egalitarian method as a special case. It also includes a new cost sharing method, which we call the opportunity egalitarian method.   Strategyproof cost-sharing mechanisms, lying in the core, that recover 1 @a fraction of the cost, are presented for the set cover and facility location games: @a=O(log n) for the former and 1:861 for the latter. Our mechanisms utilize approximation algorithms for these problems based on the method of dual-fitting.