| paper | d4-conf-aaai-2026-2124 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.2
statement extracted from the paper’s text layer
Given a finite type set \([\tau]\), rational population masses \(\mu\), and a coalition-value oracle \(V(x)\) for \(x\in[0,\mu]\), define \(F(z)=V(\mu\odot z)\) and the total Shapley allocation to type \(t\) by \(\Phi_t=\int_0^1 \partial_t F(s\mathbf{1})\,ds\). Assuming a stated smoothness bound, determine the worst-case number of coalition-value queries needed to estimate every \(\Phi_t\) within additive error \(\varepsilon\), and whether the paper's sampled \(k\)-additive least-squares approach can attain that bound.
A cooperative game with interchangeable agents grouped into \(\tau\) types, represented by a mass vector \(\mu\) and a value oracle on coalition masses. Sample mass vectors, fit a type-symmetric \(k\)-additive surrogate subject to endpoint efficiency, and estimate each type's total allocation by integrating its marginal contribution along the proportional-growth path.
The query model adds smoothness and a mass-space sampling measure, and generic quadrature may solve the allocation problem without validating SVA's fixed-\(k\) fit.
fatal: False
The mirror covers exact Shapley recovery and its sampled approximation over type masses. It leaves the feature-specific datasets, empirical comparisons, and their measured errors aside.
The strongest positive case is a narrow mirror of the paper’s Shapley computation in a high-multiplicity cooperative game. A plausible regime is a large shipping network with many small firms: firms with the same route, shipment size, costs, and contract terms form a type. If there are \(n\) firms but only \(\tau\) such types, with \(n\gg\tau\), a coalition is naturally described by the mass of each type it contains. Its cost savings or joint payoff can then be modeled as a function \(V\) of those masses. This is a population continuum, not just a fractional outcome: the masses describe how much of each kind of participant joins the coalition.
The paper’s strongest anchor is Theorem 4.2, proved here. It states that for any finite cooperative game \((N,\nu)\), when \(k\in\{1,2,3\}\), the solution of the constrained \(k\)-additive weighted least-squares problem with weights \(w_A^*=\binom{n-2}{|A|-1}^{-1}\) has singleton interaction values \(I_i^k=\phi_i\), the game’s exact Shapley values. This holds even if the original game is not \(k\)-additive, provided all coalition values are used. It is an exact-recovery result, not a polynomial-time result. The paper cites NP-hardness of exact Shapley computation from Deng (1994), but gives no numbered hardness theorem of its own, so that citation is not a second anchor.
My lead mirror is Type-Continuum Shapley Approximation. An instance has a finite type set \([\tau]\), rational type masses \(\mu\) summing to one, a value oracle \(V\) on coalition-mass vectors \(x\in[0,\mu]\), a smoothness bound, and an accuracy target \(\varepsilon\). Define \(F(z)=V(\mu\odot z)\) for \(z\in[0,1]^\tau\). The target total Shapley allocation to type \(t\) is
\[
\Phi_t=\int_0^1 \partial_t F(s\mathbf{1})\,ds.
\]
The vector is efficient: \(\sum_t\Phi_t=F(\mathbf{1})-F(\mathbf{0})\). In the replicated finite game, this is the limiting allocation obtained by averaging marginal contributions over random arrival orders. The task is to use coalition-value queries to return \(\hat\Phi\) with \(\max_t|\hat\Phi_t-\Phi_t|\le\varepsilon\), and characterize the query complexity in \(\tau\), the smoothness bound, and \(1/\varepsilon\). A natural estimator, echoing the paper, fits a type-symmetric degree-\(k\) polynomial to sampled coalition masses, constrains its endpoint difference to equal the observed total value, and returns its line-integral allocation. A solution could give a sampling rule and error guarantee, or a lower bound showing that the proposed estimator cannot achieve one.
I expect the underlying smooth-oracle approximation problem to be tractable: finite differences and quadrature along the path \(s\mathbf{1}\) give a direct route to polynomial query complexity. Whether the paper’s fixed-\(k\) least-squares estimator itself has useful guarantees is a further question; Theorem 4.2 concerns full coalition data, and the paper explicitly gives no approximation guarantee during sampling. The continuous analogue would also need to derive an appropriate mass-space weighting rather than assume the finite weights transfer unchanged.
The weakest point is that most of the paper’s experiments treat features as players, and features usually do not occur in large interchangeable populations. The authors’ cooperative-game framing also explicitly includes company cooperation, which makes the shipping regime a plausible instance of their underlying problem. The mirror covers Shapley allocation and its sampled approximation, not the paper’s particular feature datasets or its empirical comparisons.
The firms example is a genuine high-multiplicity regime: if firms of each type are interchangeable in every respect the game uses, the total Shapley allocation to a type has a sensible large-population limit. So the objection that cooperative-game players must always be individuated does not hold here.
The problem is what that limit mirrors in this paper. Theorem 4.2 is an exact identity for the fitted surrogate when all coalition values are available. It does not guarantee that SVA\(k_{\text{ADD}}\) can recover Shapley values from its sampled coalitions; the paper explicitly leaves that guarantee open. In a smooth type-mass model, the proposed target \(\Phi_t=\int_0^1\partial_tF(s\mathbf 1)\,ds\) follows directly from the limiting marginal-contribution formula. That preserves the Shapley allocation, but it does not carry over the paper’s central sampled-fitting question or establish that its \(k\)-additive estimator works in the limit.
A stronger mirror could ask for the query complexity of estimating those type allocations from coalition-mass evaluations, perhaps by fitting a degree-\(k\) surrogate. But without a regularity condition or a compact representation of the value function, finitely many queries cannot rule out important behavior between sample points. Add smoothness, and the target becomes a vector of integrals along one path, accessible by generic numerical methods. A guarantee for the paper’s particular least-squares estimator might still be interesting, but it would depend on additional choices about the oracle, smoothness, sampling measure, and error criterion; Theorem 4.2 supplies none of them.
That is the strongest negative case I see: the only named anchor proves exact recovery with exhaustive data, while the continuous computational question needs new assumptions and may reduce to generic integration. It does not establish that no worthwhile mirror exists. A carefully specified finite-query analysis of the sampled estimator remains a plausible, though less direct, research question.
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.