| paper | d4-conf-aaai-2021-0050 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→other discrete result → its continuous mirror
Answer: No finite uniform query bound exists. The guarantee is impossible for algorithms deterministic conditional on their samples. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Let \(T\) be a finite set of complete record types with rational masses \(\mu_t\ge 0\) summing to \(1\), and let \(V:[0,\mu]\to[0,1]\) be a coalition-value oracle with \(V(0)=0\). For every integer \(r\) such that each \(r\mu_t\) is integral, form a game with \(r\mu_t\) players of type \(t\), where a coalition \(S\) has value \(V(y(S))\) and \(y_t(S)=|S\cap T_t|/r\). Promise that the scaled per-player payoffs in these games’ nucleoli converge to a rate vector \(p^\star\). Given samples \(Y\sim D\) and oracle values \(V(Y)\), what is the query complexity of outputting an efficient rate vector \(p\), with \(\sum_t\mu_t p_t=V(\mu)\), such that \(\Pr_{Y\sim D}[|p\cdot Y-p^\star\cdot Y|\le\epsilon]\ge 1-\delta\), with success probability at least \(1-\Delta\)?
A high-multiplicity data-valuation market: complete record classes are the types, \(\mu_t\) is each class’s population mass, \(y_t\) is the mass contributing to a coalition, and \(V(y)\) is the value of training on those weighted records. The task is to compute type-level payment rates approximating the replica-limit nucleolus from sampled coalition-mass queries.
The mirror covers Theorem 3’s approximate nucleolus computation and Theorem 2’s approximate least-core computation; it leaves aside the experiments, Shapley comparisons, and axiomatic arguments.
A credible mirror is a high multiplicity data valuation market. A type \(t\) is a complete record class: the same feature and label values, provenance, license, and other properties that affect training or payment. A large supplier population has mass vector \(\mu\) over a modest number \(\tau\) of such types. A coalition is described by the mass \(y_t\in[0,\mu_t]\) it contributes from each type. Let \(V(y)\) be the validation value of a deterministic model trained on those weighted records, with \(V(0)=0\). This fits the paper’s logistic regression examples: duplicate records can be represented as sample weights, and the number of records can greatly exceed the number of distinct types.
The decision is a payment rate \(p_t\) per unit mass of type \(t\), with efficiency condition \(\sum_t\mu_t p_t=V(\mu)\). Coalition \(y\) receives \(\sum_t y_t p_t\). The paper itself motivates the core as a way to make every coalition’s payoff reflect its contribution, so this preserves the underlying credit assignment question while making the population the continuous object.
My lead anchor is Theorem 3, proved in this paper. It states that for \(n\ge9\), \(\epsilon<1/50\), \(\delta<1/200\), and \(\Delta<4/5\), any deterministic algorithm that works for all \(n\)-player games and all coalition distributions \(D\), and returns an allocation in the \((\epsilon,\delta)\)-probably approximate nucleolus with probability at least \(1-\Delta\), must access the values of \(\Omega(2^{n/3})\) coalitions sampled from \(D\). Here an allocation qualifies when, for a \(D\)-random coalition, its deficit is within \(\epsilon\) of that coalition’s deficit under the unique nucleolus, except with probability at most \(\delta\).
The corresponding continuous question is Replica-Limit Nucleolus Approximation. Its instance is \((T,\mu,V,D)\), with \(V\) defined on the whole box \(\prod_t[0,\mu_t]\). For each integer \(r\) with \(r\mu_t\) integral, form the finite replica game with \(r\mu_t\) players of type \(t\), and give a coalition \(S\) value \(V(y(S))\), where \(y_t(S)=|S\cap T_t|/r\). Promise that the scaled type payoffs in these replica games’ nucleoli converge: if each type-\(t\) player gets \(x_t^{(r)}\), then \(p_t^\star=\lim_r r x_t^{(r)}\) exists. Define \(d^\star(y)=V(y)-\sum_t p_t^\star y_t\). Given sampled queries \(Y\sim D\) to \(V\), the task is to output an efficient rate vector \(p\) such that
\[ \Pr_{Y\sim D}\!\left[\left|\sum_t p_tY_t+d^\star(Y)-V(Y)\right|\le\epsilon\right]\ge1-\delta \]
with success probability at least \(1-\Delta\). The research question is the oracle sample complexity of this task as a function of \(\tau\), input bit length, and \(\epsilon,\delta,\Delta\). I expect worst-case query hardness without regularity assumptions: the limit nucleolus may be sensitive to coalition masses that the sampling distribution almost never produces. That would be continuum-specific hardness, not a transfer of Theorem 3’s bound.
Theorem 2, also proved here—the proof builds on Balkanski et al.—is the strongest evidence that this population model is a worthwhile computational object. It says that, for a game and a coalition distribution \(D\), solving the least-core LP on \(O\!\left(\rho^2(\log n+\log(1/\Delta))/(\epsilon^2\delta^2)\right)\) sampled coalitions returns an allocation in the \((\epsilon,\delta)\)-probably approximate least core with probability at least \(1-\Delta\). Here \(\rho=\max_{S}v(S)/\min_{S\ne\emptyset}v(S)\). This result is established in the paper, though its proof builds on prior work.
Its mirror, Mass-Probable Least-Core Allocation, uses the same \((T,\mu,V,D)\) instance. Let
\[ e^\star=\inf_{\sum_t\mu_t p_t=V(\mu)} \ \sup_{0\le y\le\mu}\left(V(y)-\sum_t p_ty_t\right). \]
Output an efficient \(p\) satisfying
\[ \Pr_{Y\sim D}\!\left[\sum_t p_tY_t+e^\star+\epsilon\ge V(Y)\right]\ge1-\delta. \]
The continuous question is whether sampled coalition-mass queries and a finite LP yield such a vector with query complexity polynomial in the type support, bit length, \(1/\epsilon\), \(1/\delta\), and \(\log(1/\Delta)\). A paper-shaped conjecture is a bound \(O(\rho^2(\log\tau+\log(1/\Delta))/(\epsilon^2\delta^2))\) samples when the continuous value range has finite ratio \(\rho\). I expect this to be tractable: the allocation has only \(\tau\) variables, and the sampled LP is the same basic method as in the paper. Finite \(\rho\) is a substantive assumption in a continuum, since values of nonempty coalitions can approach zero.
The scope is narrow: these questions mirror the paper’s computational results about approximate least-core and nucleolus credit allocation. They do not continuize the feature or data outcomes; the payments remain monetary and the population of contributors is what becomes continuous.
The weakest point is the nucleolus anchor. There is no canonical lexicographic ordering of deficits across uncountably many coalitions, so the replica-limit promise is a deliberate definition of the continuous target. Also, Theorem 3’s hard instances range over arbitrary player games; its lower bound need not survive the symmetry imposed by grouping players into a few types. That makes Theorem 3 an excellent hardness question, but not a claimed hardness transfer. Theorem 2’s least-core mirror is the more secure case that the authors could recognize as their problem.
The nucleolus is the weaker anchor. Theorem 3 ranges over arbitrary games on \(n\) individually named players. Its lower bound need not survive when players are interchangeable within \(\tau\) types: a symmetric replica game has only \(\tau\) payoff rates, so the reduction behind the theorem may have no counterpart. The proposed replica-limit target also needs care. A limit of finite nucleoli is not guaranteed to exist, and lexicographically ordering deficits over an uncountable set of coalitions is not automatic. One could define a continuous version in other ways, but then its relationship to Theorem 3 is a new question, not a hardness transfer. This substantially weakens that anchor.
There is also a real modeling cost in the data-valuation scenario. Most records are distinct in ways that affect training, so complete types may number almost as many as data points; grouping them more coarsely can change coalition values. Treating a fraction of a record type as a weighted training example supplies a natural extension for some models, but it is an extra assumption. Still, a large population drawn from a modest set of feature-label categories is plausible, and the paper already uses data points as players. That makes the scenario defensible, even if it does not represent every valuation task.
Theorem 2 is harder to dislodge. For a finite type set, let \(V(y)\) be the value of contributing mass vector \(y\), and let \(p\) be type-level payment rates satisfying efficiency. The continuous least-core subsidy is the supremum of \(V(y)-p\cdot y\) over feasible \(y\). The sampled constraints then form a finite LP in \(\tau\) rates and a subsidy. Since violations are described by thresholding \(V(y)-p\cdot y\), a finite-dimensional uniform-convergence argument appears capable of giving a probabilistic guarantee with sample complexity polynomial in \(\tau\) and the accuracy parameters. The continuous problem needs an oracle for weighted-mass coalition values, but that is plausible for the paper’s learning setup.
That extension may turn out to be straightforward, and the nucleolus mirror may be too dependent on a chosen limit definition. Those are the strongest objections I can support. But the programme treats a well-posed question with an easy answer as worth asking, and a population of repeated data types gives the least-core question a recognizable interpretation. So I cannot honestly defeat Theorem 2’s anchor or sustain the universal claim that no worthwhile continuous mirror exists.
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.