Answer: Polynomial-time solvable (\(\mathrm{P}\)); merging is beneficial exactly when \(q<1-A_S+A_S^2\).
Proposition 6.4 — class: hardness
Given a finite type set \(T\), positive rational masses \(\mu_t\) summing to \(1\), positive rational per-capita weights \(a_t\) normalized by \(\sum_{t\in T}\mu_ta_t=1\), a quota fraction \(q\in(1/2,1)\), and a cohort \(S\subset T\) with \(0<A_S<1\), where \(A_S=\sum_{t\in S}\mu_ta_t\), consider replication games with \(N\mu_t\) voters of type \(t\), each of weight \(a_t/N\). Determine whether, in the limit along replication sizes with integral \(N\mu_t\), the Shapley–Shubik index of the bloc formed by merging every voter in \(S\) exceeds the pre-merge sum of Shapley–Shubik indices of those voters. The pre-merge limit is \(\alpha_S=\sum_{t\in S}\mu_t\); the post-merge limit is \(\bigl(\min(q,1-A_S)-\max(0,q-A_S)\bigr)/(1-A_S)\).
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. Each type has a positive binary-rational per-capita weight \(a_t\), with \(\sum_{t\in T}\mu_ta_t=1\).
The input also contains a binary-rational quota \(q\in(1/2,1)\) and a specified cohort \(S\subset T\), with \(0<A_S<1\), where \(A_S=\sum_{t\in S}\mu_ta_t\). Let \(L\) be the total input bit length; running times are measured in \(\tau\) and \(L\), with no candidate parameter \(m\) in this model.
For each positive integer \(N\) satisfying \(N\mu_t\in\mathbb Z\) for every type, let \(G_N\) be the weighted voting game with \(N\mu_t\) voters of type \(t\), each of weight \(a_t/N\), and quota \(q\); meeting the quota is winning.
Let \(C_N\) contain every voter whose type belongs to \(S\). Form \(G_N^S\) by replacing \(C_N\) with one bloc \(b\) of weight \(A_S\), retaining all other voters and the quota. Write \(\phi_i(G)\) for the standard Shapley–Shubik index.
Continuous beneficial merging asks whether \(\lim_{N\to\infty}\phi_b(G_N^S)>\lim_{N\to\infty}\sum_{i\in C_N}\phi_i(G_N)\), taking both limits along the admissible replication sizes; equality is a negative instance.
Is continuous beneficial merging solvable in polynomial time in \(\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite weighted voting games, beneficial Shapley–Shubik merging is [\(\mathrm{NP}\)-hard](https://arxiv.org/pdf/1401.3869), and subsequently was shown [\(\mathrm{PP}\)-complete even for two equal-weight merging players](https://arxiv.org/pdf/1303.1691). [Shapiro–Shapley](https://pubsonline.informs.org/doi/10.1287/moor.3.1.1) establish limiting values for fixed players when other voting weight is fragmented into vanishing pieces; this is a limit theorem rather than a complexity classification of the support-encoded decision problem.
Continuous beneficial merging is solvable in polynomial time in \(\tau,L\). More precisely, it is beneficial exactly when
\[
q<1-A_S+A_S^2.
\]
We prove both limits and then give an exact arithmetic algorithm. Throughout, write \(A=A_S\) and \(B=1-A\); by hypothesis, \(A,B>0\). All limits below are along admissible replication sizes.
For a weighted voting game, the Shapley–Shubik index of a voter is the probability that this voter is pivotal in a uniformly random permutation: the preceding voters are losing, and adding this voter makes them winning.
We use the following established theorem, in its normalized form.
Neyman’s approximation theorem. For every \(\varepsilon>0\), there exists \(K_\varepsilon>0\) such that a finite weighted voting game with nonnegative weights \(w_i\), total weight \(1\), and quota \(r\) satisfies
\[
\sum_i|\phi_i-w_i|<\varepsilon
\]
whenever
\[
K_\varepsilon\max_i w_i\le r\le1-K_\varepsilon\max_i w_i.
\]
The winning convention is that meeting the quota suffices. This statement appears as Proposition 3 in [Neyman and Smorodinsky, *Asymptotic Values of Vector Measure Games*](https://www.researchgate.net/publication/5101152_Asymptotic_Values_of_Vector_Measure_Games).
In \(G_N\), the total weight is exactly
\[
\sum_{t\in T}(N\mu_t)\frac{a_t}{N}
=\sum_{t\in T}\mu_ta_t=1.
\]
Moreover,
\[
\max_i w_i=\frac{\max_{t\in T}a_t}{N}\longrightarrow0.
\]
For each fixed \(\varepsilon>0\), the theorem’s quota inequalities therefore hold for all sufficiently large admissible \(N\), because \(q\) and \(1-q\) are positive constants. Consequently,
\[
\sum_i|\phi_i(G_N)-w_i|\longrightarrow0.
\]
The total weight of \(C_N\) is exactly \(A\). Hence the triangle inequality gives
\[
\left|\sum_{i\in C_N}\phi_i(G_N)-A\right|
\le\sum_i|\phi_i(G_N)-w_i|\longrightarrow0.
\]
Thus
\[
\boxed{\lim_{N\to\infty}\sum_{i\in C_N}\phi_i(G_N)=A.}
\]
This is a weight share; unequal per-capita weights need not give the cohort’s population share.
Assign every player in \(G_N^S\) an independent uniform arrival time in \([0,1]\). Ordering by these times generates a uniformly random permutation, since ties have probability zero and every ordering is equally likely.
Let \(U\) be the bloc’s arrival time. Conditional on \(U=u\), each outside voter independently precedes the bloc with probability \(u\). Let \(V_N(u)\) denote their total preceding weight. The bloc is pivotal precisely when
\[
q-A\le V_N(u)<q.
\]
Therefore
\[
\phi_b(G_N^S)
=\int_0^1\Pr\bigl(q-A\le V_N(u)<q\bigr)\,du.
\]
The expectation and variance are
\[
\mathbb E[V_N(u)]=uB
\]
and
\[
\operatorname{Var}(V_N(u))
=u(1-u)\sum_{t\notin S}(N\mu_t)\left(\frac{a_t}{N}\right)^2
=\frac{u(1-u)}{N}\sum_{t\notin S}\mu_ta_t^2.
\]
The final sum is finite for the fixed input. Chebyshev’s inequality consequently implies that \(V_N(u)\) converges in probability to \(uB\).
Except at the at most two values of \(u\) satisfying \(uB=q-A\) or \(uB=q\), this yields
\[
\Pr\bigl(q-A\le V_N(u)<q\bigr)
\longrightarrow
\mathbf 1_{\{q-A<uB<q\}}.
\]
Indeed, away from those boundaries, sufficiently small deviations from \(uB\) preserve membership or nonmembership in the interval.
The integrands are bounded by \(1\). Dominated convergence therefore gives
\[
\lim_{N\to\infty}\phi_b(G_N^S)
=\operatorname{length}\{u\in[0,1]:q-A<uB<q\}.
\]
The interval has positive length: its upper endpoint before truncation is positive, its lower endpoint is less than \(1\) because \(q<1\), and their difference is \(A/B>0\). Thus the limit equals
\[
F_q(A)=
\min\left\{1,\frac{q}{1-A}\right\}
-\max\left\{0,\frac{q-A}{1-A}\right\}.
\]
Since \(q>1/2\), the thresholds satisfy \(1-q<q\). Evaluating the truncations gives
\[
F_q(A)=
\begin{cases}
\dfrac{A}{1-A},&0<A\le1-q,\\[4pt]
\dfrac{1-q}{1-A},&1-q<A<q,\\[4pt]
1,&q\le A<1.
\end{cases}
\]
By Sections 2–3, merging is beneficial exactly when \(F_q(A)>A\).
Case 1: \(0<A\le1-q\). Here
\[
F_q(A)-A=\frac{A^2}{1-A}>0.
\]
Also,
\[
q\le1-A<1-A+A^2,
\]
so the claimed criterion holds.
Case 2: \(1-q<A<q\). Here
\[
F_q(A)-A
=\frac{1-q-A(1-A)}{1-A}.
\]
The denominator is positive. Therefore
\[
F_q(A)>A
\quad\Longleftrightarrow\quad
q<1-A+A^2.
\]
Case 3: \(q\le A<1\). Here \(F_q(A)-A=1-A>0\). Moreover,
\[
1-A+A^2-A=(1-A)^2>0,
\]
so again \(q\le A<1-A+A^2\).
These cases exhaust the hypotheses, proving
\[
\boxed{\text{Merging is beneficial}\quad\Longleftrightarrow\quad q<1-A_S+A_S^2.}
\]
Equality is handled exactly. If \(q=1-A+A^2\), then
\[
q-(1-A)=A^2>0,\qquad q-A=(1-A)^2>0.
\]
Hence this equality lies in Case 2, where \(F_q(A)=A\), and is a negative instance.
Compute \(A_S=\sum_{t\in S}\mu_ta_t\) and test the proved strict inequality using exact rational arithmetic.
For an explicit bit bound, let \(D\) be the product of all input denominators occurring in the masses, per-capita weights, and quota. Its binary length is \(O(L)\). Each denominator of a product \(\mu_ta_t\) divides \(D\), so one can compute integers \(P,Q\) with
\[
A_S=\frac{P}{D},\qquad q=\frac{Q}{D}.
\]
The decision becomes the integer comparison
\[
QD<D^2-PD+P^2.
\]
Because \(0<P<D\) and \(0<Q<D\), all integers in this comparison have \(O(L)\) bits. Constructing \(D,P,Q\) requires \(O(\tau)\) arithmetic operations on integers of polynomial bit length. Standard integer arithmetic therefore gives polynomial running time in \(\tau,L\).
The algorithm never constructs a replicated game or computes a finite-game power index.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned problem. It establishes both limits, derives the exact strict comparison, and gives a polynomial-time algorithm in \(\tau,L\). No major or minor mathematical issues were found.
The notation \(A=A_S\), \(B=1-A\) satisfies \(0<A,B<1\), as required throughout the argument. In particular, every division by \(B\) is valid.
Rational masses ensure an unbounded set of admissible replication sizes. Restricting the limits to those sizes causes no problem: all convergence estimates in the write-up hold for every sufficiently large admissible \(N\).
The cited theorem is stated correctly and applies. Proposition 3 of [Neyman and Smorodinsky, *Asymptotic Values of Vector Measure Games*](https://www.researchgate.net/publication/5101152_Asymptotic_Values_of_Vector_Measure_Games) gives the asserted approximation by normalized weights under the displayed quota conditions. The source uses the convention that meeting the quota is winning.
The proof correctly verifies its hypotheses:
Thus, for each fixed approximation tolerance, the theorem applies eventually. This establishes convergence of the total absolute error to zero.
The cohort’s total weight is exactly \(A\). The displayed triangle inequality therefore correctly establishes
\(\lim_{N\to\infty}\sum_{i\in C_N}\phi_i(G_N)=A\).
No uniform convergence rate in the input is needed: the eventual algorithm computes an exact criterion rather than approximating these limits.
The independent uniform arrival-time representation correctly generates a uniform random permutation.
Conditional on the bloc’s time \(u\), the outside voters’ precedence indicators are independent Bernoulli variables with parameter \(u\). The pivotal event is exactly \(q-A\le V_N(u)<q\): the lower endpoint includes equality, and the upper endpoint excludes it, consistently with the winning convention.
Both moment calculations are correct. In particular, the variance is
\(\frac{u(1-u)}{N}\sum_{t\notin S}\mu_ta_t^2\).
The sum is finite for each fixed input, so Chebyshev’s inequality gives the claimed convergence in probability.
Away from the two possible threshold times, membership in the pivotal interval is preserved by sufficiently small deviations from \(uB\). Hence the claimed probability convergence holds almost everywhere.
Dominated convergence applies: the integrands are measurable probabilities, bounded by the integrable constant \(1\), on the fixed interval \([0,1]\). The exceptional threshold times have measure zero, including when they coincide with an endpoint.
The resulting interval-length expression and its three cases are correct. The values agree at both transition points \(A=1-q\) and \(A=q\).
Every case calculation is valid:
These cases exhaust the domain.
The equality analysis is also correct. If \(q=1-A+A^2\), the two displayed positive differences place \(A\) strictly in the middle case, where the limiting powers coincide. Equality is therefore correctly rejected.
The denominator argument is sound. The product \(D\) includes every denominator occurrence, so each product denominator for \(\mu_ta_t\) divides \(D\), including repeated factors.
Its binary length is \(O(L)\). The exact representations \(A=P/D\) and \(q=Q/D\) consequently exist, and clearing the positive denominator gives the correct comparison:
\(QD<D^2-PD+P^2\).
The promised bounds \(0<A,q<1\) imply \(0<P,Q<D\). All comparison operands have \(O(L)\) bits, and the construction uses \(O(\tau)\) arithmetic operations on integers of polynomial bit length. The polynomial-time conclusion follows.
None. The write-up needs no additional mathematical clarification or repair to establish its claim.
⟨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.