Timezone: »

 
Poster
Statistical Cost Sharing
Eric Balkanski · Umar Syed · Sergei Vassilvitskii

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #222
in Posters Tue »

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, 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 curvature bounded curvature kappa it can be approximated from samples from the uniform distribution to a sqrt{1 - kappa} 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.

Keywords: Game Theory and Computational Economics
[ Paper] 

Author Information

Eric Balkanski (Harvard University)
Umar Syed (Google Research)
Sergei Vassilvitskii (Google)

More from the Same Authors