Approximation Algorithms for the Shapley Value: Taxonomy and Properties

1 Introduction

The notion of a cooperative game is omnipresent and appears in a wide range of fields far beyond its origin of economics. Multiple players solve together a task through cooperation and receive a collective reward that is to be shared among them. Not only would a fair distribution of the reward describe each player's contribution and reward it appropriately, the presence of such a mechanism itself can arguably incentivize collaboration in the first place. The field of machine learning adopted this paradigm, initially to attribute importance to individual features which contribute as players to the generalization performance of a learner [Covert et al., 2020] or to the prediction for a specific instance [Lundberg and Lee, 2017], which are then divided among the feature to obtain importance scores. These scores form an explanation of how the features impact a model's behavior. In light of the rapid increase in complexity of machine learning models, eventually reaching opaqueness and black box nature, combined with the recent demand for trustworthiness of employed models, especially the research branch of explainable AI picked up this methodology to generate feature explanations that seek to provide understanding to the human user.

Simultaneously, this development made a frequently used payoff mechanism for deriving importance scores prominent in machine learning: the well-known Shapley value [Shapley, 1953]. It assigns to each player a payoff based on its average marginal contribution, expressing how much the inclusion of that player to a coalition of other players increases collective benefit. Compared to other alternatives, it uniquely satisfies axioms that arguably capture a widespread understanding of fairness, reinforcing its popularity.

Convincing with this appeal, the Shapley value has found various applications in machine learning that go beyond the well-studied purpose of generating local or global feature explanations [Sundararajan and Najmi, 2020; Covert et al., 2021; Molnar, 2022]. Given the importance scores provided by the Shapley value, it comes naturally to conduct feature selection by favoring those with higher scores [Cohen et al., 2007; Sebasti´an and Gonz´alez-Guill´en, 2024]. However, this approach to perform selection is not limited to features. For instance, one can assign scores to data points in a training set to quantify the utility of each single data point. On this basis, the Shapley value is used for data valuation [Ghorbani and Zou, 2019; Jia et al., 2019; Wu et al., 2023], filtering out harmful outliers and reducing the training set size in general. In a similar vein, one can attribute in federated learning how much predictive performance data owners provide to a joint model [Sim et al., 2020; Liu et al., 2022]. With the subtle difference being that not individual data points are seen as players but whole datasets, each provided by a data owner. In contrast to explanations, the Shapley value provides here an economically-flavored purpose. It rewards clients appropriately for sharing their data, eventually incentivizing participation in the joint learning process. Lastly, one can select not only entities in the data but also within the model itself, thus arriving at model pruning. Akin to data valuation, one can remove base learners with negative scores from ensembles or in general select a significantly smaller subset [Rozemberczki and Sarkar, 2021]. Likewise, the Shapley value is used to prune artificial neural networks by removing single neurons depending on their scores [Ghorbani and Zou, 2020]. Moreover, it is also used for its explanatory character, providing an insight on how the neurons influence prediction. We refer to [Rozemberczki et al., 2022] for an overview of use cases in machine learning. Independent of the actual domain of interest, the Shapley value comes with a considerable drawback, impeding its application. Since a player's Shapley value takes into account its marginal contributions to all feasible subsets of players, its exact computation becomes quickly intractable, severely limiting the potential number of players (and thus features, data points, etc.) that can be considered. In particular, this exponential blowup provably results in NP-hardness for specific cooperative games [Deng and Papadimitriou, 1994]. As a viable alternative to exact computation, a diverse landscape of approximation algorithms has been developed. This subfield has attracted considerable interest in recent years as the importance of reliable and quick estimates for the Shapley value has been recognized, facilitating precise scores to quantify feature importance or pay out data owners. In contrast, closed-form polynomial solutions of the Shapley value have been found only for a small number of model classes in combination with specific formulations of collective benefit, such as decision trees [Lundberg et al., 2020] or graph neural networks [Muschalik et al., 2025].

Contribution. As the literature on approximating the Shapley value has grown in parallel to its spreading relevance in machine learning, we seek to provide an overview of the recently developed methodological landscape and thus solidify the progress made. Categorizing algorithms by their approach and utilized representation of the Shapley value, as well as pointing out connections between them, should provide a better understanding of the field and hopefully spark perspectives for novel work. Although surveys in that direction exist, we intend to contribute in a more conceptual, and universally applicable style that reaches a broader audience not limited to narrow machine learning tasks. Existing surveys are tailored towards feature explanations [Chen et al., 2023; Olsen et al., 2024], put more weight on model-specific estimation methods [Chen et al., 2023], or emphasize a certain algorithmic class without providing a general taxonomy [Lamothe and Ngueveu, 2025]. We distinguish ourselves from these by considering methods that are domain-independent and can handle any cooperative game independent of how collective benefit is modeled. This implies the absence of structural assumptions or leveraging domain-specific heuristics. We believe that this approach appropriately reflects the wide span of applications for the Shapley value.

2 Cooperative Games and the Shapley Value

A cooperative game (N, ν) consists of a player set N and a value function ν : P(N) → R. The player set contains the n involved players in the game and hence, we write N = {1, . . . , n} to keep that abstract nature. These can represent arbitrary objects of interest such as features, data points, or even base learners. To reflect that players can collaborate by forming groups to solve a task, subsets S ⊆ N are called coalitions. The collective benefit that each coalition could generate is specified by the value function as its worth ν(S). Thus, ν is the central component to model a cooperative game. Assuming that all players are willing to cooperate and form the grand coalition N, one is confronted with the question of how to fairly distribute the generated worth ν(N)-ν(∅) among them. The Shapley value [Shapley, 1953] is arguably the most well-known solution and assigns to each player i ∈ N the payoff

It can be interpreted as the weighted average of a player's marginal contributions ∆i := ν(S ∪{i})-ν(S) to all coalitions S ⊆ N -i := N \ {i} to which i could possibly contribute. If it is unclear for which value function ν the Shapley value is considered, we write ϕνi , otherwise in case of no ambiguity we use ϕi. The Shapley value's popularity is rooted in its axiomatic uniqueness as it is the only solution concept to fulfill four desiderata [Shapley, 1953] that are commonly understood to capture fairness:

• Symmetry: Two players with equal marginal contributions, i.e. ∆i(S) = ∆j(S) for all S ⊆ N \ {i, j}, receive the same payoff ϕi = ϕj .
• Dummy player: A player with no contribution, i.e. ∆i(S) = 0 for all S ⊆ N -i , receives no payoff: ϕi = 0.
• Linearity: Scaling ν by a constant c ∈ R scales each player's payoff by c, i.e. ϕν ′ i = ϕνi ·c for the cooperative game (N, ν ′ := ν·c) for all i ∈ N. Each player's payoff in the game (N, ν1 + ν2) resulting from the addition of two games (N, ν1) and (N, ν2), is the sum of the player's payoffs in both games, i.e. ϕν1+ν2 i = ϕν1 i +ϕν2 i .
• Efficiency: The sum of all player's payoffs equals the caused collective benefit, i.e. ∑i∈N ϕi = ν(N)-ν(∅).

3 Approximating Shapley Values

The price paid for its convenient and unique properties is the computational intractability of the Shapley value. Its definition already reveals that in general all 2n many coalitions need to be evaluated for their worth to compute ϕi exactly. Moreover, its exact computation is provably NP-hard for certain structured games whose value function can be specified in polynomial space w.r.t. n [Deng and Papadimitriou, 1994]. This exponential blow-up calls for a circumvention if one seeks to utilize the Shapley value in practice, especially in machine learning with dozens of features and hundreds if not thousands of data points that act as players. One typically addresses this problem by reliably estimating ϕi while keeping the number of evaluations low. In the following, we clarify our considered setting for approximation and list properties by which approximation algorithms are to be distinguished.

3.1 Approximation Problem

We assume a cooperative game (N, ν) with unknown Shapley values ϕ := (ϕ1, . . . , ϕn) to be given such that ν(S) can be evaluated for each coalition S by an approximation algorithm A. The algorithm is expected to output estimates ˆ ϕ := (ˆ ϕ1, . . . , ˆ ϕn) with each ˆ ϕi being close to ϕi, i.e. ˆ ϕi ≈ ϕi. One could also be interested in the estimation of a single particular ϕi, however, we stick to the approximation of all player's Shapley values as this is commonly the case in machine learning. A has a budget of T many evaluations at its disposal, limiting how much of ν it can observe. Thus it selects a potentially random retrieval sequence (S1, . . . , ST ) of coalitions to be evaluated and used to compute ˆ ϕi. The budget captures that access to ν typically poses the bottleneck in runtime, often requiring costly model inference or retraining in machine learning.

The quality of an estimate ˆ ϕi is quantified by an error measure to be minimized, most commonly the mean squared error (MSE). But since it is usually of stochastic nature due to random sampling performed by A, one usually judges A by its expected MSE:

Alternatives to the expected MSE exist by taking the absolute error and orthogonally to that choice divide it by the absolute Shapley value to obtain a proportional error [van Campen et al., 2018]. Regarding the handling of A's randomness, one can instead of taking the expected error, consider for each player i the error probability by which A outputs an estimate that deviates by more than some ε ≥ 0, usually expressed by an upper bound 1 - δ with δ ∈ [0, 1] to be maximized:

3.2 Properties

Besides the quality of the returned estimates, one can describe further characteristics and distinguish algorithms by other criteria, which are relevant before or during execution.

• Parameter specification: Some algorithms require the specification of additional parameters that impact the random generation of the retrieval sequence or the computation of ˆ ϕ. Often, the ideal parameterization depends on the considered game.
• Space complexity: Despite returning only nmany point estimates ˆ ϕi, some algorithms do not exhibit a space complexity of O(n), but rather Ω(n2 ). In general, at most a polynomial growth w.r.t. n is required for practicality. Some approaches even show a dependence of T .
• Adaptivity: The steps executed by A can be determined at initialization or during the approximation procedure by adapting to observations made by palpating ν. We term the former type of algorithms static and the latter adaptive. Typically, adaptive algorithms alter their sampling distribution, while their static counterparts have a priori fixed retrieval sequences.
• Consistency: For each i ∈ N, the budget-dependent estimate ˆ ϕTi converges in probability towards ϕi, i.e. lim T→∞ P(| ˆ ϕTi - ϕi| > ε) = 0 for all ε > 0. Loosely speaking, consistency promises smaller estimation error with increasing budget.

• Unbiasedness: For each i ∈ N, the estimates equal their Shapley value in expectation, i.e. E[ˆ ϕi] = ϕi. Particularly for explanations, unbiased estimates are desirable to avoid inherently misleading interpretations. Notably, biased estimates can still be consistent when the bias shrinks with T .
• Error bounds: Theoretical results regarding the estimation error have been shown for a variety of algorithms. Usually these depend on n and T as well as latent constants of the game, such as the variance of the population fromwhich A samples. Their benefit is two-fold: on the one hand they hint at which algorithms are preferable for certain types of games, on the other, understanding how the shape of ν in combination with A′ s sampling procedure impacts estimation error can guide algorithm design to further improvements.

Table 1 lists algorithms and their properties. In the following sections, we present the developments within algorithmic classes, leading to a taxonomy illustrated in Figure 1, which portrays the advance of this research field.

4 Monte CarloMethods

The arguably most widely studied class of approximation algorithms is based on a likely evident observation: the Shapley value can be interpreted as a player's expected marginal contribution, i.e. ϕi = E[∆i(S)] w.r.t. a probability distribution over P(N -i ) given by the weights in (1). Hence, it comes natural to reduce Shapley approximation to mean estimation and apply Monte Carlo methods. This class appeals with many merits: its members are mostly (trivially) consistent, unbiased, and have often error bounds for expected MSE and error probability.

4.1 SamplingMarginal Contributions

The first representative, ApproShapley [Castro et al., 2009], samples marginal contributions for each player which it elicits from permutations of N. Within a permutation π for each player i the marginal contribution ∆i(prei (π)) can be taken to update ˆ ϕi where prei (π) is the coalition of players preceeding i in π. This method is unbiased as it directly approximates a representation of π based on permutations:

with Π being the set of all permutations over N. This procedure is budget efficient since the evaluated worth ν(prei (π) ∪ {i}) can be reused for the next player's marginal contribution. However sampling marginal contributions separately for each player allows for varying sample numbers mi among players. Thus, one can prioritize players with higher sample variance ˆσ2 i . More specifically, selecting the next player greedily, by sample the one who promises maximal estimated MSE reduction ˆσ2 i/mi - ˆσ2 i/mi+1 [Strumbelj and Kononenko, 2014], constitutes the first adaptive algorithm we encounter.

Given that A is unbiased, the expected MSE boils down to 1/n ∑i∈N V[ ˆ ϕi]. Hence, applying variance reduction techniques is a natural path of improvement. The most commonly applied technique is that of stratification. Here, one partitions a population into strata and samples from each strata independently. The obtained strata estimates are then aggregated to an estimate of the whole population. The underlying idea is that the strata estimates should converge quickly if each strata showcases a high degree of homogeneity within its subpopulation, thus leading to a final estimate of lower variance. For each ϕi, stratifying is carried out by forming a stratum for each coalition size s to which i has a marginal contribution, resulting in n strata per player and n2 in total [Maleki et al., 2013]. The Shapley value even admits a representation as an arithmetic mean of strata values ϕi,s, each of which is itself an arithmetic mean of marginal contributions:

A crucial role of this approach is played by the sample allocation over all strata specified by the number of samples mi,s drawn for each ϕi,s. In its simplest form, the sample allocation is uniform as emulated by Structured Sampling [van Campen et al., 2018]. A randomly drawn permutation of N is duplicated multiple times and altered, such that each player appears exactly once at each position, from which then marginal contributions are retrieved as in [Castro et al., 2009]. More advanced methods perform adaptive stratification. Based on the observation that stratification yields an expected MSE 1 of

with stratum variances σ2 i,s , one can derive the optimal allocation that minimizes MSE:

assuming that each sample costs two evaluations, which is known as the Neyman allocation [Neyman, 1934]. Since the stratum variances are unknown, adaptive methods estimate them and adjust their sample allocation accordingly during approximation with the goal of converging to m∗i,s . Pursuing this idea, adaptive methods face an exploration-exploitation dilemma in which exploration expresses gathering information about σ2 i,s through sampling all strata and exploitation consists of chasing the estimated optimal allocation. The two-phase approach implements a simple "first-explore-thenexploit" strategy by first sampling uniformly from all strata and then trying to reach the estimated optimal allocation in the second phase [Castro et al., 2017]. In contrast, employing a sigmoid function to randomly pick between exploration and exploitation, slowly converging to the latter, represents a smoother transition between the two phases [O'Brien et al., 2015]. Both require parameterization, be it the phase lengths or the sigmoid function. The Stratified Empirical Bernstein Method greedily selects the next stratum to sample from by minimizing an upper bound on the error probability [Burgess and Chapman, 2021]. However, it requires the knowledge of the ranges of values within the strata. While these methods are unbiased, analytical results on their achieved error remain unknown. A potentially significant drawback is the number of strata scaling quadratically with n. Besides increased space complexity this poses a vulnerability for adaptive stratification. The accuracy of the estimated optimal sample allocation over the strata suffers if the available budget is not sufficient to estimate startum avriance precisely, and thus the algorithm is mislead during exploitation.

1 For simplicity we neglect that the most outer strata s = 0 and

s = n - 1 contain only one element and thus have zero variance.

Another variance reduction technique is that of antithetic sampling. The sampled marginal contributions for each player are not drawn independent anymore but constructed in such a way that these exhibit (likely) negative covariance [Ill´es and Ker´enyi, 2019; Mitchell et al., 2022].

Interestingly, the Shapley value can not only be expressed as a discrete sum, but also as an integral called multilinear extension [Owen, 1972]:

with distribution P(Si,q = S) = q|S| · (1 - q)n-|S|-1 over P(N -i ). Thus, one can approximate ϕi through numerical integration, for example by estimating E[∆i(Si,q)] for equidistant points q ∈ [0, 1] [Okhrati and Lipani, 2020]. This introduces a trade-off specified by parameterization between the number of points and the number of samples left to obtain precise estimates. Further, the equidistant points introduce a bias. Worth mentioning is the connection to stratification: instead of estimating E[∆i(Si,q)] for random q ∈ [0, 1], the unit interval is partitioned with each q representing a stratum.

Slightly deviating from marginal contributions, one can switch the sampled unit to complementary contributions ∆Ci (S) := ν(S∪{i})-ν(N \(S∪{i})). These can likewise be averaged to obtain

allowing one to analogously transfer previous approaches onto this representation [Zhang et al., 2023].

4.2 Sampling Coalitions

Despite the fundamental role of the marginal contribution, the Shapley value can be represented through other building blocks giving rise to methods that sample these units instead. Single coalitions constitute the most atomic building block allowing improved sampling efficiency. One can rewrite ϕi as

with ωi = 1 n( n-1 |S|-1) for i ∈ S and ωi = - 1 n(n-1 |S| ) otherwise. SHAP-IQ [Fumagalli et al., 2023] samples coalitions from P(N), evaluates them, and updates all ˆ ϕi via importance sampling. Noteworthy is the usage of each evaluated worth ν(S) for all players' estimates because it is part of each player's representation of ϕi. This maximum sample reuse principle [Wang and Jia, 2023] is unattainable for approaches based on marginal contributions since each observed ∆i(S) belongs only to i itself and no other player. Leveraging this advantage, further methods have been proposed, for example the disentanglement of coalition values with differing signs into two sums resulting in:

Instead of estimating each average separately [Kolpaczki et al., 2024a] making error analyses accessible, one can perform importance sampling from one distribution over P(N) and use each evaluated ν(S) to update either ˆ ϕ+i or ˆ ϕ-i for each player i [Covert et al., 2019]. Provably, there exists no single distribution over P(N) that leads to unbiased estimates without importance sampling [Kolpaczki et al., 2024a]. The separation into ϕ+i and ϕ-i can be understood as an attempt to stratify, however, one can pursue this direction even further by additionally considering coalition size:

The aggregation of stratum values to ϕi can be simplified to

The applied stratification does not only serve as a variance reduction technique by providing the benefit of more homogeneous strata. It further allows one to recover the maximum sample reuse principle without the need of importance sampling and thus facilitating error analyses. In Stratified SVARM [Kolpaczki et al., 2024a], this is achieved by observing that each stratum value is an arithmetic mean of coalition values. Hence, each coalition sampled from a distribution over P(N ) is used for every player to update an estimate of the stratum to which it belongs. The stratification can be further extended to adaptivity by the techniques presented in Section 4.1. For example, Adaptive SVARM [Kolpaczki et al., 2024b] implements the two-phase approach [Castro et al., 2017].

5 RegressionMethods

A different class of algorithms obtains estimates by solving an optimization problem, essentially performing regression.

5.1 Linear Regression

The groundlaying result for this stream of works is the discovery that the Shapley value itself is a solution to a constrained weighted least squares (WLS) problem [Charnes et al., 1988]:

At first, this formulation leads back to an exponential sum in the objective function. However, one can circumvent this hurdle by gradually constructing it from observed coalitions.

Kernel weights. KernelSHAP [Lundberg and Lee, 2017] samples and evaluates coalitions with replacement to add each observed pair S and ν(S) to the sum in the objective function. The solution to the smaller WLS problem is then treated as the desired estimate ˆ ϕ. This approach comes at the cost of space complexity depending on T since each evaluated ν(S) must be stored. Moreover, the analysis of error and other properties is challenging [Covert and Lee, 2021]. In contrast, Unbiased KernelSHAP [Covert and Lee, 2021] alters the solution to the WLS problem on an algebraic level and is provably unbiased. Surprisingly, the resulting estimates are equivalent to those of SHAP-IQ [Fumagalli et al., 2023], implying a connection between both major algorithmic classes. Further, the technique of paired sampling is proposed, additionally evaluating the complement SC of each sampled S. Given the convexity of the optimization problem, methods that still sample but conduct stochastic gradient descent have been proposed [Simon and Vincent, 2020].

Leverage scores. Less considered, but still an element of vital importance, is the distribution fromwhich coalitions are sampled to construct the estimated objective function. KernelSHAP heuristically samples with probability proportionally to the weights ( n-2 |S|-1) in (14) known as kernel weight sampling. Instead, Leverage SHAP [Musco and Witter, 2025] performs leverage sampling based on leverage scores originally quantifying the impact of individual matrix rows in regression problems. Considering (14) on an algebraic level where each coalition responds to a row of a matrix allows one to transfer this paradigm. This further unveils a connection to active learning in which leverage scores are used for the selection of the next data point. Likewise, estimation via regression can be seen as an active learning problem in which the coalitions must be chosen. As a result, each coalition of size s is drawn with probability proportional to (ns )-1 derived from a rigorous analysis [Musco and Witter, 2025] that reduces the complexity of computing scores naively in time O(2nn2 ) to constant time. The bound on expected MSE of Leverage SHAP marks a breakthrough result for regression methods although the game-specific constants and asymptotic impact of n and T are relatively hard to interpret.

Modified row-norms. Both methods can be unified under sketched regression [Chen et al., 2025] yielding a representation as unconstrained regression. Within this framework the first bound for KernelSHAP on the sample complexity guarantee an error probability is derived. Further, the geometric mean of kernel weights and leverage scores as a sample distribution named modified row-norms [Chen et al., 2025] shows favorable sample complexity bounds.

5.2 Generalized Regression

The WLS problem can be viewed from another perspective providing an interpretation that exhibits a more encompassing and unifying character. The term ϕ′0 + ∑i∈S ϕ′i can be seen as an estimate ν ′ (S) of ν(S). Hence, the regression fits a surrogate game (N, ν ′ ) with ν ′ (S) = ϕ′0 + ∑i∈S ϕ′i by minimizing the weighted mean squared error of ν ′ w.r.t. ν. Despite its lacking flexibility, evident in ∆i(S) = ϕ′i for all i ∈ N and S ⊆ N -i , this surrogate game yields the exact solution when all coalitions are observed. Consequently, one may ask whether other classes of parameterizable surrogate games likewise yield the Shapley value and if increased flexibility obtained by a higher degree of freedom improves the fit during sampling.

Inspired by the notion of k-additivity, SVAkADD [Pelegrina et al., 2025] provides a positive example by enriching the surrogate game with Shapley interactions [Grabisch and Roubens, 1999] up to degree k:

where γS,S′ is a constant depending only on S and S′ . Each interaction ϕS′ captures the synergy arising from all players in S being present. While its correctness is proven for k ≤ 3 and assumed for all k ≤ n, space complexity and computational effort for solving obviously grow with k.

Another class of k-additive surrogate games are sums of unanimity games, effectively linear combinations of binary value functions, one for each coalition up to size k [Yan et al., 2020].

6 Other Approaches

Interestingly, the two classes of Monte Carlo methods and regression methods are not necessarily in conflict with each other and metaphorically speaking can be combined to cooperate. This would simultaneously harness the unbiasedness of the former and the fast convergence of the latter (empirically in machine learning). The key observation behind this thought is the utility of the linearity axiom. A simple model f ≈ ν or surrogate game in general with Shapley values computable in polynomial time is combined with a Monte Carlo method approximating the Shapley values of the residual ν - f. Due to linearity, the addition of both estimates is expedient, since we have

The universally valid decomposition of the value function into f and ν - f gives room to apply any model and mean estimation coined RegressionMSR [Witter et al., 2025] and comes with theoretical guarantees: unbiasedness and a probabilistic bound on the MSE. Proposed candidates for f are linear models and XGBoost tree models [Witter et al., 2025].

A vastly different approach is that of divisive clustering [Corder and Decker, 2019]. Instead of approximating the Shapley values directly for the considered cooperative game (N, ν), the game is divided into smaller subgames for which the Shapley values are computed exactly, which is made feasible due to their smaller size. Interestingly, this division is not carried out on the level of ν but N. For some parameter β > 1, the players are partitioned by the leaf nodes of a binary tree into mutually disjoint coalitions of size at most logβ(n). Each leaf node constitutes a subgame containing only the leaf node's players and ν projected onto this coalition. The exact Shapley values are computed for each subgame and interpolated bottom-up from the leaves to the root of the tree to ensure the efficiency axiom. For any parent node of two siblings S1 and S2 this is done through scaling the Shapley values of each subgame S ∈ {S1, S2} by ν(S)ν(S1∪S2)/ν(S1)+ν(S2) to maintain the proportion between S1 and S2. Sensitive parameters are the leaf node size and the partitioning mechanism.

7 Open Directions

The previous sections summarize the substantial progress made in the past decade on the topic of approximating the Shapley value. Nevertheless, the field still offers multiple opportunities for improvement and room for novel approaches.

Monte Carlo methods. We suspect that orthogonal variance reduction techniques can be further combined and applied onto different representations of the Shapley value. Moreover and specifically targeting stratification, the quadratic scaling of the space complexity w.r.t. n is a burden to be tackled. Caused by the sheer number of strata, one might introduce a coarser partitioning into less strata, eventually even depending on n and the available budget for adaptive methods. If one is interested in the problem-specific empirical impact, one could study how the game-specific constants that dictate the error of each technique and representation behave in varying domains such as feature explanations, data valuation, and model pruning, among others.

Regressionmethods. The unifying concept of fitting a surrogate game for regression methods lacks a deeper theoretical foundation. One may ask which parameterizable classes of games yield the Shapley value as a solution. Further, it is yet unclear how a better fit caused by a game's increased flexibility transfers into more precise estimates, or whether this is even necessarily the case. Regarding this class and its few theoretical results in general, error bounds with clearer dependencies on the number of players and budget and compact game-specific constants would certainly be of benefit. These would facilitate the comparison with approaches conducting mean estimation and give guidance on the selection of a suitable estimator for specific domains.

Alternative problem settings. A further research direction could be the tailoring of methods to more specific or slightly altered problem settings. Certain domains may come with patterns in the value function that are to be exploited by assumptions that a method is allowed to make. Variations may also be formulated regarding the player set. Eventually, selection tasks do not come with the rigid demand for precise estimates for all players. In this case, imprecision to some greater degree of less important players may be tolerated or some players may even completely drop out of consideration.