| paper | Approximating the Shapley Value without Marginal Contributions |
| authors | — |
| venue | AAAI 2024 |
| filed under | coalition · wvg |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 6
statement extracted from the paper’s text layer
Given a rational type-mass vector \(\mu\), a value oracle for a bounded \(C^2\) function \(v\) on fractional coalition masses \(x\) with \(0 \le x \le \mu\) and known derivative bounds, a query budget \(T\), tolerance \(\epsilon\), and optionally failure probability \(\delta\), estimate \(A_t = \mu_t \int_0^1 \partial_t v(\lambda \mu) d\lambda\) for all types \(t\), minimizing query complexity subject to \(\max_t E[(\hat{A}_t - A_t)^2] \le \epsilon^2\) or the corresponding \(1-\delta\) confidence guarantee.
A nonatomic cooperative game with finitely many exchangeable data or client types: μ is type mass, x is selected coalition mass, v(x) is coalition worth, oracle queries are decision variables, and the objective is type-level Shapley-style attribution under a value-evaluation budget.
The proponent’s formal oracle formulation omits the explicit smoothness or derivative-control promise needed to identify the derivative-based Aumann–Shapley target from finitely many bounded value queries.
fatal: False
Covers the approximation guarantees of Theorem 6, Corollary 2, and Theorem 4 at the type and mass level; it leaves exact computation, arbitrary nonsmooth black-box games, empirical comparisons, and non-high-multiplicity applications untouched.
There is a defensible continuous mirror, although I would not claim that it covers every use case in the paper. My strongest case is a high-multiplicity data-valuation setting, where the players are records or client contributions and many players are genuinely interchangeable.
The paper has no numbered theorem saying that a problem is in P, NP-hard, or parameterized-hard. Its exact-computation NP-hardness claim is an unnumbered statement attributed to Deng and Papadimitriou (1994), so I would not use it as an anchor under the stated rules. The useful numbered anchors are the approximation guarantees proved in this paper. My lead anchor is Theorem 6, together with its immediate consequence Corollary 2; a supporting anchor is Theorem 4. Both are proved here.
The regime is a large data marketplace or federated-learning population. The agents are data records, client contributions, or training examples. A type contains everything relevant to the value function: the complete feature-label pattern, source, price, privacy class, compute requirements, and so on. Type \(t\) has mass \(\mu_t\), the fraction of the population with that complete description. A coalition is no longer an arbitrary named subset but a mass vector \(x\), where \(x_t\) is the amount of type \(t\) used. Its worth \(v(x)\) could be the test accuracy, utility, or revenue obtained by training on that weighted dataset.
This is plausible in a recurring-cohort regime: millions of records generated from a fixed collection of exact data strata, or many federated clients sharing one of finitely many protocol and data profiles. The relevant comparison is \(N\gg\tau\): a very large number of records but a moderate number of distinct game-relevant types. If records are individually idiosyncratic, this mirror should be rejected; I am explicitly selecting the high-multiplicity regime rather than claiming that all data-valuation instances have it.
The right continuous Shapley target is not the Shapley value of a game with merely \(\tau\) weighted players. That would erase the population. Instead, replicate the population. For an integer \(q\) with \(q\mu_t\) integral, create \(q\mu_t\) individual players of type \(t\), and define the worth of a coalition \(S\) by
\[ \nu_q(S)=v\left(\left(\frac{|S\cap N_t|}{q}\right)_{t=1}^{\tau}\right). \]
Let \(\phi_{t,q}\) be the Shapley value of one individual of type \(t\). Under the usual smoothness condition on \(v\), the high-multiplicity limit is
\[ a_t=\lim_{q\to\infty}q\phi_{t,q} =\int_0^1 \partial_t v(\lambda\mu)\,d\lambda. \]
The aggregate value assigned to type \(t\) is \(A_t=\mu_t a_t\). Thus the output remains a Shapley-style contribution allocation, but it is reported at type and mass level. This is the standard nonatomic, or Aumann–Shapley, limit of the replicated discrete problem, not an unrelated differentiable objective.
For Theorem 6, my lead continuous problem is:
Stratified High-Multiplicity Shapley Estimation. An instance consists of a rational type-mass vector \(\mu\), a finite type set of size \(\tau\), a value oracle for a bounded function \(v\) on fractional coalitions \(x\), a query budget \(T\), and an accuracy parameter \(\varepsilon\). Each oracle call returns \(v(x)\) for one fractional coalition. The task is to output estimates \(\widehat A_1,\ldots,\widehat A_\tau\) such that
\[ \max_t \mathbb E[(\widehat A_t-A_t)^2]\le \varepsilon^2 \]
using at most \(T\) value evaluations.
The connection to the paper is exact in objective and information model: the scarce resource is access to the coalition-worth function, and the output is an approximation to all Shapley allocations. The paper’s Theorem 6 proves, for Stratified SVARM, a variance bound based on stratifying coalitions by cardinality; Corollary 2 gives the corresponding MSE bound. In the mirror, cardinality becomes coalition mass \(\lambda\in[0,1]\), and the finite collection of size strata becomes a continuum of mass strata. Sampling or quadrature over \(\lambda\), together with aggregation by type, is the natural continuous counterpart.
I expect this approximation problem to be Class A under a bounded, smoothly evaluable \(v\). Its complexity should depend polynomially on \(\tau\), the value precision, \(1/\varepsilon\), and the smoothness parameters, but not on the replication factor \(q\) or the number of named records. That is exactly the kind of population-multiplicity gain the programme is looking for. A finite-resolution version, with \(q\) supplied in binary and target \(q\phi_{t,q}\), avoids any limiting ambiguity and is already a meaningful high-multiplicity relaxation.
For Theorem 4, the supporting problem is:
High-Confidence Continuous Shapley Attribution. The input is the same, together with a designated type \(t\), error tolerance \(\varepsilon\), and failure probability \(\delta\). Using at most \(T\) value-oracle calls, output \(\widehat A_t\) satisfying
\[ \Pr\bigl(|\widehat A_t-A_t|>\varepsilon\bigr)\le\delta. \]
This mirrors Theorem 4’s exponential deviation guarantee for a fixed player. I again expect Class A for bounded smooth value functions: sampling mass strata and using concentration should give a query bound polynomial in \(1/\varepsilon\), \(\log(1/\delta)\), and \(\tau\). The all-type version follows as a separate question by requiring the maximum error over \(t\) and paying a logarithmic union-bound factor.
The authors should recognise these as their problem. The players are still agents in a cooperative game; a coalition still has a worth queried through \(\nu\) or \(v\); the goal is still to estimate Shapley contributions under a limited evaluation budget; and the motivation for avoiding marginal-contribution queries is unchanged. Only the representation of the population changes from named individuals to masses of exchangeable types. This also covers the paper’s data-valuation and federated-learning motivation more naturally than its small \(n=14\) feature-attribution experiments.
The mirror does not cover the paper’s exact-computation claim, empirical comparisons, or every arbitrary black-box cooperative game. Exact continuous Aumann–Shapley computation may remain hard: singleton types can preserve the discrete problem, so hardness can transfer, while exact integration of a succinct nonlinear \(v\) could be continuum-specifically hard. Those are useful boundary questions rather than reasons to reject the approximation mirror.
My weakest point is serious. In the limit, an individual Shapley value is \(O(1/q)\), while the paper’s marginal-free representation subtracts two coalition values of order one. Without smoothness, finite resolution, or some stronger oracle, the derivative-like limit is not identifiable from finitely many value queries. Moreover, the paper’s warm-up costs depend on the number of individual players, so Stratified SVARM does not automatically become a \(\tau\)-type algorithm merely by replacing \(n\) with \(\tau\). The positive claim is therefore not “the theorem transfers unchanged.” It is that the paper’s approximation problem has a genuine high-multiplicity formulation, and that a new type-aggregated, mass-stratified algorithm should plausibly place its approximate version in Class A.
The strongest negative case is against treating Theorems 6, Corollary 2, and Theorem 4 as if their guarantees transferred to a continuous society. It does not defeat the proponent’s best reformulation completely.
The proponent is right that “individual prices” are not an objection: a recurring population of genuinely exchangeable data or federated-learning types is a legitimate high-multiplicity regime. Replicating each type \(q\) times and taking \(q\phi_{t,q}\) to an Aumann–Shapley limit is also mathematically natural. So the paper cannot honestly be rejected on the grounds that no sensible population scenario exists.
But that limit is not what Theorem 6 proves. The theorem estimates the Shapley value of each finite player using samples stratified by the integer coalition size \(\ell\). Its nontrivial guarantee is for \(\phi_i\), which is \(O(1/q)\) for a replicated type. At fixed error tolerance, the zero estimator eventually satisfies the paper’s guarantee. To obtain a meaningful limit, one must rescale by \(q\) and aggregate over the type. That produces the new quantity
\[ A_t=\mu_t\int_0^1\partial_t v(\lambda\mu)\,d\lambda, \]
not the quantity controlled by Corollary 2. Multiplying the paper’s variance bound by \(q^2\) destroys it, while the stated warm-up cost grows with \(q\tau\). Replacing \(\ell\) by a mass parameter \(\lambda\) therefore is not a continuous version of the theorem; it requires a new estimator and a new analysis.
The deeper obstruction is the oracle model. The paper is domain-independent: \(\nu\) is an arbitrary black-box set function, with boundedness or range assumptions used for concentration. The Aumann–Shapley target depends on derivatives of \(v\) along a ray through the fractional coalition space. Value queries alone do not identify those derivatives. Even with two types, after any finite adaptive set of queries one can construct two bounded, smooth functions agreeing at every queried point but differing in their transverse derivatives along the ray, and hence having different \(A_t\). Smoothness in the informal sense does not fix this: arbitrarily narrow \(C^\infty\) bumps remain possible. A finite-resolution version has the same issue unless one imposes derivative bounds or other structure on \(v\).
Consequently, the proposed continuous problem becomes solvable only after adding a substantial promise absent from the paper: a known smoothness class, a parametric or low-dimensional model, or derivative access. Under such promises, numerical integration or finite-difference methods may indeed yield useful algorithms. But their tractability would come from the new regularity assumptions, not from Theorem 6’s sample-reuse mechanism or from continuization alone. Defining a fixed-bandwidth smoothed value would avoid the derivative problem, but then it would no longer be the high-multiplicity Shapley limit; it would be a different cooperative value.
The same defeats Theorem 4. Its exponential tail bound concerns empirical averages of bounded discrete coalition values. For the rescaled continuous target, bounded \(v\) does not bound the relevant derivatives, so there is no analogue of the theorem’s range-based concentration guarantee in the paper’s black-box model. With regularity assumptions, a confidence bound is plausible, but again it is a new stochastic numerical-integration problem rather than a continuous mirror of the stated theorem.
Thus I would reject the proponent’s anchors as direct continuizations of the paper’s results. The paper itself supplies no population-level computational theorem whose complexity survives the limit; it supplies finite-player sampling guarantees whose meaningful scale collapses. However, I would not endorse the universal claim that no worthwhile mirror exists in any scenario. The typed Aumann–Shapley formulation is a defensible new research problem. The honest negative conclusion is narrower: this paper does not provide a faithful, domain-independent ChoCo mirror unless one adds exactly the structural assumptions that create the result.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.