Bounding the Estimation Error of Sampling-based Shapley Value Approximation

Monday, May 5, 2014, 11:00am – 12:30pm
Presented by Sasan Maleki, Long Tran-Thanh, Greg Hines, Talal Rahwan, and Alex Rogers
Located in TBD
In track CoopMAS2014

The Shapley value is arguably the most central normative solution concept in cooperative game theory. It speci es a unique way in which the reward from cooperation can be “fairly” divided among players. While it has a wide range of real world applications, its use is in many cases hampered by the hardness of its computation. A number of researchers have tackled this problem by (i) focusing on classes of games where the Shapley value can be computed efficiently, or (ii) proposing representation formalisms that facilitate such efficient computation, or (iii) approximating the Shapley value in certain classes of games. For the classical characteristic function representation, the only attempt to approximate the Shapley value for the general class of games is due to Castro et al. [5]. While this algorithm provides a bound on the approximation error, this bound is asymptotic, meaning that it only holds when the number of samples increases to infi nity. On the other hand, when a finite number of samples is drawn, an unquanti able error is introduced, meaning that the bound no longer holds. With this in mind, we provide non-asymptotic bounds on the estimation error for two cases: where (i) the variance, and (ii) the range, of the players’ marginal contributions is known. Furthermore, for the second case, we show that when the range is signi cantly large relative to the Shapley value, the bound can be improved (from O(r=m) to O(√r=m)). Finally, we propose, and demonstrate the e ectiveness of using strati ed sampling for improving the bounds further.