Statistical Cost Sharing
We study the cost sharing problem for cooperative games in situations where the cost function C is not available via oracle queries, but must instead be learned from samples drawn from a distribution, represented as tuples (S, C(S)), for different subsets S of players. We formalize this approach, which we call STATISTICAL COST SHARING, and consider the computation of the core and the Shapley value. Expanding on the work by Balcan et al. [2015], we give precise sample complexity bounds for computing cost shares that satisfy the core property with high probability for any function with a non-empty core. For the Shapley value, which has never been studied in this setting, we show that for submodular cost functions with bounded curvature  it can be approximated from samples from the uniform distribution to a p 1  factor, and that the bound is tight. We then define statistical analogues of the Shapley axioms, and derive a notion of statistical Shapley value and that these can be approximated arbitrarily well from samples from any distribution and for any function.
This paper studies cost sharing in cooperative games. There is a ground set N of players and a cost function C that maps subsets S of N to a real-valued cost C(S). The goal is to split the entire cost of the ground set C(N) among the players in such a way that certain desirable properties are satisfied, such as the “core property” (defined in Section 2.1) or the “Shapley axioms” (defined in Section 2.2). Prior work in the cost sharing literature has designed algorithms computing the cost shares which have oracle access to the underlying cost function C. Recent work by Balcan, Procaccia, and Zick in IJCAI 2015 studies the learning theoretic setting where the algorithm does not have oracle access but receives a sample of subsets labeled by their cost {(S1, C(S1)), (S2, C(S2)), …, (Sm, C(Sm))}. In this statistical cost sharing model, the authors of the present paper design sample efficient and computationally efficient learning algorithms that compute cost shares that (approximately) satisfy various properties with high probability.
From what I understand, in Balcan et al.’s IJCAI 2015 paper, they showed that for some games, it is possible to efficiently compute a “probably approximately stable core” (Definition 3) using a polynomial number of samples and then in the arXiv paper published a year later they showed that this is true for all games with a non-empty core. This matches Theorem 1 of the present paper. The present paper builds on Balcan et al.’s work by defining two other notions of an approximate core (Definition 3). They prove various upper and lower bounds on sample complexity and computability for these other notions (Theorems 2 and 3).
Finally, the authors study cost shares that approximate the “Shapley value” which is a solution to the cost sharing problem satisfying several desirable properties. They show that if the cost function is a submodular function, then the extent to which the Shapley value can be approximated from samples from the uniform distribution/any bounded product distribution depends on the submodular function’s curvature (with upper and lower bounds). The also show that if the cost function is a coverage function, then it can’t be approximated from samples over the uniform distribution.
Overall, I think this paper makes a solid contribution to an interesting and applicable subject area. There are a few obvious ways the theorems could be improved:
- Theorem 2: It’s too bad that the sample complexity depends on the spread of C since it seems reasonable that the spread of C might be comparable to n in many settings. Whether or not the dependence can be removed is especially interesting since Theorem 1 has no dependence on the spread. Do the authors have any intuition about whether or not the dependence on the spread is necessary?
- Theorem 4: Can this theorem be generalized to other distributions? If the authors have any interesting insights into the key technical challenge here, that would be a nice addition to the discussion.
I think the axioms for the data-dependent Shapley value could be better motivated. Specifically, the symmetry and zero element axioms seem a bit unintuitive because there’s no connection to the cost function. To me, a more natural distributional parallel to the original symmetry condition would be something like, “For all i and j, if Pr_{S \sim D}[C(S \cup {i}) = C(S \cup {j})] >= ½, then \phi_i^D = \phi_j^D” (I chose ½ arbitrarily). Also, in my opinion, a more natural distributional parallel for the original zero element condition could be “For all i, if Pr_{S \sim D}[C(S \cup {i}) – C(S) = 0] >= ½, then \phi_i^D = 0.” 
Small questions/comments:
- I think Theorem 1 should say “probably approximately stable core.”
- In the proof sketch of Theorem 4, what is C_{A_{sigma < i}}(i)?
=======After author feedback=======
Thanks, it would be great to include examples where a dependence on the spread is necessary. And I see, that's a fair point about how you have limited latitude in crafting alternative characterizations.