Source-linked AI summary
Bounding the Estimation Error of Sampling-based Shapley Value Approximation
Sasan Maleki, Long Tran-Thanh, Greg Hines, Talal Rahwan, Alex Rogers
TL;DR
Approximating the Shapley value for general characteristic-function games remains difficult because existing bounds are asymptotic and fail to quantify finite-sample error. The paper establishes non-asymptotic bounds using variance- and range-based concentration inequalities, improves the range bound when the range is large relative to the Shapley value, and evaluates stratified sampling. These results provide finite-sample error guarantees and demonstrate that stratification can further improve bounds.
Problem
General characteristic-function games still lack a finite-sample approximation guarantee for the Shapley value, while the existing bound is asymptotic.
Method
The paper applies simple random sampling with Chebyshev’s or Hoeffding’s inequality and proposes stratified sampling for Shapley-value estimation.
Results
The paper establishes non-asymptotic bounds for known variance or range, improves the large-range bound from O(r/m) to O(sqrt(r/m)), and demonstrates stratified sampling’s effectiveness.
Takeaways & Limitations
Finite-sample Shapley-value approximation can be bounded using limited information about marginal contributions, with stratification offering further bound improvements.
Takeaways & Limitations
The bounds require information such as marginal-contribution variance or range, and stratified sampling is demonstrated only for games with coalition values bounded by a linear function of coalition size.
Abstract
from arXiv · showhide
The Shapley value is arguably the most central normative solution concept in cooperative game theory. It specifies 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 \textit{characteristic function} representation, the only attempt to approximate the Shapley value for the general class of games is due to Castro \textit{et al.} \cite{castro}. While this algorithm provides a bound on the approximation error, this bound is \textit{asymptotic}, meaning that it only holds when the number of samples increases to infinity. On the other hand, when a finite number of samples is drawn, an unquantifiable 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 \textit{variance}, and (ii) the \textit{range}, of the players' marginal contributions is known. Furthermore, for the second case, we show that when the range is significantly large relative to the Shapley value, the bound can be improved (from $O(\frac{r}{m})$ to $O(\sqrt{\frac{r}{m}})$). Finally, we propose, and demonstrate the effectiveness of using stratified sampling for improving the bounds further.
1 Introduction
The Shapley value is widely important but difficult to compute for general characteristic-function games, where existing approximation bounds are asymptotic. This paper develops finite-sample bounds using concentration inequalities and stratified sampling.
- The Shapley value has broad theoretical and practical importance, with applications ranging from political conflicts to customer satisfaction and cost sharing.
- Computing the Shapley value has exponential time complexity in general, limiting practical use to games with relatively few players.
- For general characteristic-function games, prior approximation work provided an asymptotic bound whose finite-sample error was not quantified.
- The paper uses simple random sampling and non-asymptotic concentration inequalities to estimate the Shapley value when marginal-contribution variance or range is known.
- When the marginal-contribution range is significantly large relative to the Shapley value, the estimation bound improves from O(r/m) to O(sqrt(r/m)).
- The paper proposes stratified sampling and demonstrates it on games whose coalition values are bounded by a linear function of coalition size.
- The paper identifies its novelty as applying these inequalities to general Shapley-value approximation and using stratified sampling for a more efficient bound.
2 Preliminaries
A characteristic-function game assigns values to coalitions of players. The Shapley value represents a player's expected marginal contribution across uniformly random joining orders and is uniquely characterized by standard fairness axioms.
- A cooperative game in characteristic-function form consists of players N and a function v mapping every coalition C ⊆ N to a real value.
- A player's marginal contribution to coalition C is the difference v(C ∪ {i}) − v(C).
- The Shapley value is a player's expected marginal contribution when all n! joining orders are equally likely.
- The Shapley value satisfies symmetry, efficiency, and additivity, which uniquely define the value of a game.
3 Related Work
Research on Shapley-value computation spans efficient algorithms for restricted game classes, alternative representations, and sampling-based approximations. For general characteristic-function games, concentration inequalities provide a way to address finite-sample estimation, while CLT-based bounds face unquantified error without distributional knowledge.
- Prior work computes Shapley values efficiently for restricted games, including minimum cost spanning tree and induced subgraph games.
- Approximation methods target voting, weighted voting, power-index, k-majority, and supermodular games using simulation, multilinear extensions, sampling, or concentration inequalities.
- Alternative representations impose assumptions on coalition-value computation and can enable Shapley-value computation linear in input size.
- Simple random sampling estimates the Shapley value by treating it as the mean of a population of marginal contributions.
- The CLT gives an asymptotic normal approximation, but finite-sample error depends on the convergence gap and cannot generally be quantified without knowing the population distribution.The Berry–Esseen theorem can bound this error only under strong assumptions, while general-game marginal contributions may follow any distribution.
- Concentration inequalities offer distribution-agnostic bounds: Chebyshev uses variance information, Hoeffding gives exponential deviation control for bounded variables, and Vu’s inequality addresses a heavy-tailed setting under conditions.Such general-purpose bounds may be weaker than bounds exploiting a known distribution.
4 Simple Random Sampling
The section estimates Shapley values with simple random sampling and derives finite-sample error bounds when marginal-contribution variance or range is known. It also develops an improved range-dependent bound under a condition relating the Shapley value to the marginal-contribution range.
- Simple random sampling: The estimator is the mean of m random marginal contributions, with the required sample size determined separately for known variance and known range.Samples can be reused across players, so the number needed for all players equals the largest requirement among them.
- Known variance: m ≥ ⌈σ2/(δǫ2)⌉ guarantees the specified estimation-error probability when the maximum marginal-contribution variance σ2 is known.This bound follows by applying Chebyshev’s inequality to the sum of sampled marginal contributions.
- Known range: Hoeffding’s inequality yields a finite-sample bound when the range r of marginal contributions is known.The analysis applies the inequality to the sum of m sampled contributions and targets a failure probability at most δ.
- Improved range bound: The initial range-based estimation error is O(r/m), making the range term dominant when r is large.This motivates seeking a bound sublinear in r.
- Improved range bound: Under φ = O(rf(n) ln n), the improved range-based error is O(√(r/m)) with high probability.The improved dependence on r trades off against weaker efficiency in 1/m and does not provide an exact coefficient because it is expressed in big-O notation.
5 Stratified Sampling for Coalitions
Stratified sampling partitions coalitions by size and allocates samples across homogeneous strata to tighten Shapley-value estimation bounds relative to simple random sampling. The analysis derives an allocation strategy and shows improved precision, especially when the sample size is sufficiently large.
- Stratification: The method assumes strata contain marginal contributions with similar values, enabling Hoeffding-based error bounds within each stratum.The paper’s hypothesis is that such stratification can bound estimation error more efficiently than the preceding simple-random-sampling bounds.
- Sample allocation: Samples are allocated across strata to minimize the total Shapley-value estimation error, with fractional optimal allocations relaxed before integer adjustment.The integer constraint makes the exact optimization hard; the algorithm rounds allocations and distributes remaining samples sequentially.
- Stratification: Stratified sampling partitions coalitions not containing player i into n strata S0, S1, …, Sn−1 according to coalition size.Stratum Sk contains coalitions of size k, and rk is the range of player i’s marginal contributions within that stratum.
- Sample allocation: The estimated global Shapley value is formed by combining the estimated expected marginal contribution from each stratum.The analysis introduces φk for each stratum, estimates it using mk samples, and then aggregates the stratum estimates.
- Error bounds: With at least (1−δ)^n probability, the stratified estimator satisfies the derived total estimation-error bound.The bound follows by combining the per-stratum Hoeffding guarantees and the relationship between stratum ranges and coalition size.
- Error bounds: When m > (n+1)^2, the simple-random-sampling bound is significantly higher than the stratified bound, making stratification especially effective for large sample sizes.The comparison is made against applying Hoeffding’s inequality to all m samples without stratification.
6 Conclusions and Future Work
The paper establishes non-asymptotic Shapley-value estimation bounds for known marginal-contribution variance or range, improves the range-based bound in a specified regime, and uses stratified sampling to improve bounds further. Future work extends stratified sampling to classes such as weighted voting games.
- Contributions: The paper establishes non-asymptotic Shapley-value estimation bounds when marginal-contribution variance or range is known.These bounds address the asymptotic limitation of the state-of-the-art algorithm.
- Contributions: When the marginal-contribution range is significantly large relative to the Shapley value, the estimation bound can be improved.The paper also proposes stratified sampling and demonstrates its effectiveness in improving the bounds.
- Future work: Future work will extend stratified sampling techniques to classes of interest such as weighted voting games.