| paper | d4-conf-atal-2014-0275 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: Deciding existence is \(\mathrm{NP}\)-hard already for \(q=3\), with equal dyadic masses and quadratic \(V\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite set of contributor types \(T\), rational masses \(\mu_t\), a differentiable aggregate value function \(V(x)\) on \(0\leq x_t\leq\mu_t\), cross-type curvature bounds \(\kappa_{tu}\), a maximum issue size \(q\), and tolerance \(\varepsilon\), determine whether \(T\) has a partition \(\mathcal C\) into issues of size at most \(q\) with \(F(\mathcal C)=\sum_{t<u:\,C(t)\ne C(u)}\mu_t\mu_u\kappa_{tu}\leq\varepsilon\). Return such a partition and the issue-based type allocations \(\widehat a_t=\mu_t\int_0^1\partial_tV(s\mu^{C(t)})\,ds\), with the stated aggregate allocation-error certificate.
A nonatomic Shapley allocation for a crowdsourcing population whose contributors fall into finitely many complete types. Type \(t\) has mass \(\mu_t\), and \(V(x)\) evaluates the learning task using subpopulation masses \(x\). The per-contributor allocation is \(\phi_t=\int_0^1\partial_tV(s\mu)\,ds\), and total type allocation is \(a_t=\mu_t\phi_t\). Partition types into bounded-size issues to limit cross-issue curvature and certify the approximation error.
The paper’s named guarantee uses discrete pairwise similarities and strong sub-additivity, while the proposed certificate uses Hessian bounds for a smooth aggregate value function; the paper’s label game is discontinuous and its AUC game lacks the stated sub-additivity condition.
fatal: False
The mirror covers the two-group Shapley approximation in Theorem 4 for smooth aggregate-value instances. It does not cover the paper’s exact decomposition, recursive partitioning result, or its label, regression, and AUC examples without further assumptions.
The best positive case is the paper’s multi-issue Shapley approximation, not a claim that the authors’ experiments already involve a continuum. The natural regime is a large crowdsourcing platform with many contributors but relatively few complete contribution profiles: the same label-and-feature bundle, reliability, and payment terms. A type is that whole profile, and \(\mu_t\) is its share of the workforce. A realistic instance might have millions of contributors and tens or hundreds of recurring profiles. The platform still asks the paper’s question: how should it divide the value of the trained classifier among contributors?
My anchor is Theorem 4, proved in this paper. For a strongly sub-additive game, take a partition of the agents into \(C_1,C_2\), and let \(\zeta\) be the total pairwise-similarity weight crossing the cut, where pairwise similarity is \(M_2(\{i\},\{j\})\). The theorem says that replacing the original game by the two restricted games \(v_k(S)=v(S\cap C_k)\) approximates each agent’s Shapley value with error at most \(2\zeta\). Its stated running time is \(O(2^{\max(|C_1|,|C_2|)}+n^3)\): exact Shapley computation within the groups, plus the graph partitioning step. This is a named algorithmic result, though the paper does not give a named P-versus-NP-hardness classification.
Here is a continuous problem that keeps that question intact. Call it Continuous Multi-Issue Shapley Approximation. An instance has a finite set of complete contributor types \(T\), rational masses \(\mu_t>0\) summing to \(1\), and a differentiable value function \(V(x)\) for every subpopulation \(x\), where \(0\leq x_t\leq\mu_t\). \(V(x)\) is the value of training and evaluating the model using mass \(x_t\) of each type. Assume \(V\) is twice differentiable, and the input supplies a value-and-gradient oracle and bounds \(\kappa_{tu}\geq\sup_x|\partial_{tu}V(x)|\).
Define the per-contributor Shapley density of type \(t\) by
\[
\phi_t=\int_0^1 \partial_t V(s\mu)\,ds,
\]
and its total type allocation by \(a_t=\mu_t\phi_t\). This is the high-multiplicity limit of the finite Shapley question: if each member of a population of size \(N\) contributes mass \(1/N\), then \(N\) times a type-\(t\) member’s Shapley share tends to \(\phi_t\), under the smoothness assumptions.
The problem’s input also includes a maximum issue size \(q\) and an error target \(\varepsilon\). It asks whether the support types can be partitioned into issues of at most \(q\) types so that the cross-issue interaction bound
\[
F(\mathcal C)=\sum_{\substack{t<u\\ C(t)\ne C(u)}}\mu_t\mu_u\kappa_{tu}
\]
is at most \(\varepsilon\). A yes-solution returns the partition and the issue-based allocation
\[
\widehat a_t=\mu_t\int_0^1\partial_t V(s\mu^{C(t)})\,ds,
\]
where \(\mu^{C(t)}\) keeps only the masses in \(t\)’s issue. The Hessian bounds certify \(\sum_t|a_t-\widehat a_t|\leq F(\mathcal C)\); numerical integration can add a separately specified tolerance. Thus the decision variable, objective, answer, and accuracy certificate are all explicit.
This is an analogue of Theorem 4, not a theorem that follows from it unchanged. In a finite population, pairwise interactions between two members of types \(t,u\) scale with their individual masses; summing across the two cohorts produces a type-pair weight proportional to \(\mu_t\mu_u\). That gives a principled continuous pairwise-interaction graph on the support types. The new question is whether its low-cut issue structure can be found and used to allocate value. To keep that in the paper’s domain, \(V\) should describe value from aggregate crowd contributions—such as a regularized learning objective evaluated on a common task corpus—not an unrelated continuum of outcomes or axioms.
I expect the full low-cut feasibility problem to be Class B: the cut-partition combinatorics live in the interaction graph over types, and making each type a large cohort does not remove them. For a supplied partition, bounded issue size, and an efficiently evaluable gradient, computing the issue allocations and their certificate is the tractable side of the story. The paper itself proves neither complexity claim; they are predictions for the mirror. Further questions include whether the paper’s pairwise similarities at the empty coalition can replace global curvature bounds, how the best partition can be approximated, and what survives for nonsmooth values such as set-union value or AUC.
The weakest point is that smoothness narrows the mirror. With duplicated label bundles, value can jump as soon as any positive mass supplies the label, so the derivative-based limit may not exist. The paper allows general characteristic functions, while this continuous question covers only its smooth high-multiplicity instances. The authors’ crowdsourcing motivation makes that restriction plausible, but their experiments involve small populations, so it does not establish that this regime is typical.
The continuum Shapley idea itself is not novel: Aumann and Shapley developed values for non-atomic games decades ago. That is background rather than a collision under this programme’s scope; the proposed contribution is the computational question about type-level interactions, issue partitions, and certified approximation. [Aumann and Shapley, *Values of Non-Atomic Games*](https://www.degruyterbrill.com/_language/de?uri=%2Fde%2Fdocument%2Fdoi%2F10.1515%2F9781400867080%2Fhtml).
Theorem 4 is the proponent’s strongest anchor: it gives a named approximation guarantee and running time. The problem is the bridge from that theorem to their continuous question. The theorem starts with a set function \(v:2^N\to\mathbb R\), partitions individual agents, and bounds each agent’s Shapley error using edges of weight \(M_2(\{i\},\{j\})\). The proposed mirror instead starts with a differentiable function on fractional populations and certifies an aggregate allocation using Hessian bounds. That may be a useful problem, but its certificate does not follow from Theorem 4’s result or its pairwise-similarity graph.
The gap shows up in the paper’s own models. In the labels game, \(v(S)=|\bigcup_{i\in S}B_i|\). If many agents have the same complete type \(B_t\), adding any positive mass of that type supplies the same labels; value depends on whether the type is present, not on its mass. The natural mass function jumps at \(x_t=0\), so the proposed derivative-based allocation is not defined. In the regression game, exact duplicate feature types make the Gram matrix singular, contrary to the paper’s invertibility assumption. If features are instead unique, the type support grows with the population. The classifier game might be redesigned around weighted data and a smooth loss, but that replaces the paper’s coalition value and introduces curvature assumptions the paper neither proves nor uses. The authors also say their AUC game is not strongly sub-additive, the condition behind the theorem’s error guarantee.
There is a more faithful repair: take many exact replicas of each type and study the limit of their finite Shapley values. For a game that depends only on which types have appeared, type masses govern the race for each type’s first arrival. This gives a meaningful mass-dependent allocation without assuming a smooth extension. But it does not recover the proponent’s path integral or its Hessian certificate; a support-type approximation theorem would have to be developed separately. That repair is the main weakness in the negative case: it is plausible that such a theorem could be worth studying.
So the proponent has not shown that their smooth, curvature-bounded problem is Theorem 4’s continuous mirror. I would reject this anchor as stated. I cannot honestly turn that into the universal claim that no worthwhile mirror exists in any scenario: a replica-limit, type-level Shapley problem remains a plausible candidate, even though this paper provides no result for it.
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.