d4-conf-ijcai-2021-0271

The strongest positive case is a continuous Aumann–Shapley estimation problem for games with many agents but few complete agent types. There is one qualification up front: the paper proves no numbered NP-hardness, polynomial-time, FPT, or similar complexity result. Its strongest anchors are named results about the accuracy of sampling estimators. They support an approximation question, but they do not meet a strict requirement for a complexity-class anchor.

The lead is Theorem 6.1, “Vector SEBM bound,” proved in this paper. It extends the paper’s main Theorem 4.5, “Stratified Empirical Bernstein Bound,” also proved here. Theorem 4.5 considers finite data divided into strata, with bounded range \(D_i\), stratum mean \(\mu_i\), and sample mean \(\chi_{i,m_i}\). For positive weights \(\tau_i\), it bounds the error in their weighted sum:
\[ \Pr\!\left( \frac{\left|\sum_i\tau_i(\chi_{i,m_i}-\mu_i)\right|} {\sqrt{\log(6/p)}} \ge \sqrt{\alpha+(\sqrt{\beta}+\sqrt{\gamma})^2} \right)\le p. \]
Here \(\alpha,\beta,\gamma\) are the theorem’s explicit terms in the stratum ranges, sample counts, sample variances, and the sampling factors \(\Omega_{m_i}^{n_i}\) and \(\Psi_{m_i}^{n_i}\). In particular, the bound uses observed sample variances as well as known range bounds. Theorem 6.1 gives the corresponding simultaneous vector guarantee: for \(M\)-dimensional samples with coordinate ranges \(D_{i,j}\), the squared Euclidean error of the weighted vector estimate is at most \(\log(6/p)\sum_{j=1}^M\bigl(\alpha_j+(\sqrt{\beta_j}+\sqrt{\gamma_j})^2\bigr)\), except with probability \(Mp\). Its coordinatewise terms are those of Theorem 4.5 with coordinate-specific ranges and sample variances. The paper’s Algorithm 1 uses the bound to choose, one sample at a time, the stratum that most reduces it; the paper evaluates that method numerically, but does not prove a complexity bound for the algorithm.

Here is a concrete continuous mirror. Take a demand-response cooperative game with many households, grouped into \(\tau\) types by all characteristics the game uses: for example, load profile, location, reliability, and participation cost. A plausible regime is hundreds of thousands of households represented by a few dozen or hundred such types. Let \(\mu_t\) be the fraction of households of type \(t\). Represent the coalition surplus at a vector \(x\) of participating type masses by a differentiable function \(F(x)\).

The continuum value assigned per unit of type \(t\) along proportional growth of the society is
\[ \Phi_t=\int_0^1 \partial_t F(\lambda\mu)\,d\lambda. \]
The aggregate allocation to type \(t\) is \(\mu_t\Phi_t\). This has the right efficiency property:
\[ \sum_t\mu_t\Phi_t=F(\mu)-F(0). \]
It also has a direct high-multiplicity reading. If a finite society with \(n\) households has extensive coalition value \(nF(x)\), then the marginal contribution of one type-\(t\) household approaches \(\partial_tF(x)\); as \(n\) grows, a random predecessor coalition’s type masses concentrate near \(\lambda\mu\). The finite Shapley average over coalition sizes then approaches the integral above.

I would call the resulting lead problem Vector Continuous Shapley Estimation. An instance consists of rational type masses \(\mu\), a differentiable game \(F\) accessible through an oracle returning \(\nabla F(\lambda\mu)\), known bounds on each gradient coordinate over each of \(K\) intervals partitioning \([0,1]\), a query budget \(B\), and an error target \(\varepsilon\) and failure probability \(\delta\). The task is to allocate \(B\) gradient queries among those intervals and return estimates \(\hat\Phi_t\) such that
\[ \Pr\!\left(\|\hat\Phi-\Phi\|_2\le\varepsilon\right)\ge 1-\delta. \]
The estimator samples \(\lambda\) uniformly within each interval, averages the returned gradients there, and weights each average by the interval’s length. Its solution also reports the aggregate type allocations \(\mu_t\hat\Phi_t\). The sampling allocation can minimize the vector SEBB radius using the observed sample variances. This is the direct analogue of Theorem 6.1; estimating one specified type’s value is the scalar version anchored by Theorem 4.5.

I expect this approximation problem to be Class A in the stated oracle model: bounded-gradient stratified sampling gives query complexity polynomial in \(\tau\), \(K\), \(1/\varepsilon\), and \(\log(1/\delta)\), independent of the number of households. That is an approximation claim under explicit oracle and boundedness assumptions, not a polynomial-time theorem in the paper. The paper’s without-replacement tightening is finite-population machinery; the continuous-path version would use sampling with replacement, or require a separately justified extension of the bound.

The extension to all \(\tau\) type values is not a separate kind of mirror: it is the simultaneous-output form of the same estimation question, and Theorem 6.1 makes it the natural lead. Further questions include the rate at which finite Shapley values converge to these type-level values, what replaces the gradient for nonsmooth games such as threshold voting games, and how the bounds change when the type support itself grows.

The soft spot is that the continuum changes what is sampled. In the finite paper, samples are random coalitions within discrete coalition-size strata; in the limit, within-type coalition fluctuations disappear, leaving an integral over population growth. For smooth extensive games that is a natural Shapley limit, but it makes the continuous estimation problem easier and somewhat different from the paper’s finite-coalition sampling task. A referee could accept the Aumann–Shapley integral as the authors’ continuous analogue of Shapley allocation while still judging the SEBB-based numerical method to be an extension rather than a direct continuization of their main computational contribution.