Answer: \(\text{All limits exist and are rational; exact vector evaluation is polynomial-time solvable.}\)
Proposition 1 — class: other
Given finitely many unions and rational type masses μ_{kt} summing to one, and an explicitly encoded rational polynomial worth function \(V\) on coalition type-mass vectors, define each replicated finite game by \(v_n(S)=V(x(S)/n)\), where \(x(S)\) counts coalition members by type. For each type \(t\) in union \(k\), compute exactly the limit of \(n\) times an individual’s two-step Shapley value as common-denominator replications \(n\) grow, and determine the evaluation complexity in the number of unions, number of supported types, and input bit length.
A society is given by its support: \(\tau\) union–type pairs \((k,t)\), each with positive binary rational mass \(\mu_{kt}\), with \(\sum_{k,t}\mu_{kt}=1\). There are \(m\geq1\) unions, each of positive total mass; \(\tau\) is the support size, not the number of possible types.
The worth function \(V\in\mathbb{Q}[z_{kt}]\) is supplied as an explicit list of monomials with binary rational coefficients and unary nonnegative integer exponents. Require \(V(0)=0\); coefficients and worths may have either sign. Let \(L\) be the total input bit length.
Let \(D\) be the least common multiple of the mass denominators. For every positive multiple \(n\) of \(D\), union \(B_k^{(n)}\) contains \(n\mu_{kt}\) individuals of each supported type \(t\). Set \(B^{(n)}=\{B_k^{(n)}\}_{k=1}^{m}\) and \(v_n(S)=V(x(S)/n)\), where \(x_{kt}(S)\) counts members of \(S\) of union–type \((k,t)\).
Write \(M=\{1,\ldots,m\}\) and \(q_n(T)=v_n(\bigcup_{k\in T}B_k^{(n)})\). Using the ordinary Shapley value \(\operatorname{Sh}\), define the two-step value for \(i\in B_k^{(n)}\) by \(\psi_i^{(n)}=\operatorname{Sh}_i(B_k^{(n)},v_n|_{B_k^{(n)}})+[\operatorname{Sh}_k(M,q_n)-v_n(B_k^{(n)})]/|B_k^{(n)}|\).
For each supported pair, let \(i_{kt}^{(n)}\) be any individual of that pair and define \(a_{kt}=\lim_{n\to\infty,\,D\mid n}n\psi_{i_{kt}^{(n)}}^{(n)}\), whenever the limit exists.
Do all limits \(a_{kt}\) exist, and what are their exact values? Is computing the vector \((a_{kt})\) polynomial-time in \(m,\tau,L\), or NP-hard under polynomial-time Turing reductions?
In finite games, the two-step value equals the expected modified contribution under uniformly random orders in which each union forms a contiguous block: ordinary internal marginal contributions apply except to the last member, who also receives the union’s external surplus. [Finite representation result](https://www.uv.es/erices/RePEc/WP/2010/0810.pdf).
No result settling this exact polynomial-worth replication-limit evaluation problem was located in the literature search.
All limits exist, are rational, and can be computed exactly in polynomial time in the input bit length. The proof below starts directly from the defining formula for the two-step value, whose finite-game context is discussed in the [supplied paper](https://www.uv.es/erices/RePEc/WP/2010/0810.pdf).
Let \(\mathcal I\) be the set of supported union–type pairs, and write \(\mathcal I_k=\{(k,t)\in\mathcal I\}\). Define the total mass of union \(\displaystyle k\) by \(\displaystyle p_k=\sum_{(k,t)\in\mathcal I_k}\mu_{kt}>0\).
Write the supplied polynomial as
\(\displaystyle V(z)=\sum_{j=1}^{J}c_j\prod_{(k,t)\in\mathcal I}z_{kt}^{\alpha_{j,kt}}\),
after deleting its constant monomials. This deletion preserves the polynomial because their coefficients sum to \(\displaystyle V(0)=0\). Duplicate nonconstant monomials need not be combined.
For each monomial define
\(\displaystyle d_j=\sum_{(k,t)\in\mathcal I}\alpha_{j,kt}>0,\qquad
A_j=\{k:\text{some }\alpha_{j,kt}>0\},\qquad
r_j=|A_j|,\qquad
b_j=c_j\prod_{(k,t)\in\mathcal I}\mu_{kt}^{\alpha_{j,kt}}.\)
Then, for every supported pair, the exact answer is
\(\displaystyle \boxed{ a_{kt} = \sum_{j:A_j=\{k\}} \frac{\alpha_{j,kt}b_j}{d_j\mu_{kt}} + \frac{1}{p_k} \sum_{\substack{j:k\in A_j\\r_j\ge 2}} \frac{b_j}{r_j}. } \)
Empty sums are zero. Thus a monomial involving only one union contributes according to its type exponents; a monomial involving several unions contributes equally per individual within each participating union, with the displayed dependence on union mass.
For a union coalition \(\displaystyle T\subseteq M\), its coordinate vector has coordinate \(\displaystyle \mu_{kt}\) when \(\displaystyle k\in T\), and zero otherwise. Consequently,
\(\displaystyle q_n(T)=q(T):=\sum_{j=1}^{J}b_j\,u_{A_j}(T),\)
where the unanimity game \(\displaystyle u_A\) is defined by \(\displaystyle u_A(T)=1\) if \(\displaystyle A\subseteq T\), and zero otherwise.
To compute its Shapley value, consider a uniformly random order of the unions. A union outside \(\displaystyle A\) always has zero marginal contribution. A union \(\displaystyle k\in A\) has marginal contribution one precisely when it is the last member of \(\displaystyle A\) in that order. Each member of \(\displaystyle A\) has probability \(\displaystyle 1/|A|\) of being last. Therefore,
\(\displaystyle \operatorname{Sh}_k(M,u_A)= \begin{cases} 1/|A|,&k\in A,\\ 0,&k\notin A. \end{cases} \)
The Shapley value is linear because it averages marginal contributions. It follows that
\(\displaystyle \operatorname{Sh}_k(M,q) =\sum_{j:k\in A_j}\frac{b_j}{r_j}. \)
Moreover, evaluating a single union gives
\(\displaystyle v_n(B_k^{(n)})=q(\{k\})=\sum_{j:A_j=\{k\}}b_j.\)
The singleton-support monomials therefore cancel in the external surplus:
\(\displaystyle \operatorname{Sh}_k(M,q)-v_n(B_k^{(n)}) = \sum_{\substack{j:k\in A_j\\r_j\ge2}}\frac{b_j}{r_j}. \)
Since \(\displaystyle |B_k^{(n)}|=np_k\), the scaled external term is exactly
\(\displaystyle n\,\frac{\operatorname{Sh}_k(M,q_n)-v_n(B_k^{(n)})}{|B_k^{(n)}|} = \frac1{p_k} \sum_{\substack{j:k\in A_j\\r_j\ge2}}\frac{b_j}{r_j}, \)
for every admissible replication size.
Fix a supported pair \(\displaystyle (k,t)\), and abbreviate its chosen individual by \(\displaystyle i\). Let \(\displaystyle F_k\) be the polynomial obtained from \(\displaystyle V\) by setting all coordinates outside union \(\displaystyle k\) to zero. Its variables are indexed by \(\displaystyle \mathcal I_k\).
We prove
\(\displaystyle \lim_{\substack{n\to\infty\\D\mid n}} n\,\operatorname{Sh}_i(B_k^{(n)},v_n|_{B_k^{(n)}}) = \int_0^1\partial_{kt}F_k(u\mu^{(k)})\,du, \)
where \(\displaystyle \mu^{(k)}=(\mu_{ks})_{(k,s)\in\mathcal I_k}\).
Assign independent uniform priorities in \(\displaystyle [0,1]\) to the individuals of the union and order them by priority. Ties have probability zero, and symmetry makes the resulting order uniform. Hence the expected marginal contribution of \(\displaystyle i\) is its Shapley value.
Conditional on the priority of \(\displaystyle i\) being \(\displaystyle u\), let \(\displaystyle X_{ks}\) count its predecessors of type \(\displaystyle (k,s)\). These counts are independent binomial random variables with
\(\displaystyle X_{ks}\sim\operatorname{Bin}\bigl(n\mu_{ks}-\mathbf1_{\{s=t\}},u\bigr). \)
Set \(\displaystyle Z_{ks}=X_{ks}/n\), and let \(\displaystyle e_t\) be the unit vector for coordinate \(\displaystyle (k,t)\). The conditional scaled marginal contribution is
\(\displaystyle n\bigl[F_k(Z+e_t/n)-F_k(Z)\bigr] = \int_0^1\partial_{kt}F_k(Z+se_t/n)\,ds, \)
by the fundamental theorem of calculus.
We now give a uniform error bound. Because \(\displaystyle F_k\) is a polynomial, there is a finite constant \(\displaystyle H_k\) bounding the absolute values of all its second partial derivatives on \(\displaystyle [0,1]^{|\mathcal I_k|}\). Thus, for points in that cube,
\(\displaystyle |\partial_{kt}F_k(x)-\partial_{kt}F_k(y)| \le H_k\sum_{(k,s)\in\mathcal I_k}|x_{ks}-y_{ks}|. \)
The binomial mean and variance give
\(\displaystyle \mathbb E[Z_{ks}\mid u] =u\mu_{ks}-\frac{u}{n}\mathbf1_{\{s=t\}}, \qquad \operatorname{Var}(Z_{ks}\mid u)\le\frac{\mu_{ks}}{4n}. \)
Using \(\displaystyle \mathbb E|Y-\mathbb EY|\le\sqrt{\operatorname{Var}(Y)}\), we obtain
\(\displaystyle \mathbb E[|Z_{ks}-u\mu_{ks}|\mid u] \le \frac{\sqrt{\mu_{ks}}}{2\sqrt n} +\frac{\mathbf1_{\{s=t\}}}{n}. \)
Both \(\displaystyle Z+se_t/n\) and \(\displaystyle u\mu^{(k)}\) lie in the stated cube. Therefore, uniformly over \(\displaystyle u,s\in[0,1]\),
\(\displaystyle \left| \mathbb E[\partial_{kt}F_k(Z+se_t/n)\mid u] -\partial_{kt}F_k(u\mu^{(k)}) \right| \le H_k\left( \frac{\sum_{(k,s)\in\mathcal I_k}\sqrt{\mu_{ks}}}{2\sqrt n} +\frac2n \right). \)
Integrating over \(\displaystyle s\) and the uniform priority \(\displaystyle u\) proves the asserted convergence. The bound holds for every admissible \(\displaystyle n\), so it also proves convergence along the multiples of \(\displaystyle D\). No sign assumption on the polynomial was used.
A monomial survives in \(\displaystyle F_k\) precisely when \(\displaystyle A_j=\{k\}\).
For such a monomial, if \(\displaystyle \alpha_{j,kt}>0\), differentiation along the ray gives
\(\displaystyle \partial_{kt} \left(c_j\prod_{(k,s)\in\mathcal I_k}z_{ks}^{\alpha_{j,ks}}\right) \bigg|_{z=u\mu^{(k)}} = \frac{\alpha_{j,kt}b_j}{\mu_{kt}}u^{d_j-1}. \)
Its integral over \(\displaystyle [0,1]\) is \(\displaystyle \alpha_{j,kt}b_j/(d_j\mu_{kt})\). If \(\displaystyle \alpha_{j,kt}=0\), both its derivative and this expression are zero.
Linearity and the finite number of monomials yield
\(\displaystyle \int_0^1\partial_{kt}F_k(u\mu^{(k)})\,du = \sum_{j:A_j=\{k\}} \frac{\alpha_{j,kt}b_j}{d_j\mu_{kt}}. \)
Combining this result with the exact external term proves the boxed formula and existence of every requested limit.
As a consistency check, the formula also gives efficiency:
\(\displaystyle \sum_{(k,t)\in\mathcal I}\mu_{kt}a_{kt}=V(\mu).\)
Indeed, a monomial supported on one union contributes \(\displaystyle b_j\sum_t\alpha_{j,kt}/d_j=b_j\). A monomial supported on several unions contributes \(\displaystyle b_j/r_j\) from each of its \(\displaystyle r_j\) participating unions, again totaling \(\displaystyle b_j\).
The boxed formula gives an explicit algorithm:
It remains to check bit complexity, since polynomially many rational operations alone would not suffice.
The number of listed monomials and the support size are bounded by the input length. Unary exponent encoding also bounds every total degree \(\displaystyle d_j\) by \(\displaystyle L\). Each input rational has numerator and denominator bit lengths at most \(\displaystyle L\).
Writing \(\displaystyle \mu_{kt}=a_{kt}'/b_{kt}'\), an unreduced representation of
\(\displaystyle b_j=c_j\prod_{(k,t)\in\mathcal I}(a_{kt}'/b_{kt}')^{\alpha_{j,kt}}\)
has numerator and denominator bit lengths bounded by \(\displaystyle O((d_j+1)L)=O(L^2)\). Computing these products takes polynomial time because the exponents are unary.
Each \(\displaystyle p_k\) likewise has a polynomial-size rational representation: a common denominator is the product of the denominators of its supported masses. Multiplication or division by \(\displaystyle p_k,\mu_{kt},d_j,r_j\), and multiplication by an exponent preserve polynomial bit length.
Finally, each output coordinate sums at most \(\displaystyle J\) such rational contributions. Using the product of their denominators as a common denominator bounds the resulting numerator and denominator lengths by a polynomial in \(\displaystyle L\). Intermediate lengths satisfy the same bound. Standard integer arithmetic and greatest-common-divisor reduction therefore implement the entire computation in polynomial bit time.
In particular, the algorithm never constructs a replicated population or enumerates union coalitions. Thus exact evaluation is polynomial-time solvable. NP-hardness under polynomial-time Turing reductions would consequently imply \(\displaystyle \mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. All requested limits exist, the displayed formula is correct, and the algorithm computes the entire vector exactly in polynomial bit time under the stated encoding. No major or minor mathematical issues were found.
The proof uses the defining two-step formula directly. It does not rely on the linked finite representation result, so that paper introduces no unverified dependency.
Deleting all constant monomials preserves \(V\): their coefficients sum to \(V(0)=0\). Every remaining monomial has positive total degree \(d_j\), a nonempty union support \(A_j\), and \(r_j\geq1\). Consequently, all subsequent divisions by \(d_j\) and \(r_j\) are valid.
The other denominators are also nonzero: every supported mass \(\mu_{kt}\) is positive, and every union mass \(p_k\) is positive by hypothesis.
Duplicate monomials and negative coefficients cause no problem. The argument evaluates each listed monomial separately and uses linearity.
For every admissible \(n\), the normalized counts of a complete union are exactly its specified masses. Thus the assertion that \(q_n\) is independent of \(n\) is correct.
A nonconstant monomial contributes \(b_j\) to a union coalition precisely when that coalition contains every union in \(A_j\). This verifies the decomposition
\[
q(T)=\sum_j b_j u_{A_j}(T).
\]
The unanimity-game Shapley calculation is correct: an outside union has zero marginal contribution, and a participating union contributes precisely when it appears last among the members of \(A_j\). Uniform ordering gives each participating union probability \(1/r_j\).
Evaluation at the singleton coalition \(\{k\}\) retains exactly the monomials with \(A_j=\{k\}\). Their contributions therefore cancel in the external surplus. Since \(|B_k^{(n)}|=np_k\), the displayed scaled external term is exact for every admissible \(n\).
Setting coordinates outside union \(k\) to zero correctly produces the polynomial governing the restricted game.
Independent uniform priorities induce a uniform permutation because ties have probability zero and all individuals are exchangeable. Taking the expected marginal contribution therefore gives the ordinary Shapley value.
Conditional on the chosen individual's priority \(u\), each other individual precedes it independently with probability \(u\). Hence the stated independent binomial predecessor counts are correct. The subtraction of one individual occurs exactly in the chosen individual's own type.
The fundamental-theorem-of-calculus identity has the correct scaling:
\[
n\bigl[F_k(Z+e_t/n)-F_k(Z)\bigr]
=
\int_0^1\partial_{kt}F_k(Z+se_t/n)\,ds.
\]
All evaluation points belong to the asserted cube. In particular, the chosen type has at most \(n\mu_{kt}-1\) predecessors, so adding at most \(1/n\) to its normalized count keeps that coordinate at most \(\mu_{kt}\leq1\). All other coordinates satisfy the same upper bound without an increment.
A polynomial's second partial derivatives are bounded on this compact cube. The resulting bound on differences of its first derivative is valid.
The conditional means and variance estimates are correct:
\[
\mathbb E[Z_{ks}\mid u]
=
u\mu_{ks}-\frac{u}{n}\mathbf1_{\{s=t\}},
\qquad
\operatorname{Var}(Z_{ks}\mid u)
\leq\frac{\mu_{ks}}{4n}.
\]
The expected absolute-deviation bound follows from the variance bound and the mean displacement. The final \(2/n\) accounts for both exclusion of the chosen individual and the subsequent displacement \(se_t/n\). Its constant is valid uniformly in \(u,s\).
For the fixed input polynomial, this error tends to zero uniformly. Integrating the estimate therefore justifies the claimed limit without any unsupported exchange of limits and expectations. Restricting to multiples of \(D\) preserves convergence.
Exactly the monomials supported on \(\{k\}\) survive in \(F_k\). For a positive exponent in the chosen coordinate, differentiation along the mass ray yields the stated coefficient times \(u^{d_j-1}\). Because \(d_j\geq1\), integration contributes the factor \(1/d_j\).
A zero exponent gives zero derivative and zero contribution in the displayed formula. Thus no division by an exponent or negative-power evaluation is needed in this case.
Adding the internal limit to the already exact external term establishes the boxed expression for every supported pair. All its quantities are rational, so rationality follows as claimed.
The efficiency check is also correct: each monomial contributes its full value \(b_j\) to the mass-weighted sum.
The complexity argument addresses both operation counts and operand lengths.
Under the explicit-list and unary-exponent encoding:
The algorithm distributes each monomial's contribution over at most the supported coordinates, so it also performs polynomially many operations. Standard exact integer arithmetic and rational reduction complete the claimed polynomial bit-time implementation.
The algorithm need not construct the replicated population, enumerate coalitions, or compute \(D\). Large replication denominators therefore do not undermine the complexity conclusion.
The write-up handles the zero polynomial through empty sums, a single union through cancellation of the external surplus, singleton type support, linear monomials, duplicate monomials, and signed coefficients. No positivity of worth is used.
The statement about NP-hardness is appropriately conditional: membership in polynomial time implies that NP-hardness under polynomial-time Turing reductions would imply \(\mathrm P=\mathrm{NP}\).
No additional clarification or repair is required.
⟨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.