Answer: For \(m=1\), every type satisfies \(\phi_t^{(n)}\to\sigma_t\) along the specified replication sizes. Exact computation of \((\sigma_t)_{t=1}^{\tau}\) is polynomial-time solvable in \(\tau,L\).
Theorem 1 — class: hardness
Given rational type masses \(\mu_t>0\) summing to \(1\), integer lengths \(\ell_t\) and values \(w_t\), and a rational per-capita capacity \(b\) with \(0<b<\sum_t\mu_t\ell_t\), define \(V_b(x)=\max\{\sum_t w_ty_t:0\leq y_t\leq x_t,\ \sum_t\ell_ty_t\leq b\}\). For replicated finite instances with \(n\mu_t\) agents of type \(t\) and capacity \(nb\), along sufficiently large common-denominator multiples \(n\), prove whether the per-agent Shapley shares converge to \(\sigma_t=\int_0^1\partial_t^+V_b(\alpha\mu)\,d\alpha\), and compute those limiting shares exactly.
A society is given by its support: \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts listed types, not possible types. Type \(t\) has binary encoded integers \(\ell_t>0\) and \(w_t\geq0\). There is one capacity constraint, \(m=1\), with rational \(0<b<\sum_t\mu_t\ell_t\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
For \(x\in\mathbb R_{\geq0}^{\tau}\), define \(V_b(x)=\max\{\sum_t w_ty_t:0\leq y_t\leq x_t,\ \sum_t\ell_ty_t\leq b\}\), with real selection masses \(y_t\).
Define \(\partial_t^+V_b(x)=\lim_{h\downarrow0}[V_b(x+he_t)-V_b(x)]/h\), where \(e_t\) is the coordinate unit vector, and \(\sigma_t=\int_0^1\partial_t^+V_b(\alpha\mu)\,d\alpha\). Equal value-to-length ratios are allowed; only optimal values are used, so no optimizer tie-breaking is imposed.
Let \(D\) be a common denominator of \(b\) and all masses. For positive multiples \(n\) of \(D\) satisfying \(nb\geq\max_t\ell_t\), form \(N_n\) with \(n\mu_t\) indivisible agents of type \(t\).
Its coalition value is \(v_n(S)=\max\{\sum_{i\in T}w_{t(i)}:T\subseteq S,\ \sum_{i\in T}\ell_{t(i)}\leq nb\}\), where \(t(i)\) denotes agent \(i\)'s type. Let \(\phi_t^{(n)}\) be the ordinary Shapley value of one type-\(t\) agent, with coalition values unscaled.
Do \(\phi_t^{(n)}\to\sigma_t\) for every type along these replication sizes?
Is exact computation of \((\sigma_t)_{t=1}^{\tau}\) polynomial in \(m,\tau,L\), or is it NP-hard?
Exact Shapley computation for finite indivisible knapsack budgeted games is NP-hard. [Source](https://arxiv.org/html/1409.5200).
No result settling this exact continuous computation problem or its stated indivisible replication limit was located in the literature search.
For the stated class with \(m=1\), both questions are settled:
The proofs allow equal value-to-length ratios and zero values.
Write the distinct ratios as \(r_1>\cdots>r_q\geq0\), where \(q\leq\tau\), and let \(G_j=\{t:w_t/\ell_t=r_j\}\). Set \(r_{q+1}=0\) and define
\(A_j=\sum_{s\in G_1\cup\cdots\cup G_j}\mu_s\ell_s,\qquad \Delta_j=r_j-r_{j+1},\qquad \beta_j=\min\{1,b/A_j\}.\)
Every \(A_j\) is positive because every listed mass and length is positive.
We will prove that, for \(t\in G_i\),
\(\displaystyle \boxed{\sigma_t=\ell_t\sum_{j=i}^{q}\Delta_j\beta_j.}\)
For arbitrary \(x\in\mathbb R_{\geq0}^{\tau}\), define the available length in the first \(j\) ratio groups by
\(C_j(x)=\sum_{s\in G_1\cup\cdots\cup G_j}\ell_sx_s.\)
Then
\(\displaystyle V_b(x)=\sum_{j=1}^{q}\Delta_j\min\{b,C_j(x)\}.\)
To prove this, take any feasible selection \(y\), and let \(z_s=\ell_sy_s\) denote its selected length of type \(s\). Telescoping the ratios gives
\(\displaystyle \sum_s w_sy_s=\sum_{j=1}^{q}\Delta_j\sum_{s\in G_1\cup\cdots\cup G_j}z_s.\)
Each inner sum is at most both \(b\) and \(C_j(x)\). Since every \(\Delta_j\) is nonnegative, this proves the claimed expression is an upper bound.
For attainment, select available length in decreasing order of ratio until either capacity is exhausted or all available length has been selected. This selection is feasible and, for every \(j\), selects exactly \(\min\{b,C_j(x)\}\) length from the first \(j\) groups. It therefore attains the upper bound. An arbitrary order within each group suffices; the resulting optimal value is independent of that order.
If \(t\in G_i\), increasing \(x_t\) by \(h\) increases \(C_j(x)\) by \(\ell_th\) exactly when \(j\geq i\). The right derivative of \(\min\{b,c+\ell_th\}\) at \(h=0\) is \(\ell_t\) when \(c<b\), and zero when \(c\geq b\), including equality. Consequently,
\(\displaystyle \partial_t^+V_b(x)=\ell_t\sum_{j=i}^{q}\Delta_j\,\mathbf 1_{\{C_j(x)<b\}}.\)
Along the prescribed path, \(C_j(\alpha\mu)=\alpha A_j\). Integrating this finite sum gives
\(\displaystyle \sigma_t=\ell_t\sum_{j=i}^{q}\Delta_j\int_0^1\mathbf 1_{\{\alpha A_j<b\}}\,d\alpha =\ell_t\sum_{j=i}^{q}\Delta_j\min\{1,b/A_j\},\)
as claimed. In particular, ties introduce no ambiguity into either the derivative or the integral.
The formula gives the following algorithm:
This uses \(O(\tau\log(\tau+1))\) exact arithmetic operations and comparisons.
For completeness, the intermediate bit lengths are polynomially bounded. Let \(Q\) be the product of the input denominators of \(b\) and the masses. Its bit length is \(O(L)\). Each cumulative length can be represented over \(Q\); because \(A_j\leq\max_t\ell_t\), its numerator also has \(O(L)\) bits. Thus every individual term \(\Delta_j\beta_j\) has a numerator and denominator of \(O(L)\) bits.
Adding at most \(\tau\) such terms without fraction reduction gives numerators and denominators of \(O(\tau L)\) bits. The final multiplication by \(\ell_t\) preserves that bound. Using elementary integer arithmetic, a conservative bit-operation bound is therefore
\(\displaystyle T(1,\tau,L)=O\!\left(\tau^3\log(\tau+1)L^2\right).\)
Hence exact continuous computation is polynomial-time solvable on the stipulated class \(m=1\). The cited [NP-hardness result for finite knapsack budgeted games](https://arxiv.org/html/1409.5200) concerns a different computation and does not contradict this formula.
Fix an admissible replication size \(n\), and write \(B_n=nb\). For an integer count vector \(k\in\mathbb Z_{\geq0}^{\tau}\), define
\(\displaystyle f_n(k)=\max\left\{\sum_s w_sz_s:z\in\mathbb Z_{\geq0}^{\tau},\ z_s\leq k_s,\ \sum_s\ell_sz_s\leq B_n\right\},\)
and let \(F_n(k)\) be the same optimum with real selections. Scaling the real selections gives
\(F_n(k)=nV_b(k/n).\)
Let \(W=\max_s w_s\). For every count vector,
\(\displaystyle 0\leq F_n(k)-f_n(k)\leq W.\)
Indeed, a fractional greedy optimum, using a fixed order of types with nonincreasing ratios, has at most one nonintegral selected count: types before the capacity cutoff are selected completely, and types after it are not selected. Rounding the one possible nonintegral count down preserves feasibility and loses at most \(W\). This proves the bound.
We also have, for every type \(t\),
\(\displaystyle 0\leq f_n(k+e_t)-f_n(k)\leq w_t,\qquad 0\leq F_n(k+e_t)-F_n(k)\leq w_t.\)
Monotonicity proves the lower bounds. For the upper bounds, take an optimum at \(k+e_t\) and remove at most one unit of its type-\(t\) selection to meet the bounds at \(k\). This preserves capacity feasibility and loses at most \(w_t\).
A bounded value error alone does not imply convergence of marginal contributions. The next step establishes the necessary averaging.
We first prove an elementary smoothing lemma.
Lemma. Fix \(p\in(0,1)\). If \(X_M\) has the binomial distribution with parameters \(M,p\), and \(a:\mathbb Z\to[0,W]\), then
\(\displaystyle \left|\mathbb E[a(X_M+1)-a(X_M)]\right| \leq W\max_k\Pr(X_M=k),\)
and the right-hand side tends to zero as \(M\to\infty\), uniformly over the choice of \(a\).
Proof. Write \(p_k=\Pr(X_M=k)\), extending it by zero outside its support. Then
\(\displaystyle \mathbb E[a(X_M+1)-a(X_M)] =\sum_k a(k)(p_{k-1}-p_k).\)
The binomial probabilities are unimodal, because
\(\displaystyle \frac{p_{k+1}}{p_k}=\frac{M-k}{k+1}\frac{p}{1-p}\)
decreases with \(k\). Thus the total positive mass, and the total negative mass in absolute value, of \(p_{k-1}-p_k\) both equal \(\max_k p_k\). Since \(a(k)\in[0,W]\), the asserted inequality follows.
To verify that \(\max_k p_k\to0\), coefficient extraction gives
\(\displaystyle p_k=\frac1{2\pi}\int_{-\pi}^{\pi}(1-p+pe^{iu})^Me^{-iku}\,du.\)
Now \(\lvert1-p+pe^{iu}\rvert^2=1-4p(1-p)\sin^2(u/2)\). Using \(1-z\leq e^{-z}\) and \(\sin(|u|/2)\geq|u|/\pi\) for \(|u|\leq\pi\), we obtain
\(\displaystyle p_k\leq\frac1{2\pi}\int_{-\pi}^{\pi} \exp\!\left(-\frac{2Mp(1-p)u^2}{\pi^2}\right)\,du \leq\frac{\sqrt{\pi}}{2\sqrt{2Mp(1-p)}}.\)
This tends to zero for fixed \(p\in(0,1)\), completing the proof.
There are \(N_s=n\mu_s\) agents of type \(s\). Fix a tagged type-\(t\) agent. Assign independent uniform priorities in \([0,1]\) to all agents and order them by priority. By exchangeability and the absence of ties almost surely, this is a uniform random permutation.
Conditioned on the tagged priority being \(\alpha\), the predecessor counts \(K_s\) are independent, with
\(\displaystyle K_s\sim\operatorname{Bin}(N_s-\mathbf1_{\{s=t\}},\alpha).\)
The random-permutation definition of the Shapley value therefore gives
\(\displaystyle \phi_t^{(n)} =\int_0^1\mathbb E[f_n(K+e_t)-f_n(K)]\,d\alpha.\)
Define the error \(g_n(k)=F_n(k)-f_n(k)\), which belongs to \([0,W]\). For fixed \(\alpha\in(0,1)\), condition on all counts except \(K_t\) and apply the lemma to the function of the remaining coordinate \(g_n\). Independence then gives
\(\displaystyle \left|\mathbb E[g_n(K+e_t)-g_n(K)]\right| \leq W\max_k\Pr\!\left(\operatorname{Bin}(N_t-1,\alpha)=k\right) \longrightarrow0.\)
Here \(N_t-1\to\infty\) because \(\mu_t>0\). Consequently, for every fixed \(\alpha\in(0,1)\), the expected integer and fractional marginal contributions differ by a quantity tending to zero.
Fix \(\alpha\in(0,1)\) outside the finite set of thresholds \(b/A_j\). For each type \(s\),
\(\displaystyle \mathbb E[K_s/n]=\alpha\mu_s-\frac{\alpha}{n}\mathbf1_{\{s=t\}},\qquad \operatorname{Var}(K_s/n)\leq\frac{\mu_s}{4n}.\)
Chebyshev’s inequality implies \(K_s/n\to\alpha\mu_s\) in probability. Since there are finitely many types, every prefix length satisfies
\(C_j(K/n)\to\alpha A_j\quad\text{in probability}.\)
Let \(t\in G_i\), and put \(H_j(K)=nC_j(K/n)\). The continuous value formula yields the exact identity
\(\displaystyle F_n(K+e_t)-F_n(K) =\sum_{j=i}^{q}\Delta_j \bigl[\min\{nb,H_j(K)+\ell_t\}-\min\{nb,H_j(K)\}\bigr].\)
If \(\alpha A_j<b\), then with probability tending to one, \(H_j(K)+\ell_t<nb\), so the bracket equals \(\ell_t\). If \(\alpha A_j>b\), then with probability tending to one, \(H_j(K)>nb\), so the bracket equals zero. The exclusion of thresholds ensures these are the only cases.
Each bracket lies in \([0,\ell_t]\). Its expectation therefore converges to \(\ell_t\mathbf1_{\{\alpha A_j<b\}}\). Summing finitely many terms proves
\(\displaystyle \mathbb E[F_n(K+e_t)-F_n(K)] \longrightarrow \ell_t\sum_{j=i}^{q}\Delta_j\mathbf1_{\{\alpha A_j<b\}} =\partial_t^+V_b(\alpha\mu).\)
Combining this with the error estimate proves the same limit for the expected integer marginal, for almost every \(\alpha\).
Finally, those expected integer marginals always lie in \([0,w_t]\). Dominated convergence applies on \([0,1]\), giving
\(\displaystyle \lim_{\substack{n\to\infty\\ D\mid n,\;nb\geq\max_s\ell_s}} \phi_t^{(n)} =\int_0^1\partial_t^+V_b(\alpha\mu)\,d\alpha =\sigma_t.\)
This proves convergence for every listed type along all the required replication sizes.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. Both claims are established for the stipulated class \(m=1\): convergence of every type’s indivisible Shapley value to its specified continuous value, and exact polynomial-time computation of the continuous vector. I found no major or minor issues requiring repair.
The argument addresses the supplied problem directly:
Positive masses and lengths ensure \(A_j>0\), so every division by \(A_j\) is valid. The common-denominator condition ensures that the replicated type counts are integers. For each fixed type, these counts tend to infinity along the admissible sizes.
The identity
\(V_b(x)=\sum_{j=1}^{q}\Delta_j\min\{b,C_j(x)\}\)
is correctly proved.
For the upper bound, a type in group \(G_i\) occurs in exactly the prefixes indexed by \(j\geq i\), and its total coefficient is
\(\sum_{j=i}^{q}\Delta_j=r_i\).
Thus the telescoping expression reproduces its value exactly. Each selected prefix length is bounded by both its available length and the total capacity. Multiplying these bounds by nonnegative \(\Delta_j\) preserves the inequalities.
The proposed greedy selection attains every prefix bound simultaneously. Before the capacity cutoff, a prefix is selected completely; after the cutoff, it contains the entire selected capacity. This also holds when all available length is below capacity.
Ties cause no problem because selection within a group does not change its ratio. If the last ratio is zero, its coefficient \(\Delta_q\) is zero, so filling unused capacity with zero-value material does not affect optimality.
Assessment: correct and complete.
For \(t\in G_i\), the affected prefixes are exactly those with \(j\geq i\). The right derivative of their truncated length is correctly evaluated:
In particular, the equality case is handled in the direction required by the definition of \(\partial_t^+\).
Along the path, \(C_j(\alpha\mu)=\alpha A_j\). The set of \(\alpha\in[0,1]\) satisfying \(\alpha A_j<b\) has measure \(\min\{1,b/A_j\}\). Strictness at an endpoint does not change this measure.
The resulting formula
\(\sigma_t=\ell_t\sum_{j=i}^{q}\Delta_j\beta_j\)
therefore follows exactly. The derivative exists everywhere on the path, and its finite indicator representation establishes integrability.
Assessment: correct, including thresholds, ties, and zero values.
The algorithm correctly implements the formula.
Cross-multiplication compares ratios exactly because all lengths are positive. Grouping equal ratios and computing suffix sums require no optimizer tie-breaking.
The bit-length claims are valid:
The arithmetic-operation count \(O(\tau\log(\tau+1))\) is valid. With elementary integer arithmetic on the stated intermediate sizes, the conservative bound
\(T(1,\tau,L)=O(\tau^3\log(\tau+1)L^2)\)
is a valid polynomial upper bound.
The distinction from finite indivisible Shapley computation is appropriate. The [cited paper](https://arxiv.org/html/1409.5200) states NP-hardness for that finite computation; the prover does not use it to justify the continuous algorithm.
Assessment: exact polynomial-time computation is established.
The scaling identity \(F_n(k)=nV_b(k/n)\) correctly scales both selection bounds and capacity.
For integer availability counts, the described fractional greedy optimum has at most one nonintegral selected count. Rounding that count down preserves feasibility and loses at most one item’s value. Therefore
\(0\leq F_n(k)-f_n(k)\leq W\)
holds uniformly over \(k\) and \(n\).
The marginal bounds are also correct. An optimal selection under \(k+e_t\) can exceed the type-\(t\) availability under \(k\) by at most one unit. Removing that excess preserves feasibility and loses at most \(w_t\), in either the integer or fractional model. Monotonicity supplies the lower bounds.
The prover correctly recognizes that a bounded value error alone does not establish marginal convergence.
Assessment: correct; the required marginal averaging is addressed separately.
The smoothing lemma is valid.
The shifted-probability identity has the correct sign and indexing. Binomial unimodality implies that the positive and negative masses of \(p_{k-1}-p_k\) each equal the maximum binomial probability. Because \(a\) takes values in \([0,W]\), the claimed bound follows with the stated constant \(W\).
The Fourier coefficient formula and modulus calculation are correct. The exponential estimate has the correct factor \(2Mp(1-p)\). Extending the Gaussian integral to the real line yields precisely the displayed upper bound
\(\sqrt{\pi}/(2\sqrt{2Mp(1-p)})\).
It tends to zero for each fixed \(p\in(0,1)\).
Independent continuous priorities generate a uniform random permutation. Conditional on the tagged priority, the predecessor counts are independent binomials with exactly the stated parameters, including exclusion of the tagged agent.
Consequently, the integral representation of its ordinary Shapley value is correct. Conditioning on the other type counts permits application of the smoothing bound to \(g_n\). Its uniformity over the function being averaged is essential here and is supplied by the lemma.
Since \(\mu_t>0\), \(N_t-1\to\infty\). Thus the expected integer and fractional marginals differ by a quantity tending to zero at every fixed interior priority.
Assessment: the central averaging argument is rigorous.
The mean and variance formulas for \(K_s/n\) are correct, including the tagged-agent correction. Chebyshev’s inequality applies because the variance tends to zero and the mean tends to \(\alpha\mu_s\). With finitely many types, the corresponding prefix lengths converge in probability.
The displayed identity for the fractional marginal follows directly from the continuous value formula and scaling.
Away from the finite set of thresholds, each limiting prefix length has a strictly positive distance from capacity. The stated probability conclusions therefore follow, including the extra increment \(\ell_t\). Each bracket is bounded by \(\ell_t\), which justifies convergence of its expectation to the stated constant.
Combining this limit with the smoothing estimate establishes convergence of the expected integer marginal for almost every \(\alpha\).
The final dominated-convergence application satisfies its hypotheses: the expected marginals are measurable, converge almost everywhere, and are uniformly bounded by the integrable constant \(w_t\). The exceptional thresholds and endpoints have measure zero. No uniform convergence in \(\alpha\) is needed.
If \(w_t=0\), the marginal bound makes the discrete marginal identically zero, and the continuous formula also gives zero. Thus this edge case is covered.
Assessment: the replication limit follows for every listed type along all specified sizes.
None. The submitted argument resolves both assigned questions without a missing mathematical step.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.