d4-conf-sagt-2020-0010 (d4-conf-sagt-2020-0010)

Given rational type masses \(\mu_t>0\) summing to \(1\), positive integer weights \(w_t\), and a rational quota fraction \(\theta\in(0,1)\), let \(\bar w=\sum_t\mu_t w_t\). For sufficiently large population sizes \(N\) such that \(N\mu_t\) and \(N\theta\bar w\) are integers, form the weighted voting game with \(N\mu_t\) voters of type \(t\), each of weight \(w_t\), and quota \(N\theta\bar w\). Let \(x_t^{(N)}\) be the common per-voter nucleolus payoff for type \(t\), and set \(p_t^{(N)}=N x_t^{(N)}\). Determine whether \(p^{(N)}\) converges over these admissible \(N\); if it does, compute its limit.

A society is given by its support: \(\tau\geq1\) types with positive binary rational masses \(\mu_t\) summing to \(1\), positive binary integer weights \(w_t\), and a binary rational quota fraction \(\theta\in(0,1)\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length. There is no separate parameter \(m\).
Put \(\bar w=\sum_t\mu_t w_t\). An admissible population size is a positive integer \(N\) for which every \(N\mu_t\) and \(N\theta\bar w\) is integral. Consider all admissible \(N\) sufficiently large that \(N\theta\bar w>\max_t w_t\).
The replicated game has \(N\mu_t\) voters of weight \(w_t\); a coalition has value \(1\) exactly when its total weight is at least \(N\theta\bar w\), and otherwise has value \(0\). Use the standard nucleolus over imputations, with grand-coalition value \(1\). Symmetry gives a common payoff \(x_t^{(N)}\) within each type; set \(p_t^{(N)}=Nx_t^{(N)}\).

Is deciding whether \(p^{(N)}\) converges as admissible \(N\to\infty\), and computing its exact limit when it does, solvable in polynomial time in \(\tau,L\), or is this problem NP-hard?

Discrete weighted voting nucleoli admit a pseudopolynomial-time algorithm ([Könemann–Toth](https://arxiv.org/pdf/2005.10853)).
The exact replication setting is already covered by Kurz–Napel–Nohn: sufficiently many replicas have nucleolus equal to normalized voting weights, implying eventual equality \(p_t^{(N)}=w_t/\bar w\) and polynomial-time limit computation ([primary source](https://www.vwl4.uni-bayreuth.de/pool/Publikationen_Napel/2014_the_nucleolus_of_large_majority_games.pdf)). Thus this target is already settled.

Result

The problem is polynomial-time solvable. Every society satisfying the stated hypotheses has a convergent sequence, with exact limit

\(\displaystyle \lim_{\substack{N\to\infty\\N\text{ admissible}}}p_t^{(N)}=\frac{w_t}{\bar w}\qquad(t=1,\ldots,\tau).\)

In fact, this equality holds for every sufficiently large admissible \(N\).

1. Admissible sizes are unbounded

Put \(c=\theta\bar w\). Write each \(\mu_t=a_t/b_t\) and \(c=a_0/b_0\) in lowest terms, with positive denominators, and define

\(\displaystyle D=\operatorname{lcm}(b_0,b_1,\ldots,b_\tau).\)

For a reduced rational \(a/b\), integrality of \(Na/b\) is equivalent to \(b\mid N\): coprimality of \(a\) and \(b\) implies that \(b\mid Na\) exactly when \(b\mid N\). Consequently, the admissible sizes are precisely the positive multiples of \(D\).

Because \(c>0\), all sufficiently large such multiples also satisfy \(Nc>\max_t w_t\). Thus the sequence in the question has an unbounded domain.

2. The applicable theorem

We use Proposition 2 of Kurz–Napel–Nohn. For a weighted majority game represented by integer weights, let \(M\) be the largest weight, \(r\) the number of distinct weight values, \(m^\circ\) the minimum multiplicity of a weight value, and \(\widehat q\) the quota divided by total weight. The proposition states that the nucleolus equals the normalized weight vector whenever

\(\displaystyle \min\{\widehat q,1-\widehat q\}\,m^\circ>2rM^2.\)

Their definition is the nucleolus over imputations, as required here. [Kurz–Napel–Nohn, Sections 2–3, Proposition 2](https://www.vwl4.uni-bayreuth.de/pool/Publikationen_Napel/2014_the_nucleolus_of_large_majority_games.pdf).

3. Verification and eventual equality

Define

\(\displaystyle M=\max_t w_t,\qquad \mu_{\min}=\min_t\mu_t>0,\qquad \delta=\min\{\theta,1-\theta\}>0.\)

For admissible \(N\), the replicated game has positive integer weights and total weight

\(\displaystyle W_N=\sum_{t=1}^{\tau}N\mu_t w_t=N\bar w.\)

Its quota is \(q_N=N\theta\bar w\), so its normalized quota is exactly \(\widehat q_N=\theta\).

There are at most \(\tau\) distinct weight values. For any occurring weight \(a\), its multiplicity is

\(\displaystyle m_a(N)=N\sum_{\{t:w_t=a\}}\mu_t\geq N\mu_{\min}.\)

Hence \(m^\circ(N)\geq N\mu_{\min}\). In particular, repeated weight values among the listed types cause no difficulty.

Choose

\(\displaystyle N_0=1+\left\lfloor\max\left\{\frac{2\tau M^2}{\delta\mu_{\min}},\frac{M}{\theta\bar w}\right\}\right\rfloor.\)

For every admissible \(N\geq N_0\), the quota exceeds \(M\), and

\(\displaystyle \delta m^\circ(N)\geq\delta N\mu_{\min}>2\tau M^2\geq2rM^2.\)

All hypotheses of Proposition 2 therefore hold. Each voter of type \(t\) receives its normalized weight,

\(\displaystyle x_t^{(N)}=\frac{w_t}{W_N}=\frac{w_t}{N\bar w}.\)

Multiplication by \(N\) gives

\(\displaystyle p_t^{(N)}=\frac{w_t}{\bar w}\qquad(N\geq N_0,\ N\text{ admissible}).\)

This proves eventual constancy and the asserted limit.

4. Exact computation in polynomial time

The algorithm returns “convergent” and computes \((w_t/\bar w)_{t=1}^{\tau}\). It need not construct any replicated game.

To verify the bit complexity, write the input masses as \(\mu_t=a_t/b_t\), and set

\(\displaystyle B=\prod_{t=1}^{\tau}b_t,\qquad A=\sum_{t=1}^{\tau}a_t w_t(B/b_t).\)

Then \(\bar w=A/B\), and the exact output coordinates are

\(\displaystyle \frac{w_tB}{A},\)

reduced using greatest common divisors.

The binary length of \(B\) is at most the sum of the input denominator lengths plus a constant, hence is \(O(L)\). Because the masses sum to one, \(\bar w\leq M\), so \(A=B\bar w\leq BM\). Thus \(A\) and every numerator \(w_tB\) also have \(O(L)\) bits. All divisions \(B/b_t\) are exact. Polynomially many integer arithmetic and greatest-common-divisor operations on these integers compute the output in time polynomial in \(\tau,L\).

Therefore both convergence determination and exact limit computation are polynomial-time solvable under the stated hypotheses.

⟨structured verdict parsed — rendered above⟩

The argument resolves the assigned problem. The cited theorem is stated correctly, its hypotheses hold for every sufficiently large admissible population, and the exact limit can be computed in polynomial time. No major or minor mathematical issues were found.

• Admissible population sizes. For a reduced fraction \(\frac{a}{b}\), the equivalence between integrality of \(\frac{Na}{b}\) and divisibility \(b\mid N\) is correct. Applying this to all masses and to \(c=\theta\bar w\) shows that admissible sizes are exactly the positive multiples of \(D\). All denominators are positive integers, so \(D\) exists. Since \(c>0\), restricting to \(Nc>M\) leaves an unbounded set of admissible sizes.

• Cited theorem. Proposition 2 does assert equality of the nucleolus and normalized weights under

\[ \min\{\widehat q,1-\widehat q\}m^\circ>2rM^2 \]
for an integer-weight representation. The source defines the nucleolus over imputations and uses the same winning-coalition convention as the task. Its nonincreasing ordering of weights is merely an indexing convention. No minimality, homogeneity, or constant-sum assumption is required. The prover’s citation and theorem statement are accurate. [Kurz–Napel–Nohn, Sections 2–3, Proposition 2](https://www.vwl4.uni-bayreuth.de/pool/Publikationen_Napel/2014_the_nucleolus_of_large_majority_games.pdf).

• Replicated-game parameters. Admissibility makes each \(N\mu_t\) integral; positivity makes it a positive multiplicity. The calculation

\[ W_N=N\bar w,\qquad \frac{q_N}{W_N}=\theta \]
is correct. In particular, the normalized quota lies strictly between zero and one, and the grand coalition is winning.

• Distinct weights and multiplicities. The bound \(r\leq\tau\) is valid even when listed types share a weight. Each occurring weight has multiplicity

\[ N\sum_{\{t:w_t=a\}}\mu_t\geq N\mu_{\min}. \]
Thus \(m^\circ(N)\geq N\mu_{\min}\). The proof correctly groups equal weights rather than assuming all listed weights are distinct.

• Threshold and strict inequalities. The chosen \(N_0\) is an integer strictly larger than both quantities inside the maximum, including when that maximum is integral. Consequently, every admissible \(N\geq N_0\) satisfies both the task’s quota restriction and

\[ \delta m^\circ(N)\geq\delta N\mu_{\min}>2\tau M^2\geq2rM^2. \]
The strict inequality required by Proposition 2 is therefore established.

• Eventual equality and convergence. The theorem gives each voter of type \(t\) payoff \(\frac{w_t}{N\bar w}\). Multiplying by \(N\) yields the claimed eventual equality. Because admissible sizes are unbounded, eventual constancy establishes the stated limit along all admissible sizes. The argument also covers \(\tau=1\); no exceptional case is omitted.

• Exact arithmetic and complexity. The definitions of \(A\) and \(B\) correctly give \(\bar w=\frac{A}{B}\). The product \(B\) has \(O(L)\) bits. Since the masses are positive and sum to one, \(0<\bar w\leq M\), giving \(0<A\leq BM\). Every output numerator \(w_tB\) likewise has \(O(L)\) bits. Intermediate summands and partial sums are positive and bounded by \(A\), so their sizes are also controlled. Exact divisions and greatest-common-divisor computations require only polynomial time. The algorithm need not enumerate replicas or reach the potentially large threshold \(N_0\).

No repair or additional clarification is needed. The proof establishes polynomial-time convergence determination and exact limit computation for every valid input.

⟨structured verdict parsed — rendered above⟩