d4-journals-scw-2002-0033 (d4-journals-scw-2002-0033)

Given rational masses \(\mu_t\) of voting-mandate types, per-member weights \(w_t\), and a bloc comprising positive masses \(\sigma_t\) from two types, replicate the types in regular finite societies with exact counts and weighted-majority quotas at half the total weight. For type-symmetric internal weighted-majority rules with rational per-type weights \(v_t\), decide whether some \(v\) makes every bloc type’s limiting absolute Banzhaf influence \(\lim_{N\to\infty}\sqrt{N}\,\beta'_a[W_N\parallel W_{S,N}]\) at least its separate baseline \(\lim_{N\to\infty}\sqrt{N}\,\beta'_a[W_N]\), and whether strict gains are possible, restricting to sequences for which these limits exist.

A society is given by its support: a list of \(\tau\) voting-mandate types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not possible types. Each type has a nonnegative rational per-member weight \(w_t\), with \(\sum_t\mu_tw_t>0\). There are \(m=2\) voting alternatives, yes and no; let \(L\) be the total input bit length.
A prescribed bloc has rational masses \(0\leq\sigma_t\leq\mu_t\), positive for exactly two types \(i,j\). Let \(D\) be the least common multiple of the denominators of all masses. For every \(N=kD\), society \(W_N\) contains exactly \(N\mu_t\) members of type \(t\), of whom \(N\sigma_t\) belong to \(S_N\). Its quota is \(q_N=\tfrac N2\sum_t\mu_tw_t\), and equality with the quota passes.
Choose fixed rational internal weights \(v_i,v_j\geq0\), independent of \(N\), with \(\sigma_iv_i+\sigma_jv_j>0\). The internal rule \(W_{S,N}(v)\) assigns each bloc member its type's internal weight and passes at quota \(\tfrac N2(\sigma_iv_i+\sigma_jv_j)\), including equality.
In the composite rule \(W_N\parallel W_{S,N}(v)\), all bloc mandates vote yes exactly when the internal rule passes; outsiders retain their original votes and weights, and the external quota remains \(q_N\).
Use absolute Banzhaf influence \(\beta'_a\). For a representative bloc member \(a_{t,N}\) of type \(t\), define \(b_t=\lim_{k\to\infty}\sqrt{kD}\,\beta'_{a_{t,kD}}[W_{kD}]\) and \(c_t(v)=\lim_{k\to\infty}\sqrt{kD}\,\beta'_{a_{t,kD}}[W_{kD}\parallel W_{S,kD}(v)]\). Inputs are promised to have finite baseline limits; only internal weights with finite composite limits are admissible.
Feasibility means \(c_t(v)\geq b_t\) for both \(t\in\{i,j\}\); expediency means \(c_t(v)>b_t\) for both.

Is deciding the existence of an admissible feasible internal rule in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? Separately, is deciding the existence of an admissible expedient internal rule in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L\).

For two individual voters in any finite simple voting game, a bloc is never expedient and is feasible exactly when their absolute Banzhaf influences are equal or one is a dummy ([Felsenthal–Machover](https://www.lse.ac.uk/cpnss/assets/documents/voting-power-and-procedures/publications/2002/felsanthal.pdf)).
Asymptotic alliance results also exist for blocs whose weight remains a small fraction of total weight ([Feix–Lepelley–Merlin–Rouet](https://link.springer.com/article/10.1007/s00355-006-0171-6)); no result settling these exact replication decision problems was located.

1. Result and notation. Both decision problems are in \(\mathrm{P}\). Every valid instance admits an admissible feasible internal rule. An admissible expedient rule exists exactly when there is positive original voting weight both inside and outside the bloc.

Extend \(\sigma_t\) by zero for types outside \(\{i,j\}\), and define

\(\displaystyle A=\sum_t\mu_tw_t^2,\qquad B=\sigma_iw_i+\sigma_jw_j,\qquad C=\sigma_iw_i^2+\sigma_jw_j^2,\qquad R=\sum_t(\mu_t-\sigma_t)w_t^2=A-C.\)

The hypotheses imply \(A>0\), while \(B,C,R\geq0\). The expediency criterion is therefore

\(\displaystyle B>0\quad\text{and}\quad R>0.\)

For the prescribed \(m=2\), both decisions and the construction of rational witnessing weights take \(O(\tau L^2)\) bit operations using elementary exact arithmetic. The dependence on \(m\) is constant here; no claim about other values of \(m\) is needed.

The proof below establishes the limits directly, including the effect of ties.

2. A replication-limit lemma. We use the standard absolute Banzhaf influence: the probability that changing a voter’s vote changes the outcome when every other voter votes yes independently with probability \(1/2\).

Consider finitely many types with fixed positive rational masses \(p_s\) and nonnegative rational weights \(u_s\). Their masses need not sum to one. Suppose

\(\displaystyle Q=\sum_s p_su_s^2>0.\)

For each admissible replication size \(N\), give type \(s\) exactly \(Np_s\) voters and use quota \(\frac N2\sum_s p_su_s\), including equality. Then a representative type-\(r\) voter has influence satisfying

\(\displaystyle \lim_{N\to\infty}\sqrt N\,\beta'_r=\sqrt{\frac2\pi}\,\frac{u_r}{\sqrt Q}.\)

Here and below, limits run through the replication sizes for which the counts are integers.

*Proof.* If \(u_r=0\), the voter is a dummy, so the assertion holds. Assume \(u_r>0\).

Multiplying every weight and the quota by the same positive rational number preserves the rule. Clear denominators and divide by the greatest common divisor of the positive integer weights. Thus we may work with integer weights \(a_s\) whose positive entries have greatest common divisor one. Put

\(\displaystyle Q_*=\sum_s p_sa_s^2,\qquad q_N^*=\frac N2\sum_s p_sa_s.\)

Remove the representative voter, and let \(X_N\) be the remaining yes-weight. For positive-weight types, write

\(\displaystyle n_s=Np_s-\mathbf1_{\{s=r\}}.\)

The mean of \(X_N\) is \(M_N=q_N^*-a_r/2\). Fourier inversion gives, for every integer \(z\),

\(\displaystyle \Pr(X_N=z)=\frac1{2\pi}\int_{-\pi}^{\pi}e^{-i\theta(z-M_N)}\Phi_N(\theta)\,d\theta,\qquad \Phi_N(\theta)=\prod_{s:a_s>0}\cos(a_s\theta/2)^{n_s}.\)

We establish the central local estimate

\(\displaystyle \sqrt N\,\Pr(X_N=z_N)\longrightarrow\sqrt{\frac2{\pi Q_*}} \quad\text{whenever }|z_N-M_N|\text{ is bounded}. \)

First, all factors \(|\cos(a_s\theta/2)|\) equal one only if \(a_s\theta\) is an integer multiple of \(2\pi\) for every positive-weight type. The greatest-common-divisor condition then implies that \(\theta\) is a multiple of \(2\pi\). Consequently, on any closed subset of \([-\pi,\pi]\) excluding zero, there is a constant \(\rho<1\) such that

\(\displaystyle |\Phi_N(\theta)|\leq\rho^N\)

for all sufficiently large \(N\). To see the uniform bound, use \(n_s\geq Np_s/2\) and take the maximum of the continuous function \(\prod_s|\cos(a_s\theta/2)|^{p_s/2}\) on that closed set.

Near zero, the expansion \(\log\cos x=-x^2/2+O(x^4)\) gives, for each fixed real \(u\),

\(\displaystyle \log\Phi_N(u/\sqrt N) =-\frac{u^2}{8N}\sum_s n_sa_s^2+O(N^{-1}) \longrightarrow-\frac{Q_*u^2}{8}. \)

Choose a sufficiently small fixed \(\delta>0\). The inequality \(\log\cos x\leq-x^2/2\), valid for \(|x|<\pi/2\), also gives

\(\displaystyle |\Phi_N(\theta)|\leq \exp(-NQ_*\theta^2/16) \qquad(|\theta|\leq\delta) \)

for sufficiently large \(N\). After substituting \(\theta=u/\sqrt N\), this provides an integrable Gaussian bound. If \(|z_N-M_N|\) is bounded, the phase \(e^{-iu(z_N-M_N)/\sqrt N}\) tends to one. Dominated convergence, together with the exponentially small contribution outside \([-\delta,\delta]\), yields

\(\displaystyle \lim_{N\to\infty}\sqrt N\,\Pr(X_N=z_N) =\frac1{2\pi}\int_{\mathbb R}e^{-Q_*u^2/8}\,du =\sqrt{\frac2{\pi Q_*}}. \)

The same argument is uniform when \(|z_N-M_N|\) ranges over any fixed bounded interval.

The representative voter is pivotal precisely when

\(\displaystyle q_N^*-a_r\leq X_N<q_N^*.\)

This half-open interval contains exactly \(a_r\) integers, whether or not \(q_N^*\) is an integer. Every such integer lies within \(a_r/2\) of \(M_N\). Summing the local estimate therefore gives

\(\displaystyle \lim_{N\to\infty}\sqrt N\,\beta'_r =a_r\sqrt{\frac2{\pi Q_*}}. \)

Undoing the common scaling proves the lemma. In particular, ties introduce no alternating leading coefficient. \(\square\)

Applying the lemma to the original society, and setting \(K=\sqrt{2/\pi}\), gives

\(\displaystyle b_t=K\,\frac{w_t}{\sqrt A}.\)

Thus the baseline limits exist for every input satisfying the stated rationality and positivity hypotheses.

3. Composite limits and admissibility. Fix any allowed rational internal weights, and put

\(\displaystyle V=\sigma_iv_i^2+\sigma_jv_j^2.\)

The internal positivity requirement implies \(V>0\). The lemma gives

\(\displaystyle \lim_{N\to\infty}\sqrt N\,\beta'_{a_{t,N}}[W_{S,N}(v)] =K\,\frac{v_t}{\sqrt V}. \)

Let \(X_N^{\mathrm{out}}\) be the outsiders’ yes-weight. Changing the bloc’s collective vote from no to yes changes the external outcome exactly when

\(\displaystyle q_N-NB\leq X_N^{\mathrm{out}}<q_N.\)

Denote the probability of this event by \(P_N\). A bloc member changes the composite outcome exactly when that member is internally pivotal and the outsiders satisfy this event. These events involve disjoint sets of independent votes. Hence the exact factorization is

\(\displaystyle \beta'_{a_{t,N}}[W_N\parallel W_{S,N}(v)] =\beta'_{a_{t,N}}[W_{S,N}(v)]\,P_N. \)

If \(B=0\), the external pivotal interval is empty, so every composite influence is zero.

Now suppose \(B>0\). Writing \(H=\sum_t\mu_tw_t\), the outsider mean and variance are

\(\displaystyle M_N^{\mathrm{out}}=\frac N2(H-B),\qquad \operatorname{Var}(X_N^{\mathrm{out}})=\frac N4R. \)

The external pivotal interval is therefore

\(\displaystyle [M_N^{\mathrm{out}}-NB/2,\ M_N^{\mathrm{out}}+NB/2). \)

Its complement is contained in the event \(|X_N^{\mathrm{out}}-M_N^{\mathrm{out}}|\geq NB/2\). Chebyshev’s inequality yields

\(\displaystyle 0\leq1-P_N\leq\frac{R}{NB^2}\longrightarrow0.\)

Combining this with the internal limit proves

\(\displaystyle c_t(v)= \begin{cases} 0,&B=0,\\[2pt] K\,v_t/\sqrt V,&B>0. \end{cases} \)

Every allowed rational internal rule consequently has finite composite limits and is admissible.

4. Feasibility: every instance is a yes-instance. If \(B=0\), nonnegativity and \(\sigma_i,\sigma_j>0\) imply \(w_i=w_j=0\). Thus \(b_i=b_j=0\), and the admissible choice \(v_i=v_j=1\) has \(c_i=c_j=0\). It is feasible.

If \(B>0\), choose

\(\displaystyle v_i=w_i,\qquad v_j=w_j.\)

This satisfies the internal positivity requirement, and \(V=C>0\). Since \(A=C+R\geq C\),

\(\displaystyle c_t(v)=K\,\frac{w_t}{\sqrt C} \geq K\,\frac{w_t}{\sqrt A}=b_t \qquad(t\in\{i,j\}). \)

This proves feasibility in all cases.

5. Expediency: necessary and sufficient conditions. We prove that expediency holds exactly when \(B>0\) and \(R>0\).

*Necessity.* If \(B=0\), both composite limits are zero, so strict improvement is impossible.

Suppose \(B>0\) but \(R=0\). Then \(A=C\). For every allowed internal rule, the composite-limit formula gives

\(\displaystyle \sigma_i c_i(v)^2+\sigma_j c_j(v)^2 =K^2\,\frac{\sigma_iv_i^2+\sigma_jv_j^2}{V} =K^2. \)

The baseline limits likewise satisfy

\(\displaystyle \sigma_i b_i^2+\sigma_j b_j^2 =K^2\,\frac C A =K^2. \)

All these limits are nonnegative, and both bloc masses are positive. Therefore \(c_i(v)>b_i\) and \(c_j(v)>b_j\) would make the first weighted sum of squares strictly larger than the second. This contradiction proves necessity.

*Sufficiency.* Suppose \(B>0\) and \(R>0\).

If both original bloc weights are positive, choose \(v_t=w_t\). Since \(C<A\),

\(\displaystyle c_t(v)=K\,\frac{w_t}{\sqrt C}>K\,\frac{w_t}{\sqrt A}=b_t\)

for both types.

Otherwise, exactly one original bloc weight is positive. Relabel so that \(w_i>0\) and \(w_j=0\). Choose the fixed rational weights

\(\displaystyle v_i=w_i,\qquad v_j=\varepsilon,\qquad \varepsilon=\frac{\min\{1,R\}}2.\)

Here \(\varepsilon>0\) and \(\varepsilon^2<R\): for \(R\leq1\), its square is \(R^2/4<R\); for \(R>1\), its square is \(1/4<R\). Since \(\sigma_j\leq1\),

\(\displaystyle V=C+\sigma_j\varepsilon^2<C+R=A. \)

Consequently,

\(\displaystyle c_i(v)=K\,\frac{w_i}{\sqrt V}>b_i,\qquad c_j(v)=K\,\frac{\varepsilon}{\sqrt V}>0=b_j. \)

This proves sufficiency and supplies rational witnessing weights in every expedient case.

6. Algorithms, bit complexity, and interpretation. Feasibility is decided by returning yes on every promised-valid input. Its witness is \((w_i,w_j)\) when \(B>0\), and \((1,1)\) otherwise.

Expediency requires only testing the following two conditions:

• Some bloc type has positive original weight: \(w_i>0\) or \(w_j>0\).
• Some supported type has positive original weight and positive outsider mass: \(w_t>0\) and \(\mu_t>\sigma_t\).

The second condition is equivalent to \(R>0\), because every summand defining \(R\) is nonnegative. Thus the decision uses \(O(\tau)\) rational tests, without computing any replication size or influence.

For witness construction, \(R\) can be computed by exact rational arithmetic. An unreduced common denominator formed from the input denominators, with squared weight denominators, has \(O(L)\) bits; the corresponding numerators also have \(O(L)\) bits. Hence \(O(\tau)\) arithmetic operations on \(O(L)\)-bit integers give the conservative bound \(O(\tau L^2)\) bit operations, including witness construction. Every witnessing weight has polynomial, in fact \(O(L)\), bit length. The decision alone can be implemented in \(O(L^2)\) bit operations.

The distinction from the finite two-voter theorem is essential: this task fixes two types, while the bloc has \(N(\sigma_i+\sigma_j)\) individual voters. The [Felsenthal–Machover theorem](https://www.lse.ac.uk/cpnss/assets/documents/voting-power-and-procedures/publications/2002/felsanthal.pdf) concerns a bloc of two individual voters.

For example, take \(\mu_i=\mu_j=1/2\), \(\sigma_i=\sigma_j=1/4\), and \(w_i=w_j=1\). Then \(A=1\), \(C=R=1/2\), and the internal choice \(v_i=v_j=1\) gives \(b_i=b_j=K\) and \(c_i=c_j=\sqrt2K\). This is an expedient replicated bloc under the exact definitions in the question.

⟨structured verdict parsed — rendered above⟩

The prover’s output resolves both assigned decision problems. The argument is correct and rigorous: feasibility always holds, and expediency holds exactly when \(B>0\) and \(R>0\). I found no major or minor issues requiring repair.

• Definitions and positivity.

The quantities \(A,B,C,R\) are well-defined, and \(R=A-C\) follows directly from their definitions. Since all supported masses are positive, all weights are nonnegative, and the total original voting weight is positive, at least one supported weight is positive. Thus \(A>0\).

Because both prescribed bloc masses are positive, \(B=0\) is equivalent to \(w_i=w_j=0\), while \(B>0\) implies \(C>0\). These implications justify the later divisions and case distinctions.

• Replication-limit lemma: normalization and Fourier inversion.

Clearing rational weight denominators and dividing by the greatest common divisor preserves both the voting rule and its treatment of quota equality. The resulting positive integer weights have greatest common divisor one.

After removing the representative voter, the stated mean \(M_N=q_N^*-a_r/2\) is correct. Each remaining voter contributes a Bernoulli variable with success probability \(1/2\), so the centered characteristic function is exactly the displayed product of cosine powers. The Fourier inversion formula is consequently valid, including when \(M_N\) is a half-integer.

Types of weight zero can be omitted from this product without affecting the distribution or the influence.

• Replication-limit lemma: local estimate and ties.

The greatest-common-divisor condition correctly excludes any nonzero point in the integration interval at which all cosine factors have absolute value one. The continuous-product argument therefore gives the required uniform exponential bound away from zero. The eventual inequalities \(n_s\geq Np_s/2\) hold because the positive masses are fixed.

Near zero, the logarithmic expansion has the stated limit. For each fixed \(u\), the fourth-order remainder contributes \(O(N^{-1})\). Choosing a sufficiently small fixed neighborhood ensures that all cosine factors are positive there and that the stated Gaussian domination applies.

The bounded displacement condition makes the phase converge to one. Dominated convergence and the exponentially small outer contribution justify the local estimate. The Gaussian integral has the correct constant:
\[ \frac{1}{2\pi}\int_{\mathbb R}e^{-Q_*u^2/8}\,du =\sqrt{\frac{2}{\pi Q_*}}. \]

The pivotal interval correctly includes its lower endpoint and excludes its upper endpoint. An interval of this form with integer length \(a_r\) contains exactly \(a_r\) integers, regardless of whether the quota is integral. Those integers remain within the stated bounded distance of the mean. Summing the local estimates and undoing the scaling proves the lemma, with no parity-dependent leading coefficient.

Thus the baseline formula \(b_t=K w_t/\sqrt A\) is established along the required replication sizes. The proof also justifies the claim that the baseline-limit promise is automatically satisfied under the task’s hypotheses.

• Composite influence and admissibility.

The internal positivity condition implies \(V>0\), so applying the lemma to the internal electorate is legitimate. The lemma explicitly permits masses whose sum is not one.

The exact factorization of composite influence is valid. Internal pivotality depends only on the other bloc members’ votes, and external pivotality depends only on outsider votes. These vote sets are independent under the specified Banzhaf distribution. The external pivotal interval is precisely
\[ q_N-NB\leq X_N^{\mathrm{out}}<q_N. \]

For \(B=0\), this interval is empty, so the composite influences are zero.

For \(B>0\), both the outsider mean and variance are correct. The interval is centered at that mean with half-width \(NB/2\). Its complement is contained in the stated deviation event, and Chebyshev’s inequality gives the correct bound \(R/(NB^2)\). This also handles \(R=0\): the outsider weight then equals its mean deterministically and lies inside the interval.

Therefore \(P_N\to1\), and the displayed composite-limit formula follows. All allowed rational internal rules have finite limits and are admissible.

• Feasibility.

When \(B=0\), both baseline bloc influences and both composite influences vanish. The proposed positive internal weights satisfy the internal-rule requirement.

When \(B>0\), choosing the original bloc weights gives \(V=C>0\). The comparison \(C\leq A\) establishes both required weak inequalities, including when one original bloc weight is zero. Hence every valid instance is feasible.

• Expediency: necessity.

The case \(B=0\) excludes strict improvement immediately.

When \(B>0\) and \(R=0\), the two displayed weighted sums of squared limits both equal \(K^2\). All limits are nonnegative and both coefficients are positive. Strict improvement in both coordinates would therefore strictly increase the weighted sum, contradicting equality. The necessity argument is valid even if one baseline influence is zero.

• Expediency: sufficiency and rational witnesses.

When both original bloc weights are positive, \(C<A\) makes both influence comparisons strict.

In the remaining case, the proposed \(\varepsilon\) is positive and rational. The verification of \(\varepsilon^2<R\) is correct in both stated ranges, including \(R=1\). Since \(\sigma_j\leq1\), the resulting \(V<A\) yields strict improvement for the positive-weight type, while the previously zero-weight type receives positive influence. The witness is fixed independently of replication size and satisfies internal positivity.

• Algorithms, bit complexity, and scope.

The positivity tests are equivalent to the derived criterion because every summand of \(R\) is nonnegative. They scan supported types, as required by the task’s definition of \(\tau\).

The claimed arithmetic bounds are sound. Products of input denominators, including squared weight denominators, have \(O(L)\) bits. The corresponding exact sums and witnessing weights also have \(O(L)\) bits. Using elementary integer arithmetic gives the conservative \(O(\tau L^2)\) bound for decisions and witness construction. The sharper \(O(L^2)\) decision bound is also justified by the rational comparisons alone.

The dependence on \(m\) is properly restricted to the prescribed \(m=2\). The discussion of the finite two-individual-voter theorem is consistent with the task and is not used to establish the replication result. The concluding numerical example agrees with the proved formulas.

No additional clarification is needed to make the argument verifiable.

⟨structured verdict parsed — rendered above⟩