d4-conf-atal-2008-0151 (d4-conf-atal-2008-0151)

Given a finite support \(T\), rational masses \(\mu_t>0\) summing to \(1\), positive rational weights \(a_t\), a target type \(t^\star\), and a quota fraction \(\rho\in(0,1)\), consider each admissible population size \(N\) with \(N\mu_t\in\mathbb{Z}\). Set the quota to \(\lceil \rho N\bar a\rceil\), where \(\bar a=\sum_{t\in T}\mu_ta_t\). Let \(\Phi_N\) be the total Shapley–Shubik index of the \(t^\star\) players; let \(\Phi_N^{\mathrm{split}}\) be that total when every such player splits into two identities of weight \(a_{t^\star}/2\). Decide whether \(\liminf_{N\to\infty,\;N\mu_t\in\mathbb{Z}\ \forall t}(\Phi_N^{\mathrm{split}}-\Phi_N)>0\).

A society is given by its support: a nonempty 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 weight \(a_t\). The input also specifies \(t^\star\in T\) and a binary rational \(\rho\in(0,1)\). Let \(L\) be the total input bit length; running times are measured in \(\tau,L\), with no separate \(m\) parameter.
For each sufficiently large integer \(N\) satisfying \(N\mu_t\in\mathbb Z\) for every \(t\), form a weighted voting game with \(N\mu_t\) distinct players of weight \(a_t\), and quota \(q_N=\lceil\rho N\bar a\rceil\), where \(\bar a=\sum_{t\in T}\mu_ta_t\). A coalition wins precisely when its weight is at least \(q_N\).
Let \(\Phi_N\) be the sum of the Shapley–Shubik indices of the type \(t^\star\) players. Simultaneously replace every such player by two distinct identities, each of weight \(a_{t^\star}/2\), keeping \(q_N\) fixed. Let \(\Phi_N^{\mathrm{split}}\) sum the indices of all these replacement identities in the resulting game.

Is deciding whether \(\liminf_{N\to\infty,\;N\mu_t\in\mathbb Z\ \forall t\in T}(\Phi_N^{\mathrm{split}}-\Phi_N)>0\) solvable in polynomial time in \(\tau,L\), or is it NP-hard?

For a finite explicitly listed electorate with binary integer weights and quota, deciding whether one designated player's equal two-way split strictly increases its combined Shapley–Shubik power is NP-hard ([Bachrach–Elkind](https://aamas.csc.liv.ac.uk/Proceedings/aamas08/proceedings/pdf/paper/AAMAS08_0085.pdf)); the [expanded treatment](https://arxiv.org/pdf/1401.3869) retains this result.
On the continuum side, [Neyman](https://pubsonline.informs.org/doi/10.1287/moor.13.4.556) establishes existence of asymptotic values for weighted majority games; that result does not formulate this simultaneous-splitting decision problem.

1. Result

The problem is polynomial-time solvable. Every valid input has answer NO. In fact, both aggregate powers converge, and
\( \lim_N\Phi_N=\lim_N\Phi_N^{\mathrm{split}} =\frac{\mu_{t^\star}a_{t^\star}}{\bar a}. \)
Consequently,
\( \lim_N(\Phi_N^{\mathrm{split}}-\Phi_N)=0. \)

All limits here and below are taken through the admissible integers. This set is unbounded because the masses are rational.

The proof must control individual indices to accuracy \(o(N^{-1})\), since the designated group contains a number of players proportional to \(N\). We establish that control explicitly.

2. An exact integral representation

Assign every player an independent uniform arrival time in \([0,1]\). Their arrival order is a uniformly random permutation: ties have probability zero, and exchangeability gives every permutation equal probability.

Consider a player of weight \(w\), with quota \(Q\). Conditional on its arrival time being \(p\), every other player independently precedes it with probability \(p\). Let \(S_N(p)\) denote their total weight. The player is pivotal exactly when
\( Q-w\leq S_N(p)<Q. \)
Thus its Shapley–Shubik index is
\( \phi_N=\int_0^1 \Pr\!\left(Q-w\leq S_N(p)<Q\right)\,dp. \)

We next estimate the integrated probability of each possible predecessor total.

3. An integrated lattice lemma

Lemma. Fix positive integers \(b_1,\ldots,b_k\) satisfying
\( \gcd(b_1,\ldots,b_k)=1, \)
and positive constants \(c_1,\ldots,c_k\). Suppose the integer multiplicities satisfy
\( n_j(N)=Nc_j+O(1). \)
Define
\( A=\sum_jc_jb_j,\qquad B=\sum_jc_jb_j^2. \)
For each \(p\in[0,1]\), let
\( S_N(p)=\sum_{j=1}^k b_jX_{j,N}(p), \)
where the variables \(X_{j,N}(p)\) are independent and have distributions
\( X_{j,N}(p)\sim\operatorname{Bin}(n_j(N),p). \)

Fix \(\rho\in(0,1)\). For every integer sequence \(z_N\) satisfying
\( z_N=\rho NA+O(1), \)
we have
\( \int_0^1\Pr(S_N(p)=z_N)\,dp =\frac{1}{NA}+o(N^{-1}). \)

All constants in this lemma may depend on the fixed weights and proportions.

3.1. Uniform local approximation

Write
\( M_N=\sum_jn_j(N)b_j=NA+O(1), \qquad V_N=\sum_jn_j(N)b_j^2=NB+O(1). \)
The mean and variance of \(S_N(p)\) are \(pM_N\) and \(p(1-p)V_N\).

For every compact interval \(I\subset(0,1)\), we first prove, uniformly over \(p\in I\) and \(z\in\mathbb Z\),
\( \Pr(S_N(p)=z) = G_N(p,z)+O(N^{-1}), \)
where
\( G_N(p,z)= \frac{1}{\sqrt{2\pi p(1-p)V_N}} \exp\!\left(-\frac{(z-pM_N)^2}{2p(1-p)V_N}\right). \)

Let
\( F_N(\theta,p)= \mathbb E\exp\!\left(i\theta(S_N(p)-pM_N)\right). \)
For one Bernoulli contribution,
\( \left|\mathbb E e^{i\theta b_j(X-p)}\right|^2 = 1-4p(1-p)\sin^2(b_j\theta/2). \)

Choose a sufficiently small fixed \(\delta>0\). For \(|\theta|\leq\delta\), continuous logarithms of these characteristic functions exist, and Taylor expansion gives
\( \log F_N(\theta,p) = -\frac12p(1-p)V_N\theta^2+R_N(\theta,p), \qquad |R_N(\theta,p)|\leq CN|\theta|^3. \)
Uniformity follows because \(I\) is compact, the weights are fixed, and there are \(O(N)\) independent contributions.

The modulus identity also gives
\( \operatorname{Re}\log F_N(\theta,p)\leq-cN\theta^2 \)
on this interval. Indeed, for sufficiently small \(\delta\), each \(\sin^2(b_j\theta/2)\) is bounded below by a positive constant times \(b_j^2\theta^2\); also \(p(1-p)\) is bounded below on \(I\).

Both logarithms therefore have real parts bounded above by a negative constant times \(N\theta^2\). Using
\( e^x-e^y=(x-y)\int_0^1e^{(1-s)y+sx}\,ds, \)
we obtain
\( \left|F_N(\theta,p) -e^{-p(1-p)V_N\theta^2/2}\right| \leq CN|\theta|^3e^{-c'N\theta^2}. \)
Its integral over \([-\delta,\delta]\) is \(O(N^{-1})\), since
\( N\int_{\mathbb R}|\theta|^3e^{-c'N\theta^2}\,d\theta =O(N^{-1}). \)

On \(\delta\leq|\theta|\leq\pi\), the function
\( \sum_jc_j\sin^2(b_j\theta/2) \)
has a strictly positive minimum. To verify this, simultaneous vanishing would require \(b_j\theta\in2\pi\mathbb Z\) for every \(j\). Bézout’s identity and the greatest-common-divisor assumption would then imply \(\theta\in2\pi\mathbb Z\), impossible on this compact set. Since \(n_j(N)\geq Nc_j/2\) for sufficiently large \(N\), the modulus identity consequently yields
\( |F_N(\theta,p)|\leq e^{-c''N}. \)

Finally, Fourier inversion gives
\( \Pr(S_N(p)=z) = \frac{1}{2\pi}\int_{-\pi}^{\pi} e^{-i\theta(z-pM_N)}F_N(\theta,p)\,d\theta. \)
The inverse Fourier transform over \(\mathbb R\) of
\( e^{-p(1-p)V_N\theta^2/2} \)
is \(G_N(p,z)\). Its integral outside \([-\delta,\delta]\) is exponentially small. The preceding bounds prove the claimed uniform \(O(N^{-1})\) approximation.

3.2. Integrating the local approximation

Set
\( J_N=[\rho-N^{-2/5},\,\rho+N^{-2/5}]. \)
For sufficiently large \(N\), this interval lies inside a fixed compact subinterval of \((0,1)\).

Outside \(J_N\),
\( |z_N-pM_N| = |NA(\rho-p)+O(1)| \geq \frac A2N^{3/5}. \)
The sum \(S_N(p)\) consists of independent variables with ranges of lengths \(b_j\); the sum of their squared range lengths is \(V_N=O(N)\). Hoeffding’s inequality therefore gives
\( \Pr(S_N(p)=z_N) \leq 2\exp\!\left(-\frac{2(z_N-pM_N)^2}{V_N}\right) \leq 2e^{-cN^{1/5}}. \)
Hence the integral outside \(J_N\) is \(o(N^{-1})\).

Inside \(J_N\), the integrated error in the local approximation is
\( O(N^{-1}|J_N|)=O(N^{-7/5})=o(N^{-1}). \)

It remains to integrate \(G_N\). Put
\( p_N=z_N/M_N=\rho+O(N^{-1}), \qquad p=p_N+u/\sqrt N. \)
Then \(z_N-pM_N=-uM_N/\sqrt N\). The transformed integration intervals tend to all of \(\mathbb R\), because their endpoints are asymptotic to \(\pm N^{1/10}\).

Since
\( M_N/N\longrightarrow A,\qquad V_N/N\longrightarrow B, \)
the transformed integrand for \(N\int_{J_N}G_N(p,z_N)\,dp\) converges pointwise to
\( \frac{1}{\sqrt{2\pi\rho(1-\rho)B}} \exp\!\left(-\frac{A^2u^2}{2\rho(1-\rho)B}\right). \)
On the transformed intervals it is bounded by \(Ce^{-cu^2}\): \(p\) stays in a compact subinterval of \((0,1)\), and \(M_N^2/(NV_N)\) stays bounded away from zero. Extending it by zero elsewhere, dominated convergence therefore applies. It yields
\( \lim_N N\int_{J_N}G_N(p,z_N)\,dp = \frac{1}{\sqrt{2\pi\rho(1-\rho)B}} \int_{\mathbb R} e^{-A^2u^2/(2\rho(1-\rho)B)}\,du =\frac1A. \)

Combining the central integral, its approximation error, and the tail bound proves the lemma.

4. Replicated types have power proportional to weight

We now deduce a general consequence that permits the number of identities to change.

Suppose category \(j\) contains \(Nc_j\) players of fixed positive rational weight \(w_j\), where every \(c_j\) is a positive rational. The proportions need not sum to one. Let
\( W=\sum_jc_jw_j, \)
and suppose the quota satisfies
\( Q_N=\rho NW+O(1), \qquad 0<\rho<1. \)

Claim. Every player in category \(j\) has index
\( \phi_{j,N}=\frac{w_j}{NW}+o(N^{-1}), \)
so that category’s aggregate power converges to
\( \frac{c_jw_j}{W}. \)

Proof. Because the weights are positive rationals, there is a positive rational \(h\) such that
\( b_j=w_j/h\in\mathbb Z_{>0}, \qquad \gcd(b_1,\ldots,b_k)=1. \)
For example, clear the denominators and then divide the resulting integers by their greatest common divisor. Scaling weights and quota by \(1/h\) leaves the game unchanged.

Write
\( R_N=Q_N/h,\qquad A=W/h=\sum_jc_jb_j. \)
Thus
\( R_N=\rho NA+O(1). \)

Fix one category-\(j\) player. After excluding that player, the predecessor multiplicities are \(Nc_\ell\), except that category \(j\) has multiplicity \(Nc_j-1\). These satisfy every hypothesis of the lemma.

The predecessor total \(S_N(p)\), in scaled units, is integer-valued. The pivotal interval
\( R_N-b_j\leq S_N(p)<R_N \)
contains exactly the \(b_j\) integers
\( \lceil R_N\rceil-b_j,\, \lceil R_N\rceil-b_j+1,\, \ldots,\, \lceil R_N\rceil-1. \)
Every one of these integer sequences equals \(\rho NA+O(1)\). Applying the lemma to each, and using the integral representation, gives
\( \phi_{j,N} = \frac{b_j}{NA}+o(N^{-1}) = \frac{w_j}{NW}+o(N^{-1}). \)
There are only \(b_j\) terms, and \(b_j\) is fixed as \(N\) grows.

Players within a category have equal indices by permutation symmetry. Multiplying by their number \(Nc_j\) proves the aggregate limit. This also shows explicitly why lattice effects and quota rounding do not alter that limit.

5. Applying the claim before and after splitting

Before splitting, take
\( c_t=\mu_t,\qquad w_t=a_t. \)
Then \(W=\bar a\), and
\( q_N=\lceil\rho N\bar a\rceil=\rho N\bar a+O(1). \)
Therefore
\( \lim_N\Phi_N = \frac{\mu_{t^\star}a_{t^\star}}{\bar a}. \)

After splitting, use the categories
\( c_t'=\mu_t,\quad w_t'=a_t \quad(t\ne t^\star), \)
and
\( c_{t^\star}'=2\mu_{t^\star}, \qquad w_{t^\star}'=a_{t^\star}/2. \)
Their total weight per unit \(N\) remains
\( W' = \sum_{t\ne t^\star}\mu_ta_t + 2\mu_{t^\star}(a_{t^\star}/2) =\bar a. \)
The quota is unchanged and thus satisfies the same required asymptotic relation. The claim applies even though the category proportions now sum to \(1+\mu_{t^\star}\). It gives
\( \lim_N\Phi_N^{\mathrm{split}} = \frac{2\mu_{t^\star}(a_{t^\star}/2)}{\bar a} = \frac{\mu_{t^\star}a_{t^\star}}{\bar a}. \)

Subtracting these convergent sequences establishes
\( \liminf_N(\Phi_N^{\mathrm{split}}-\Phi_N)=0. \)

6. Complexity and the finite-electorate result

The algorithm returns NO on every valid input. Its decision step is constant time; reading or validating the input takes polynomial time in \(\tau,L\). No bound on how quickly the asymptotic estimates converge is needed.

This conclusion is compatible with the finite-electorate hardness result: [Theorem 12 of the expanded treatment](https://arxiv.org/pdf/1401.3869) concerns whether an equal split increases power in a particular finite game. Here the predicate requires a strictly positive limiting aggregate gain under replication.

[Neyman’s asymptotic-value result](https://pubsonline.informs.org/doi/10.1287/moor.13.4.556) supplies relevant continuum context, but the proof above establishes the required replicated-type limits directly.

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The output resolves the stated decision problem. The lattice lemma is valid, its hypotheses hold before and after simultaneous splitting, and the resulting aggregate limits coincide. I found no major or minor mathematical gaps.

1. Scope and quantifiers

The proof fixes an arbitrary valid input and takes limits through the admissible integers. This matches the task: the society, weights, and quota fraction remain fixed while \(N\) increases.

Rationality of the masses ensures an unbounded admissible sequence. All asymptotic constants may depend on the fixed input. This dependence is compatible with the complexity conclusion because the algorithm does not compute a convergence threshold or approximate finite-electorate indices.

The claimed equality of both aggregate limits is stronger than the required assertion that the limiting inferior of their difference is not positive.

2. Exact integral representation

The arrival-time representation is correct:

• Independent continuous uniform arrival times induce a uniformly random permutation.
• Conditional on the designated player arriving at time \(p\), the other players precede it independently with probability \(p\).
• For a player of weight \(w\), pivotality is exactly \(Q-w\leq S_N(p)<Q\). Both endpoint conventions agree with the winning rule “weight at least \(Q\).”
• Integrating the conditional pivotality probability over \(p\) gives its Shapley–Shubik index.

No approximation enters this representation.

3. Integrated lattice lemma: local approximation

The definitions of \(M_N\) and \(V_N\), and the formulas for the mean and variance, are correct. The multiplicity assumptions give \(M_N=NA+O(1)\) and \(V_N=NB+O(1)\), with \(A,B>0\).

The characteristic-function argument is valid at every substantive step:

• The squared modulus formula for a centered Bernoulli contribution is correct; centering does not change its modulus.
• A sufficiently small fixed neighborhood of zero admits continuous logarithms. Since the weights are fixed and \(p\) ranges over a compact subset of \((0,1)\), the Taylor remainder is uniformly bounded by \(CN|\theta|^3\).
• The modulus identity gives a uniform bound of the form \(\operatorname{Re}\log F_N\leq-cN\theta^2\). The Gaussian exponent satisfies the same kind of bound.
• The stated exponential interpolation identity applies to the complex logarithms. It therefore gives the asserted error bound \(CN|\theta|^3e^{-c'N\theta^2}\).
• The integral of this bound is \(O(N^{-1})\), as claimed.
• Away from zero, the greatest-common-divisor condition excludes simultaneous vanishing of all sine terms. Bézout’s identity justifies this exclusion, including the endpoints of the Fourier interval.
• Positivity of every \(c_j\) ensures that each weight category supplies linearly many contributions for sufficiently large \(N\). Consequently, the characteristic function is exponentially small on the remaining compact region.
• Integer-valued Fourier inversion and the Gaussian Fourier transform give the displayed local approximation.

Uniformity in the integer \(z\) is justified: its only appearance in the inversion error is through a factor of modulus one.

4. Integrated lattice lemma: integration and tails

The localization and all exponents are correct.

Outside \(J_N\), the displacement from the mean is at least \((A/2)N^{3/5}\) for sufficiently large \(N\). This follows uniformly from the stated bounded errors and \(|p-\rho|\geq N^{-2/5}\).

Hoeffding’s inequality is applied to independent bounded Bernoulli contributions. Their squared range lengths sum to \(V_N\), exactly as required. The resulting exponent has order \(N^{1/5}\), so the integrated tail is \(o(N^{-1})\). This argument also covers \(p=0\) and \(p=1\).

Inside \(J_N\), integrating the uniform \(O(N^{-1})\) local error over an interval of length \(2N^{-2/5}\) gives \(O(N^{-7/5})\).

For the Gaussian integral:

• \(p_N=z_N/M_N=\rho+O(N^{-1})\) is correct.
• The substitution \(p=p_N+u/\sqrt N\) produces the displayed limiting integrand, including its normalization.
• The transformed endpoints diverge with magnitude \(N^{1/10}\).
• The claimed dominating function \(Ce^{-cu^2}\) follows from compactness of the \(p\)-range and positivity of the limiting constants.
• Extending the integrand by zero permits dominated convergence on the fixed domain \(\mathbb R\).
• The final Gaussian integral equals \(1/A\).

Thus the lemma establishes the required \(1/(NA)+o(N^{-1})\) estimate. In particular, its integrated error is sufficiently small for subsequent aggregation.

5. Application to replicated categories

The rational lattice normalization is valid. A common denominator followed by division by the integer greatest common divisor produces a positive rational \(h\) and positive integer weights \(b_j=w_j/h\) with greatest common divisor one.

Scaling the quota by the same factor preserves every coalition’s winning status. The scaled quota need not be integral, and the proof correctly accommodates this.

Removing one designated player changes its category multiplicity by one, so every multiplicity still has the lemma’s required form. The leading total-weight parameter remains \(A=W/h\).

The half-open pivotal interval contains exactly the listed \(b_j\) integers, whether or not \(R_N\) is integral. Every listed integer sequence satisfies the lemma’s localization assumption. Since \(b_j\) is fixed as \(N\) grows, summing the estimates preserves the \(o(N^{-1})\) error.

Permutation symmetry makes all players in a category have the same index. Multiplication by \(Nc_j\) therefore gives the claimed aggregate limit. No uniformity over an increasing collection of individual errors is needed.

6. Simultaneous splitting and edge cases

Both applications satisfy the general claim’s hypotheses.

Before splitting, \(W=\bar a\), and quota rounding contributes a bounded error.

After splitting, the designated category has multiplicity \(2N\mu_{t^\star}\) and weight \(a_{t^\star}/2\). These multiplicities are integral along the original admissible sequence, and total weight remains \(N\bar a\). The unchanged quota therefore retains the required asymptotic relation.

The category proportions need not sum to one in the general claim, so the increased number of identities causes no mismatch. Coincident category weights are also harmless: neither independence nor the greatest-common-divisor argument requires distinct weights.

The proof covers support size one. Positivity of the weights and \(0<\rho<1\) ensure that quotas lie strictly between zero and total weight for sufficiently large \(N\).

Both aggregate powers consequently converge to \(\mu_{t^\star}a_{t^\star}/\bar a\). Subtracting their convergent sequences proves that the limiting inferior in the task is zero.

7. Complexity and cited context

Returning NO on every valid input correctly decides the predicate. Reading and validating binary rational input takes polynomial time; no electorate expansion, lattice computation, or numerical limit estimation is required.

The finite-electorate comparison is accurately described: [Theorem 12 of the expanded treatment](https://arxiv.org/pdf/1401.3869) states hardness even for equal two-way splitting. It concerns a finite game, so it does not contradict the proved replication limit.

Neyman’s result is contextual rather than an invoked premise. The output supplies its own asymptotic argument, so no unverified application of that theorem supports the conclusion.

Required repair or clarification: none.

⟨structured verdict parsed — rendered above⟩