d4-conf-aaai-2026-2124 (d4-conf-aaai-2026-2124)

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 society is given by its support: a list of \(\tau\geq2\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; there is no separate \(m\) parameter.
An exact value oracle returns the signed real number \(V(x)\) at any rational \(x\in\prod_t[0,\mu_t]\); derivatives are unavailable. Set \(F(z)=V(\mu\odot z)\), where \(\odot\) denotes componentwise multiplication, and normalize \(V(0)=0\).
Assume \(F\) extends to a twice continuously differentiable function on a neighborhood of \([0,1]^\tau\), with \(\sup_z\max_{i,j}|\partial_i\partial_jF(z)|\leq B\), for a supplied positive rational \(B\). Define the total allocation \(\Phi_t=\int_0^1\partial_tF(s\mathbf1)\,ds\).
For positive rational \(\varepsilon\), let \(N^*(\tau,B,\varepsilon)\) be the least worst-case query budget of an adaptive randomized algorithm satisfying \(\Pr(\max_t|\widehat\Phi_t-\Phi_t|\leq\varepsilon)\geq2/3\) for every admissible oracle. Exact real arithmetic has unit cost; state arithmetic running times and rational query-coordinate lengths in \(\tau,L,B,\varepsilon\) and any surrogate degree \(k\), where \(L\) is the binary input length.
The sampled surrogate procedure uses \(1\leq k\leq\min\{3,\tau\}\) and \(Q(z)=\sum_{|S|\leq k}c_S\prod_{t\in S}z_t\), the multilinear extension of a game with no interactions above order \(k\).
It queries both endpoints and samples distinct nonempty proper subsets \(A\subset[\tau]\), successively with probability proportional to \(w_A=\binom{\tau-2}{|A|-1}^{-1}\) among remaining subsets, querying \(F(\mathbf1_A)\).
It minimizes \(\sum_{A\text{ sampled}}w_A(F(\mathbf1_A)-Q(\mathbf1_A))^2\) subject to \(Q(\mathbf1)-Q(0)=F(\mathbf1)-F(0)\), chooses the minimizer with smallest Euclidean coefficient norm, and returns \(\widehat\Phi_t=\int_0^1\partial_tQ(s\mathbf1)\,ds\).

What is the asymptotically optimal query complexity \(N^*(\tau,B,\varepsilon)\), and can the specified sampled \(k\)-additive least-squares procedure attain it?

Discrete: using every coalition, efficiency-constrained weighted least squares with these weights recovers exact Shapley allocations for \(k\in\{1,2,3\}\); this gives no sampled-query guarantee. [Source](https://arxiv.org/html/2502.04763v2).
Continuous: the allocation is the Aumann–Shapley or integrated-gradients attribution, for which gradient-based numerical evaluation is established. [Source](https://proceedings.mlr.press/v70/sundararajan17a.html). No result settling the specified value-only minimax problem was located.

1. Proven results and unresolved question

The sharp joint asymotics of $N^*(\tau,B,\varepsilon)$ remain unresolved. The following bounds and the obstruction to the sampled surrogate are proved below.

Write
$$ r=\frac{\tau B}{\varepsilon}, \qquad \lambda=\log\!\bigl(2+\tau(1+r)\bigr), $$
where $\log$ denotes the natural logarithm. There are universal constants $c,C>0$ such that
$$ c\max\left\{ \tau,\; r^{2/3},\; \tau r^{2/3} \left(\frac{\log(2\tau)}{\lambda}\right)^{1/3} \right\} \leq N^*(\tau,B,\varepsilon) $$
and
$$ N^*(\tau,B,\varepsilon) \leq C\tau\left( 1+\min\left\{ r,\; r^{2/3}\bigl(\log(2\tau)\bigr)^{1/3} \right\} \right). $$

The joint lower bound follows from the stronger implicit inequality
$$ \bigl(N^*(\tau,B,\varepsilon)\bigr)^3 \log\!\bigl(2+N^*(\tau,B,\varepsilon)\bigr) \geq c\tau^3r^2\log(2\tau). $$
This improves the joint lower bound in the notes by a factor of $\log(2\tau)$ in this implicit inequality.

For every fixed $\tau$, these bounds give the complete conclusion
$$ N^*(\tau,B,\varepsilon) = \Theta_\tau\left(1+(B/\varepsilon)^{2/3}\right). $$

The specified sampled least-squares procedure cannot attain the minimax complexity in general: for every permitted $k$ and every sample budget, it fails with probability one on an admissible oracle whenever
$$ \varepsilon<\frac{B(\tau-1)}{18}. $$
This remains true when every coalition is queried. More generally, complete coalition data leave an unavoidable allocation uncertainty of order $\tau B$.

2. Reduction and value-only upper bounds

2.1. Reduction to the cube

Since every $\mu_t$ is positive and rational, a rational cube query $z$ can be implemented by querying $V$ at
$$ x=\mu\odot z. $$
Conversely, a rational query $x$ to $V$ corresponds to the rational cube point $z_t=x_t/\mu_t$. Thus the masses affect query-coordinate lengths, but not query complexity.

For lower bounds, any admissible cube function gives a society oracle by setting
$$ V(x)=F(x_1/\mu_1,\ldots,x_\tau/\mu_\tau). $$

Define
$$ g_i(s)=\partial_iF(s\mathbf 1), \qquad D=\tau B. $$
The chain rule and the Hessian bound imply
$$ |g_i'(s)| = \left|\sum_{j=1}^{\tau}\partial_i\partial_jF(s\mathbf 1)\right| \leq D. $$
Consequently, each $g_i$ is $D$-Lipschitz. Its magnitude need not be bounded, because arbitrary affine functions are admissible.

The fundamental theorem of calculus also gives
$$ \sum_{i=1}^{\tau}\Phi_i=F(\mathbf 1)-F(0). $$

2.2. Derivative approximation from values

Choose $h$ to be the largest dyadic power satisfying
$$ h\leq \min\left\{\frac12,\frac{\varepsilon}{2B}\right\}. $$
In particular, $h$ is within a factor of two of this threshold.

For $s\in[0,1]$, put
$$ \beta(s)= \begin{cases} 1,&s\leq 1/2,\\ -1,&s>1/2, \end{cases} $$
and define
$$ d_i(s)= \frac{F(s\mathbf 1+\beta(s)he_i)-F(s\mathbf 1)} {\beta(s)h}. $$
Both query points lie in the cube. Applying the fundamental theorem of calculus along coordinate $i$ gives
$$ |d_i(s)-g_i(s)| \leq \frac1h\int_0^h Bu\,du = \frac{Bh}{2} \leq\frac{\varepsilon}{4}. $$
Thus $\tau+1$ value queries suffice to approximate the entire gradient at one diagonal point.

2.3. Deterministic quadrature

Let $n$ be the smallest power of two satisfying
$$ n\geq\max\{1,r\}. $$
Query at the midpoints
$$ s_j=\frac{j+1/2}{n}, \qquad j=0,\ldots,n-1, $$
and return
$$ \widehat\Phi_i=\frac1n\sum_{j=0}^{n-1}d_i(s_j). $$

For a $D$-Lipschitz function, midpoint quadrature has error at most $D/(4n)$. Indeed, on a cell of length $1/n$ with midpoint $s_j$,
$$ \int_{\text{cell}}|g_i(s)-g_i(s_j)|\,ds \leq D\int_{\text{cell}}|s-s_j|\,ds = \frac{D}{4n^2}. $$
Summing over the cells proves
$$ \left|\frac1n\sum_jg_i(s_j)-\Phi_i\right| \leq\frac{D}{4n}\leq\frac{\varepsilon}{4}. $$
Together with the finite-difference error, this yields error at most $\varepsilon/2$ in every coordinate.

The query count is
$$ (\tau+1)n=O\bigl(\tau(1+r)\bigr). $$

2.4. Randomized stratified quadrature

Let
$$ \ell=\left\lceil\log_2(6\tau)\right\rceil. $$
Then $\ell\geq\log(6\tau)$ and $\ell=O(\log(2\tau))$.

Choose $n$ to be the smallest power of two satisfying
$$ n\geq1, \qquad n^3\geq 2r^2\ell. $$
Choose $M$ to be the smallest power of two satisfying
$$ M\geq\max\{1,r/n\}. $$
These near-threshold choices are part of the algorithm.

Independently for each stratum, draw $J_j$ uniformly from $\{0,\ldots,M-1\}$ and set
$$ S_j=\frac{j+(J_j+1/2)/M}{n}. $$
All sampling points are rational. Return
$$ \widehat\Phi_i=\frac1n\sum_{j=0}^{n-1}d_i(S_j). $$

First consider
$$ Z_i=\frac1n\sum_jg_i(S_j). $$
Its expectation is composite midpoint quadrature on $nM$ cells, so
$$ |\mathbb EZ_i-\Phi_i| \leq\frac{D}{4nM} \leq\frac{\varepsilon}{4}. $$

Within one stratum, $g_i$ has range length at most $D/n$. Therefore each independent summand $g_i(S_j)/n$ has range length at most $D/n^2$. Hoeffding’s inequality gives
$$ \Pr\left(|Z_i-\mathbb EZ_i|>\frac{\varepsilon}{2}\right) \leq 2\exp\left(-\frac{n^3\varepsilon^2}{2D^2}\right) \leq\frac1{3\tau}. $$
A union bound over the coordinates shows that, with probability at least $2/3$, every coordinate has total error at most
$$ \frac{\varepsilon}{4} +\frac{\varepsilon}{2} +\frac{\varepsilon}{4} =\varepsilon. $$

The query count is
$$ O\left( \tau\left[1+r^{2/3}\bigl(\log(2\tau)\bigr)^{1/3}\right] \right). $$
Selecting the cheaper of the deterministic and randomized constructions proves the stated upper bound.

2.5. Arithmetic time and coordinate lengths

Let $q=(\tau+1)n$ be the query budget of the selected construction, and set
$$ H_{\mathrm{coord}} = L+\log(2+\tau)+\log(2+B/\varepsilon). $$

The specified dyadic choices imply that every query coordinate, after multiplication by its input mass, has binary length
$$ O(H_{\mathrm{coord}}). $$
To see this, the exponents determining $h,n,M$ are all
$$ O\bigl(\log(2+\tau)+\log(2+B/\varepsilon)\bigr), $$
and multiplying by $\mu_i$ adds at most $O(L)$ bits.

Parameter selection by successive doubling takes $O(H_{\mathrm{coord}})$ arithmetic operations. Including explicit construction of all $\tau$ coordinates of every query, deterministic arithmetic time is
$$ O(\tau q+H_{\mathrm{coord}}). $$
The randomized construction uses exactly $\log_2M$ random bits per stratum. Its arithmetic and random-bit operation count is
$$ O(\tau q+nH_{\mathrm{coord}}+H_{\mathrm{coord}}). $$
These counts use the stipulated unit-cost exact real arithmetic model.

3. A smooth family for lower bounds

Define
$$ P(u)= \begin{cases} u^3(1-u)^3,&0\leq u\leq1,\\ 0,&\text{otherwise}, \end{cases} $$
and
$$ R(v)= \begin{cases} v(1-v^2)^3,&|v|\leq1,\\ 0,&\text{otherwise}. \end{cases} $$
The functions and their derivatives through order two vanish at their support boundaries. Hence both are globally twice continuously differentiable. Also,
$$ R(0)=0,\qquad R'(0)=1, \qquad I:=\int_0^1P(u)\,du =\frac{3!\,3!}{7!} =\frac1{140}. $$

Let
$$ K= \|P''\|_\infty\|R\|_\infty + 2\|P'\|_\infty\|R'\|_\infty + \|P\|_\infty\|R''\|_\infty. $$
This is a fixed positive finite constant.

For an integer $n\geq1$, choose vectors $a_j\in[-1,1]^\tau$, for $j=0,\ldots,n-1$, satisfying
$$ \sum_{i=1}^{\tau}a_{ji}=0. $$
Put
$$ s(z)=\frac1\tau\sum_i z_i, \qquad q_j(z)=\frac1\tau\sum_i a_{ji}z_i, $$
and define
$$ F_a(z)= \frac{B\tau^2}{Kn^2} \sum_{j=0}^{n-1} P(ns(z)-j)R(nq_j(z)). $$

At any point, at most one summand has a nonzero derivative of order at most two. At boundaries between the supports, all such derivatives vanish. For the contributing summand, the product rule gives
$$ \partial_i\partial_\ell F_a = \frac BK \left[ P''R + (a_{ji}+a_{j\ell})P'R' + a_{ji}a_{j\ell}PR'' \right], $$
where the arguments are $ns(z)-j$ and $nq_j(z)$. The coefficient bounds and the definition of $K$ imply
$$ |\partial_i\partial_\ell F_a|\leq B $$
globally. Also $F_a(0)=0$. Thus this is an admissible family.

On the diagonal, the zero-sum condition gives $q_j(s\mathbf1)=0$. Differentiating before restricting to the diagonal yields
$$ \partial_iF_a(s\mathbf1) = \frac{B\tau}{Kn}\sum_j a_{ji}P(ns-j). $$
Integration therefore gives
$$ \Phi_i=\delta_n\sum_j a_{ji}, \qquad \delta_n=\frac{BI\tau}{Kn^2}. $$

Crucially, every value query involves at most one block $a_j$, including queries away from the diagonal.

4. Affine and scalar lower bounds

4.1. At least $\tau$ queries are necessary

Restrict to affine functions
$$ F_a(z)=a\cdot z, \qquad a\in\mathbb R^\tau. $$
They are admissible, and their allocations equal $a$.

Suppose an algorithm uses $N<\tau$ queries. Give $a$ a centered Gaussian distribution with covariance $R_0^2I_\tau$, where
$$ R_0=4\varepsilon\sqrt{\tau}. $$
Condition on the algorithm’s random seed.

Each query is a linear measurement of $a$. Although its direction may depend on previous responses, that direction is fixed after conditioning on the preceding transcript. Sequential Gaussian conditioning shows that the posterior covariance is $R_0^2$ times the orthogonal projection onto the common nullspace of the measured directions: each new measurement removes variance only in its newly measured direction.

This nullspace has positive dimension. Choose a unit vector $v$ in it, measurably from the transcript. Conditional on the transcript, $v\cdot a$ has standard deviation $R_0$. Maximum-norm success implies
$$ |v\cdot(\widehat a-a)| \leq\varepsilon\|v\|_1 \leq\varepsilon\sqrt{\tau}. $$
A Gaussian with standard deviation $R_0$ has density at most $1/(R_0\sqrt{2\pi})$. Hence conditional success probability is at most
$$ \frac{2\varepsilon\sqrt{\tau}}{R_0\sqrt{2\pi}} = \frac14\sqrt{\frac2\pi} <\frac23. $$
Averaging contradicts the required guarantee on every affine input. Thus
$$ N^*(\tau,B,\varepsilon)\geq\tau. $$

4.2. A scalar lower bound with dimension amplification

Let $p=\lfloor\tau/2\rfloor$, and choose $a\in[-1,1]^\tau$ with its first $p$ entries equal to $1$ and all remaining entries equal to
$$ -\frac{p}{\tau-p}. $$
Then $\sum_i a_i=0$ and $a_1=1$.

In the family of Section 3, set
$$ a_j=\sigma_j a, $$
where the $\sigma_j$ are independent uniform signs. Grant the algorithm the entire sign associated with each queried block. This strengthens its information.

After $N$ adaptive queries, at least $m\geq n-N$ signs remain independent and uniform conditional on the transcript. The first allocation is
$$ \Phi_1=\delta_n\sum_j\sigma_j. $$

The largest atom of a sum of $m$ uniform signs is at most $1/\sqrt{m+1}$. For completeness, write
$$ p_r=\frac{\binom{2r}{r}}{2^{2r}}. $$
The recurrence
$$ p_{r+1}=p_r\frac{2r+1}{2r+2} $$
and
$$ (2r+1)(2r+3)\leq(2r+2)^2 $$
prove $p_r\leq1/\sqrt{2r+1}$ by induction. The odd case follows from its central atom
$$ p_r\frac{2r+1}{2r+2}\leq\frac1{\sqrt{2r+2}}. $$

The remaining allocation has lattice spacing $2\delta_n$. An interval of radius $\varepsilon$ contains at most $\varepsilon/\delta_n+1$ possible values. Therefore conditional success probability is at most
$$ \frac{\varepsilon/\delta_n+1}{\sqrt{m+1}}. $$

Choose $n=32(N+1)$. Then $m\geq31N+32$. If
$$ \varepsilon\leq\frac{\delta_n\sqrt{n-N}}4, $$
the preceding probability is at most
$$ \frac14+\frac1{\sqrt{33}}<\frac23. $$
Consequently, a successful algorithm must satisfy
$$ \varepsilon> c\frac{B\tau}{(N+1)^{3/2}} $$
for a universal $c>0$. Combining this with $N\geq\tau\geq2$ yields
$$ N^*(\tau,B,\varepsilon)\geq c r^{2/3}. $$

5. A Gaussian maximum-norm lemma

The strengthened joint lower bound needs simultaneous uncertainty in many coordinates.

Lemma. There is a universal $a_0>0$ with the following property. If a centered Gaussian vector $G\in\mathbb R^d$ has covariance $K_0$ satisfying
$$ 0\preceq K_0\preceq nI_d, \qquad \operatorname{tr}K_0\geq\frac{nd}{2}, $$
then
$$ \Pr\left( \|G\|_\infty\leq a_0\sqrt{n\log(2d)} \right)\leq\frac14. $$
Consequently, for every center $b\in\mathbb R^d$,
$$ \Pr\left( \|G-b\|_\infty \leq \frac{a_0}{\sqrt2}\sqrt{n\log(2d)} \right)\leq\frac12. $$

5.1. Selecting many weakly correlated coordinates

Let
$$ T=\{i:(K_0)_{ii}\geq n/4\}. $$
Since every diagonal entry is at most $n$,
$$ \frac{nd}{2} \leq\operatorname{tr}K_0 \leq n|T|+\frac n4(d-|T|). $$
Thus $|T|\geq d/3$.

Form a graph on $T$, joining $i$ and $j$ when
$$ |(K_0)_{ij}|>n/16. $$
Because the eigenvalues of $K_0$ lie in $[0,n]$,
$$ \sum_{i,j}(K_0)_{ij}^2 = \operatorname{tr}(K_0^2) \leq n\operatorname{tr}K_0 \leq n^2d. $$
Each edge contributes twice to this sum, so the graph has at most $128d$ edges.

A graph with $m$ vertices and $e$ edges has an independent set of size at least $m^2/(2e+m)$. To verify this, take a uniformly random ordering and select each vertex that precedes all its neighbors. The selected set is independent, and its expected size is
$$ \sum_v\frac1{\deg(v)+1} \geq\frac{m^2}{2e+m} $$
by Cauchy–Schwarz.

Hence there is an independent set $J$ of size
$$ M:=|J|\geq\frac d{2313}. $$
For $i\in J$, standardize
$$ W_i=\frac{G_i}{\sqrt{(K_0)_{ii}}}. $$
These variables have variance one, and their off-diagonal covariances are at most $1/4$.

5.2. Gaussian comparison, with proof

We use the following comparison: if centered Gaussian vectors $X,Y$ have equal coordinate variances and
$$ \operatorname{Cov}(X_i,X_j) \leq \operatorname{Cov}(Y_i,Y_j) \quad(i\ne j), $$
then
$$ \Pr(\max_iX_i\leq t) \leq \Pr(\max_iY_i\leq t). $$

Here is a proof. For independent $X,Y$, set
$$ Z(u)=\sqrt{1-u}\,X+\sqrt u\,Y. $$
Gaussian integration by parts gives, for smooth bounded $f$,
$$ \frac d{du}\mathbb Ef(Z(u)) = \frac12\sum_{i,j} \left( \operatorname{Cov}(Y_i,Y_j) - \operatorname{Cov}(X_i,X_j) \right) \mathbb E[\partial_i\partial_jf(Z(u))]. $$
This identity follows by differentiating and applying
$$ \mathbb E[Z_i h(Z)] = \sum_j\operatorname{Cov}(Z_i,Z_j) \mathbb E[\partial_jh(Z)], $$
which is integration by parts in the Gaussian density. Singular covariance matrices follow by adding independent Gaussian noise and taking a limit.

Take $f(x)$ to be a product of smooth decreasing approximations to the indicators of $x_i\leq t$, with values in $[0,1]$. Its mixed second derivatives are nonnegative. The diagonal covariance differences vanish, so the interpolation derivative is nonnegative. Taking the indicator limit proves the comparison.

Apply it to $W$ and
$$ Y_i=\frac12Z_0+\frac{\sqrt3}{2}Z_i, $$
where $Z_0,Z_1,\ldots,Z_M$ are independent standard Gaussians.

If $\|G\|_\infty\leq a\sqrt{n\log(2d)}$, then
$$ W_i\leq 2a\sqrt{\log(2d)} \quad(i\in J). $$
Since $d\leq2313M$, a sufficiently small universal $a$ ensures, for $M\geq2$, that
$$ 2a\sqrt{\log(2d)} \leq\frac18\sqrt{\log M}. $$

On $Z_0\geq-3$, the event $\max_iY_i\leq t$ implies
$$ \max_iZ_i\leq\frac{t+3/2}{\sqrt3/2}. $$
For all sufficiently large $M$, with the above choice of $t$, this upper threshold is at most $\frac12\sqrt{\log M}$.

Moreover,
$$ \Pr\left(\max_{1\leq i\leq M}Z_i \leq\frac12\sqrt{\log M}\right)\longrightarrow0. $$
Indeed, for $u\geq0$,
$$ \Pr(Z_1>u) \geq \frac1{\sqrt{2\pi}}e^{-(u+1)^2/2}, $$
by integrating the density over $[u,u+1]$. At $u=\frac12\sqrt{\log M}$, the product of this lower bound and $M$ tends to infinity; independence then gives the asserted limit.

Choose a universal $M_0$ large enough that this maximum probability is at most $1/8$, and that the preceding threshold comparison holds, for every $M\geq M_0$. Since
$$ \Pr(Z_0<-3)\leq e^{-9/2}, $$
the required central-box probability is less than $1/4$ whenever $d\geq2313M_0$.

For the remaining finitely bounded dimensions, some coordinate has variance at least $n/2$. Its density bound gives
$$ \Pr\left(\|G\|_\infty\leq a\sqrt{n\log(2d)}\right) \leq 2a\sqrt{\frac{\log(2d)}{\pi}}. $$
Decreasing $a$ if necessary makes this at most $1/4$ for every $d<2313M_0$. This proves the first assertion with a universal $a_0>0$.

Finally, let $G'$ be an independent copy of $G$. If
$$ p=\Pr(\|G-b\|_\infty\leq\eta), $$
then
$$ p^2\leq\Pr(\|G-G'\|_\infty\leq2\eta). $$
The covariance of $G-G'$ is $2K_0$, so the first assertion, with $n$ replaced by $2n$, makes the right-hand side at most $1/4$ when
$$ \eta\leq\frac{a_0}{\sqrt2}\sqrt{n\log(2d)}. $$
Thus $p\leq1/2$, proving the lemma.

6. The strengthened joint lower bound

Consider any successful algorithm with worst-case budget $N$. Section 4 gives $N\geq\tau$.

Set
$$ d=\lfloor\tau/2\rfloor, \qquad n=\left\lceil\frac{2N}{d}\right\rceil. $$
Draw independent standard Gaussian vectors $b_j\in\mathbb R^d$, and put
$$ H=\sqrt{2\log(24nd)}. $$
Define paired coefficients
$$ a_{j,2\ell-1}=\frac{b_{j\ell}}H, \qquad a_{j,2\ell}=-\frac{b_{j\ell}}H, \qquad \ell=1,\ldots,d. $$
When $\tau$ is odd, set the final coefficient to zero.

Let $E$ be the event that all $nd$ Gaussian entries have magnitude at most $H$. The Gaussian tail bound and a union bound give
$$ \Pr(E)\geq1-2nd\,e^{-H^2/2}=\frac{11}{12}. $$
On $E$, all coefficient vectors satisfy the hypotheses of Section 3, so the resulting oracle is admissible.

For the probabilistic argument, also define these functions outside $E$, and force the algorithm to stop after $N$ queries there. This does not affect its guarantee on admissible inputs.

A query in block $j$ depends on $b_j$ through the single linear measurement
$$ \sum_{\ell=1}^d b_{j\ell}(z_{2\ell-1}-z_{2\ell}). $$
Grant the algorithm that measurement. Given it, the original response can be computed, so this is a stronger oracle.

Condition on the random seed and the strengthened transcript. Sequential Gaussian conditioning shows that the posterior block covariances are orthogonal projections $P_j$. They remain block diagonal, because each measurement acts on one block. Every query removes at most one unit of covariance trace, hence
$$ \sum_j\operatorname{tr}P_j \geq nd-N \geq\frac{nd}{2}. $$
For
$$ S=\sum_jb_j, $$
the posterior covariance is
$$ K_0=\sum_jP_j, \qquad 0\preceq K_0\preceq nI_d, \qquad \operatorname{tr}K_0\geq\frac{nd}{2}. $$

The odd-indexed allocations satisfy
$$ \Phi_{2\ell-1}=\frac{\delta_n}{H}S_\ell. $$
Thus maximum-norm allocation success requires $S$ to lie in a box of radius $\varepsilon H/\delta_n$ around a transcript-dependent center. The shifted-box assertion of Section 5 applies to its conditional Gaussian law; its conditional mean is absorbed into the center.

Consequently, conditional success probability is at most $1/2$ whenever
$$ \frac{\varepsilon H}{\delta_n} \leq \frac{a_0}{\sqrt2}\sqrt{n\log(2d)}. $$
But the guarantee on admissible inputs requires unconditional success probability at least
$$ \frac23\Pr(E)\geq\frac{11}{18}>\frac12. $$
Therefore a successful algorithm must satisfy
$$ \varepsilon> c\frac{B\tau\sqrt{\log(2d)}}{Hn^{3/2}}. $$

Because $N\geq\tau$,
$$ n\leq\frac{3N}{d}, \qquad nd\leq3N, \qquad H^2\leq2\log(72N). $$
Squaring and rearranging gives
$$ N^3\log(72N) \geq c\frac{B^2\tau^2d^3}{\varepsilon^2}\log(2d). $$
For $\tau\geq2$, $d\geq\tau/3$ and $\log(2d)$ is within universal constant factors of $\log(2\tau)$. Hence
$$ N^3\log(2+N) \geq c\tau^3r^2\log(2\tau). $$

Apply this to $N=N^*$. The deterministic upper bound gives
$$ N^*\leq C\tau(1+r), $$
so
$$ \log(2+N^*)\leq C'\lambda. $$
It follows that
$$ N^* \geq c\tau r^{2/3} \left(\frac{\log(2\tau)}{\lambda}\right)^{1/3}. $$
Together with Section 4, this proves all the lower bounds stated in Section 1.

In particular, for every fixed $A>0$, the parameter range
$$ 1\leq r\leq\tau^A $$
has the lower bound
$$ N^*\geq c_A\tau r^{2/3}. $$
The upper bound can still exceed this by a logarithmic factor.

7. Coalition data cannot determine the continuous allocation accurately

7.1. A dimension-amplified counterexample

Consider
$$ F(z)=\frac B3\,z_1\sum_{j=2}^{\tau}z_j(1-z_j). $$
Its only potentially nonzero Hessian entries are
$$ \partial_{jj}F=-\frac{2B}{3}z_1 \quad(j\geq2), $$
and
$$ \partial_{1j}F=\partial_{j1}F =\frac B3(1-2z_j) \quad(j\geq2). $$
Also $\partial_{11}F=0$.

On the open neighborhood $(-1/4,5/4)^\tau$, the absolute values of these entries are at most $5B/6$ and $B/2$, respectively. Thus $F$ meets the stated smoothness and Hessian requirements. It also satisfies $F(0)=0$.

Every coalition value is zero, because each $z_j(1-z_j)$ vanishes at a vertex. On the diagonal,
$$ \partial_1F(s\mathbf1) = \frac B3(\tau-1)s(1-s), $$
and, for $j\geq2$,
$$ \partial_jF(s\mathbf1) = \frac B3s(1-2s). $$
Therefore
$$ \Phi_1=\frac{B(\tau-1)}{18}, \qquad \Phi_j=-\frac B{18}\quad(j\geq2). $$

For the specified least-squares procedure, all observed responses and the efficiency constraint’s right-hand side are zero. The zero coefficient vector is feasible and has objective value zero. It is the unique minimizer of smallest Euclidean norm, since every nonzero coefficient vector has positive norm.

Thus the procedure always returns the zero allocation, regardless of the sampled coalitions or the permitted degree $k$. Its error is
$$ \frac{B(\tau-1)}{18}. $$
This proves its claimed failure for every
$$ \varepsilon<\frac{B(\tau-1)}{18}. $$

The same construction rules out every vertex-only algorithm at this accuracy. The admissible functions $F$ and $-F$ have identical vertex values. Hence a vertex-only algorithm has the same output distribution on both. Their success regions are disjoint when $\varepsilon<B(\tau-1)/18$, so the two success probabilities sum to at most one. At least one is therefore at most $1/2$.

7.2. An upper bound on the ambiguity of complete vertex data

The preceding obstruction has the correct order in $\tau B$.

For a vertex game $v(A)=F(\mathbf1_A)$, define its Shapley allocation by
$$ \operatorname{Sh}_i(v) = \sum_{A\subseteq[\tau]\setminus\{i\}} \frac{|A|!(\tau-|A|-1)!}{\tau!} \bigl(v(A\cup\{i\})-v(A)\bigr). $$
We prove
$$ |\operatorname{Sh}_i(v)-\Phi_i| \leq\frac{B\tau}{3}. $$

For $s\in[0,1]$, let the coordinates of $U_{-i}$ be independent Bernoulli variables with parameter $s$. The beta integral
$$ \int_0^1s^a(1-s)^b\,ds=\frac{a!\,b!}{(a+b+1)!} $$
for nonnegative integers $a,b$ follows by repeated integration by parts. Applying it with $a=|A|$ and $b=\tau-1-|A|$ gives
$$ \operatorname{Sh}_i(v) = \int_0^1 \mathbb E_s\bigl[F(U_{-i},1)-F(U_{-i},0)\bigr]\,ds. $$
The fundamental theorem of calculus then gives
$$ \operatorname{Sh}_i(v) = \int_0^1\int_0^1 \mathbb E_s[\partial_iF(U_{-i},u)]\,du\,ds. $$

Changing coordinates one at a time inside the cube, the Hessian bound implies
$$ |\partial_iF(U_{-i},u)-\partial_iF(s\mathbf1)| \leq B\left( |u-s|+\sum_{j\ne i}|U_j-s| \right). $$
Now
$$ \mathbb E_s|U_j-s|=2s(1-s), $$
and
$$ \int_0^1 2s(1-s)\,ds=\frac13, \qquad \int_0^1\int_0^1|u-s|\,du\,ds=\frac13. $$
Integrating the derivative-difference bound proves
$$ |\operatorname{Sh}_i(v)-\Phi_i| \leq B\left(\frac13+\frac{\tau-1}{3}\right) =\frac{B\tau}{3}. $$

Consequently, complete vertex data admit an estimator with maximum-norm error at most $B\tau/3$, whereas Section 7.1 gives a lower obstruction of $B(\tau-1)/18$. Their unavoidable accuracy scale is therefore
$$ \Theta(\tau B). $$

This explains the distinction from the supplied discrete result: the cited full-coalition theorem recovers the Shapley allocation of the vertex game. It does not identify that allocation with the continuous integrated-gradient allocation. [Theorem 4.2](https://arxiv.org/html/2502.04763v2)

8. Arithmetic cost of the sampled surrogate

Let $T$ be the number of sampled nonempty proper coalitions, with
$$ 0\leq T\leq2^\tau-2, $$
and let
$$ D_k=\sum_{j=0}^k\binom{\tau}{j}. $$
For the permitted degrees, $D_k=\Theta(\tau^k)$.

The procedure makes $T+2$ value queries. Every society query coordinate is either zero or an input mass, so its binary length is $O(L)$.

For a sampled coalition $A$, the design row is
$$ X_{A,S}=\mathbf1_{\{S\subseteq A\}}, \qquad |S|\leq k. $$
Forming the weighted normal equations takes $O(TD_k^2)$ arithmetic operations. The efficiency constraint is
$$ \sum_{S\ne\varnothing}c_S=F(\mathbf1)-F(0). $$
It is always feasible, for example by putting the right-hand side into one singleton coefficient.

Elimination on the constrained normal equations gives a particular minimizing coefficient vector and a basis for all homogeneous minimizing directions. Orthogonal projection off that homogeneous space selects the minimum-norm minimizer. Explicitly, if the independent basis vectors are the columns of $Z$ and $c_0$ is a particular minimizer, the selected vector is
$$ c_0-Z(Z^\mathsf TZ)^{-1}Z^\mathsf Tc_0. $$
The Gram matrix is invertible because the columns of $Z$ are independent. These operations take $O(D_k^3)$ time, including rank-deficient cases.

For a multilinear monomial indexed by nonempty $S$,
$$ \int_0^1\partial_i\prod_{t\in S}z_t\bigg|_{z=s\mathbf1}\,ds = \begin{cases} 1/|S|,&i\in S,\\ 0,&i\notin S. \end{cases} $$
Hence the returned allocations are
$$ \widehat\Phi_i=\sum_{S\ni i}\frac{c_S}{|S|}, $$
and can be formed in $O(kD_k)$ operations.

The required sampling distribution also has an implementation without enumerating all coalitions. Precompute binomial coefficients, and use the common denominator
$$ D_{\mathrm w} = \prod_{a=1}^{\tau-1}\binom{\tau-2}{a-1}. $$
Its binary length is $O(\tau^2)$. Each coalition of size $a$ then has integer weight
$$ u_a=\frac{D_{\mathrm w}}{\binom{\tau-2}{a-1}}. $$

Maintain the remaining count $m_a$ at each size. Select size $a$ with probability proportional to $m_au_a$, then select a uniform unused coalition of that size. Each remaining coalition consequently receives probability proportional to its required weight.

Exact uniform integers can be sampled by rejection from the next power-of-two range, with fewer than two expected trials. The relevant weight totals have $O(\tau^2)$ bits. Store removed combinatorial ranks in sorted lists; mapping an unused rank to its original rank and updating the lists takes $O(T)$ operations per draw. Combinatorial unranking takes $O(\tau)$ operations using the precomputed binomial coefficients.

A conservative total expected arithmetic and random-bit operation bound is therefore
$$ O\left( L+\tau^2+T\tau^2+T^2+TD_k^2+D_k^3 \right). $$
This running-time statement supplies no continuous-allocation accuracy guarantee.

9. What remains open

The fixed-support minimax rate is established, and the sampled surrogate’s failure is established at the stronger accuracy threshold of order $\tau B$.

The joint minimax bounds do not match within universal constant factors. In particular, the strengthened Gaussian lower bound does not determine whether the logarithmic factor in the randomized upper bound is necessary, or whether another value-only algorithm can remove it. No sharp joint asymptotic formula is claimed.

⟨structured verdict parsed — rendered above⟩

Overall assessment

The output establishes substantial partial results, but does not resolve the requested joint asymptotics of $N^*(\tau,B,\varepsilon)$. Its upper bounds, lower bounds, fixed-support rate, and counterexample to the sampled surrogate are sound in substance. I found no false central step.

The principal remaining issue is explicitly acknowledged: the joint lower and upper bounds do not match. There is also a minor regularity omission in the stated Gaussian interpolation identity.

Step-by-step verification

1. Reduction and upper bounds

Section 2.1: correct. Positivity and rationality of the masses make both query transformations rational and invertible. Thus the masses affect coordinate lengths rather than query counts.

The chain-rule bound
$$ |g_i'(s)|\leq \tau B $$
uses exactly the supplied entrywise Hessian bound. The efficiency identity follows by integrating the derivative of $F(s\mathbf1)$. No bound on the affine part of $F$ is needed.

Section 2.2: correct. The chosen sign and $h\leq 1/2$ keep both finite-difference points in the cube, including at the endpoints and at $s=1/2$. The coordinate derivative varies by at most $Bu$, so
$$ |d_i(s)-g_i(s)|\leq \frac{Bh}{2}\leq \frac{\varepsilon}{4}. $$
The shared diagonal evaluation gives the claimed $\tau+1$ queries.

Section 2.3: correct. The midpoint error calculation gives $D/(4n)$ with $D=\tau B$. The choice $n\geq r$ makes this at most $\varepsilon/4$. The stated total error and query count follow.

Section 2.4: correct. The finite sampling grid makes every query rational. Averaging over the independent uniform choices gives midpoint quadrature on $nM$ cells, and $nM\geq r$ controls its bias.

For each fixed coordinate, the summands are independent and have range lengths at most $D/n^2$. Hoeffding’s inequality therefore gives exactly
$$ 2\exp\left(-\frac{n^3\varepsilon^2}{2D^2}\right). $$
The choice $n^3\geq 2r^2\ell$, together with $\ell\geq\log(6\tau)$, makes this at most $1/(3\tau)$. Independence between coordinates is unnecessary for the union bound.

The three error contributions sum to $\varepsilon$, and selecting the cheaper construction establishes the stated upper bound.

Section 2.5: correct under the stipulated arithmetic model. The dyadic exponents have the claimed logarithmic sizes. Multiplication by an input mass adds at most $O(L)$ bits. The running times account for explicitly constructing all query coordinates, and the randomized construction uses a fixed number of bits per stratum.

2. Smooth lower-bound family

Section 3: correct. The boundary vanishing of the functions and their first two derivatives makes $P$ and $R$ globally twice continuously differentiable. The integral $I=1/140$ is correct.

The supports in the variable $ns(z)$ ensure that at most one summand contributes derivatives at a point. At shared boundaries, its derivatives through order two vanish.

The displayed Hessian formula has the correct scaling: the two differentiation factors cancel the factor $\tau^2/n^2$. The bounds on the coefficients and the definition of $K$ consequently give the required Hessian bound.

The zero-sum coefficient condition eliminates $q_j$ on the diagonal. Differentiating before restriction produces the stated allocation formula
$$ \Phi_i=\frac{BI\tau}{Kn^2}\sum_j a_{ji}. $$
The one-block-per-query property also holds away from the diagonal.

3. Affine and scalar lower bounds

Section 4.1: correct. Conditioning on the random seed permits sequential conditioning on adaptive linear measurements. Each informative measurement removes one Gaussian direction; dependent measurements remove none. With fewer than $\tau$ measurements, a residual unit direction retains variance $R_0^2$.

Maximum-norm success implies the displayed scalar error bound by Cauchy–Schwarz. The Gaussian density calculation is correct and gives a success probability strictly below $2/3$. Averaging over the Gaussian input distribution contradicts a guarantee on every affine input.

Section 4.2: correct. Revealing an entire sign for every queried block strengthens the oracle. Unrevealed signs remain independent and uniform under adaptive querying.

The central-atom bounds, including the odd case, are correct. The allocation lattice has spacing $2\delta_n$, giving the stated bound on the number of values in an error interval.

For $n=32(N+1)$, the residual sign count is at least $31N+32$. The displayed conditional success bound is consequently below $2/3$ under the stated error condition. Its rearrangement gives the scalar lower bound with dimension amplification.

4. Gaussian maximum-norm lemma

Section 5.1: correct. The trace condition gives $|T|\geq d/3$. The spectral bound gives the stated Frobenius-norm estimate and the edge bound $128d$.

The random-order independent-set argument and its Cauchy–Schwarz estimate are valid. The constant $2313$ is consistent with these bounds. Standardization gives off-diagonal covariances at most $1/4$.

Section 5.2: sound, with one minor regularity omission. The comparison argument has the correct direction: increasing off-diagonal covariances increases the probability that all coordinates lie below the same threshold. Products of decreasing, nonnegative smoothing functions have nonnegative mixed second derivatives.

However, the interpolation identity is stated for every “smooth bounded $f$.” Boundedness of $f$ alone does not ensure the derivative integrability needed for differentiation under expectation and Gaussian integration by parts.

Minimum clarification: restrict the identity to smooth functions with bounded first and second derivatives, and specify that the indicator approximations satisfy this condition. This is an expositional repair; the functions needed in the argument can satisfy it.

The remainder checks out:

• The comparison vector has unit coordinate variances and off-diagonal covariance $1/4$.
• The standardization threshold follows from the selected variance lower bound.
• The Gaussian tail estimate obtained by integrating over a unit interval is valid.
• The sufficiently large dimension argument and the bounded-dimension density argument yield a universal positive constant.
• The independent-copy argument gives the shifted-box assertion with the stated factor $1/\sqrt2$.

5. Strengthened joint lower bound

Section 6: correct in substance. The paired coefficients satisfy the zero-sum condition. On $E$, their magnitudes are at most one. The Gaussian tail union bound gives $\Pr(E)\geq 11/12$.

Each strengthened query reveals one linear measurement in one block and permits reconstruction of the original value response. Sequential Gaussian conditioning therefore leaves block-diagonal projection covariances and loses at most one unit of trace per query.

The covariance bounds for the sum of blocks meet the Gaussian lemma’s hypotheses. Absorbing the conditional mean into the estimator’s center is legitimate.

The conditioning argument does not incorrectly apply the Gaussian lemma after conditioning on $E$. It applies the lemma under the unconditioned Gaussian distribution, while the success guarantee on admissible inputs supplies the separate lower bound
$$ \Pr(\text{success})\geq \frac23\Pr(E). $$
These bounds yield the required contradiction.

The subsequent estimates for $n$, $nd$, and $H$, and the rearrangement to
$$ N^3\log(2+N)\geq c\tau^3r^2\log(2\tau), $$
are correct. Using the already established deterministic upper bound to control $\log(2+N^*)$ is also valid.

The fixed-$\tau$ conclusion follows from the scalar lower bound, the affine lower bound, and the randomized upper bound.

6. Failure of the sampled surrogate

Section 7.1: correct and decisive. The polynomial counterexample is admissible even on the explicitly supplied open neighborhood. Its Hessian entries and allocations are computed correctly.

Every vertex response is zero. The zero coefficient vector is feasible, has zero objective, and uniquely has smallest coefficient norm. Thus every permitted degree and every sample budget return zero, with the claimed deterministic error.

For arbitrary vertex-only algorithms, the indistinguishability of $F$ and $-F$ and the disjoint success regions establish the stronger impossibility statement.

Section 7.2: correct. The beta-integral representation reproduces the Shapley coefficients. The fundamental theorem of calculus and the coordinatewise Hessian estimate apply entirely inside the cube.

Both integrated absolute deviations equal $1/3$, so the bound $B\tau/3$ is correct. Together with the counterexample, this establishes the asserted order of vertex-data ambiguity.

The cited discrete theorem concerns complete coalition data for the specified weights and degrees; it supplies no continuous attribution identification or sampled accuracy guarantee. This agrees with [Theorem 4.2 and the accompanying sampling discussion](https://arxiv.org/html/2502.04763v2).

7. Surrogate arithmetic costs

Section 8: correct under unit-cost exact arithmetic. The design rows and efficiency constraint are correct. Feasibility, constrained least-squares elimination, and projection onto the orthogonal complement of homogeneous minimizing directions justify the minimum-norm computation, including rank-deficient cases.

The monomial attribution formula and the resulting allocation cost are correct.

The sampling implementation gives every remaining coalition the required probability. The common denominator has the claimed bit-length bound. The final time estimate is explicitly expected, appropriately accounting for rejection sampling; it is not a worst-case running-time assertion.

Remaining task-level issue

Major — unresolved joint minimax rate. The output does not determine an asymptotically optimal query complexity uniformly in $\tau$, $B$, and $\varepsilon$. Its matching fixed-support bounds do not settle the growing-support question. Sections 1 and 9 acknowledge this accurately.

Minimum additional work needed: establish matching joint bounds, or otherwise resolve the discrepancy between the displayed bounds. Merely restating the fixed-support result cannot complete this part of USER_TASK.

The surrogate question is resolved negatively in general. The joint minimax question remains open within this output.

⟨structured verdict parsed — rendered above⟩