d4-journals-geb-2017-0078 (d4-journals-geb-2017-0078)

Given binary-rational type masses μ_t summing to one, a target aggregate power vector p, accuracy ε, and fixed η in (0,1/2), find rational type weights w_t ≥ 0 and a quota fraction q such that, writing W = ∑_t μ_t w_t, ηW ≤ q ≤ (1-η)W, the type-level limits Φ_t exist and ∥Φ-p∥_2 ≤ ε. Here Φ_t is the limit, as N tends to infinity through sizes with integral Nμ_t, of the total ordinary Shapley–Shubik index of the Nμ_t voters of type t in the replicated game with quota Nq. Treat this as a promise inverse-design problem: a type-homogeneous reasonable scheme achieves error at most ε/2.

A society is given by its support: a list of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types. Voting is binary, so \(m=2\).
Fix a rational constant \(\eta\in(0,1/2)\). Input also includes \(p\in\mathbb Q^\tau\) and rational \(\varepsilon>0\); \(L\) is the total input bit length.
A type-homogeneous scheme assigns every voter of type \(t\) the same weight \(w_t\geq0\). Write \(W=\sum_t\mu_tw_t\), require \(W>0\), and call the scheme reasonable when \(\eta W\leq q\leq(1-\eta)W\); its quota fraction is \(q/W\).
For every positive integer \(N\) with all \(N\mu_t\) integral, form a weighted voting game with \(N\mu_t\) voters of type \(t\), each of weight \(w_t\); a coalition wins when its total weight is at least \(Nq\).
Let \(\phi_i^{(N)}\) be the ordinary Shapley–Shubik index and define \(\Phi_t=\lim_{N\to\infty}\sum_{i:\operatorname{type}(i)=t}\phi_i^{(N)}\), along all such admissible sizes. These indices use the ordinary normalization, summing to \(1\).
Promise: some reasonable type-homogeneous scheme with real weights and quota has all these limits and satisfies \(\|\Phi-p\|_2\leq\varepsilon/2\). Find rational weights and quota defining a reasonable scheme whose limits exist and satisfy \(\|\Phi-p\|_2\leq\varepsilon\).

Is this promised inverse-design problem solvable in time polynomial in \(m,\tau,L,1/\varepsilon\), or is it NP-hard?

Known discrete result: [De, Diakonikolas, and Servedio](https://arxiv.org/pdf/1212.5132) give a randomized algorithm with running time \(\operatorname{poly}(n,2^{\operatorname{poly}(1/\varepsilon)},\log(1/\delta))\), achieving Shapley error \(\varepsilon\) with probability at least \(1-\delta\) under a sufficiently accurate reasonable-target promise.
For discrete exact inversion with a prescribed threshold, [Diakonikolas and Pavlou](https://arxiv.org/pdf/1812.11712) prove intractability unless the polynomial hierarchy collapses.
On the continuous side, [Neyman](https://www.researchgate.net/publication/38361781_Renewal_Theory_for_Sampling_Without_Replacement) establishes a forward Shapley–Shubik limit theorem for vanishing individual relative weights and quotas bounded away from the endpoints.

Result

The promised problem is deterministically polynomial-time solvable, in fact in time polynomial in \(\tau,L\), with no additional dependence on \(1/\varepsilon\).

The key identity is that every reasonable fixed type-homogeneous scheme has limits
\[ \Phi_t=\frac{\mu_tw_t}{W}. \]
Thus inverse design reduces to Euclidean projection onto the probability simplex. We prove the limit identity, give an exact rational construction, and verify its bit complexity.

1. The forward limit

We use the following precise form of Neyman’s theorem, stated as Theorem 1.1 in [Kurz, *Approximating power by weights*](https://arxiv.org/pdf/1802.00497).

Neyman’s theorem. Let \(a_1,\ldots,a_n\) be nonnegative real weights summing to \(1\), and let \(P_i(a,b)\) be the probability that voter \(i\) first makes the accumulated weight strictly exceed \(b\) in a uniformly random ordering. For every \(h>0\), there are constants \(\delta>0\) and \(K>0\) such that, writing \(\rho=\max_i a_i\),
\[ \rho<\delta,\qquad K\rho<b<1-K\rho \quad\Longrightarrow\quad \sum_i|P_i(a,b)-a_i|<h. \]

These pivotal probabilities have the ordinary normalization: their sum is \(1\).

Proposition. Fix any scheme with real weights \(w_t\geq0\), \(W>0\), and quota fraction \(\alpha=q/W\in[\eta,1-\eta]\). Along all admissible population sizes, its limits exist and satisfy
\[ \Phi_t=\frac{\mu_tw_t}{W}. \]

Proof. Because all masses are rational, there are infinitely many admissible sizes: every multiple of a common denominator is admissible.

For an admissible size \(N\), normalize each voter’s weight by the total weight \(NW\). A voter \(i\) of type \(t\) then has weight
\[ a_i^{(N)}=\frac{w_t}{NW}. \]
These normalized weights sum to \(1\), and their maximum satisfies
\[ \rho_N=\frac{\max_t w_t}{NW}\longrightarrow0. \]
Here the weights and the finite support are fixed while \(N\) increases.

We must account for the task’s weak quota inequality. Let \(s_N\) be the largest normalized coalition weight strictly below \(\alpha\). This maximum exists because there are finitely many coalitions, and the empty coalition has weight \(0<\alpha\). Choose
\[ \max\{s_N,\eta/2\}<b_N<\alpha. \]
Such a choice exists because both \(s_N\) and \(\eta/2\) are strictly below \(\alpha\).

For every coalition \(S\),
\[ \sum_{i\in S}a_i^{(N)}\geq\alpha \quad\Longleftrightarrow\quad \sum_{i\in S}a_i^{(N)}>b_N. \]
Indeed, every coalition weight below \(\alpha\) is at most \(s_N<b_N\), while every weight at least \(\alpha\) exceeds \(b_N\). Therefore the two threshold conventions define exactly the same finite game. In particular,
\[ \phi_i^{(N)}=P_i(a^{(N)},b_N). \]

Also, \(\eta/2<b_N<1-\eta\). For any \(h>0\), take the constants \(\delta,K\) from Neyman’s theorem. For all sufficiently large admissible \(N\),
\[ \rho_N<\delta,\qquad K\rho_N<\eta/2. \]
Consequently \(K\rho_N<b_N<1-K\rho_N\), so the theorem gives
\[ \sum_i|\phi_i^{(N)}-a_i^{(N)}|\longrightarrow0. \]

There are exactly \(N\mu_t\) voters of type \(t\). Hence
\[ \left| \sum_{i:\operatorname{type}(i)=t}\phi_i^{(N)} -\frac{\mu_tw_t}{W} \right| \leq \sum_i|\phi_i^{(N)}-a_i^{(N)}| \longrightarrow0. \]
This proves the proposition. The auxiliary quotas \(b_N\) are used only in this proof; the algorithm need not compute them.

2. The feasible vectors form exactly the simplex

Define the probability simplex
\[ \Delta_\tau= \left\{r\in\mathbb R^\tau: r_t\geq0,\ \sum_{t=1}^{\tau}r_t=1 \right\}. \]

The proposition implies that every reasonable scheme has its limiting vector in \(\Delta_\tau\).

Conversely, let \(r\in\Delta_\tau\). Because every mass is positive, we can set
\[ w_t=\frac{r_t}{\mu_t},\qquad q=\frac12. \]
Then
\[ W=\sum_t\mu_tw_t=\sum_t r_t=1. \]
Since \(\eta<1/2\), this scheme is reasonable. The proposition yields \(\Phi_t=r_t\). If \(r\) is rational, all output weights and the quota are rational.

Thus every simplex vector is attainable, including boundary vectors with zero coordinates.

3. Exact rational projection

We now construct the point \(r\in\Delta_\tau\) closest to the rational input vector \(p\).

Define
\[ F(\lambda)=\sum_{t=1}^{\tau}\max\{p_t-\lambda,0\}. \]
This function is continuous. It tends to infinity as \(\lambda\) tends to negative infinity, and is zero when \(\lambda\geq\max_t p_t\). Moreover, it is strictly decreasing wherever it is positive: if \(\lambda_1<\lambda_2\) and \(F(\lambda_2)>0\), at least one summand decreases strictly and all others are nonincreasing. Therefore there is a unique \(\lambda\) satisfying \(F(\lambda)=1\).

Set
\[ r_t=\max\{p_t-\lambda,0\}. \]
By construction, \(r\in\Delta_\tau\).

Projection property. For every \(x\in\Delta_\tau\),
\[ \|x-p\|_2^2\geq\|r-p\|_2^2+\|x-r\|_2^2. \]

To prove this, let \(A=\{t:p_t>\lambda\}\). For \(t\in A\), \(r_t-p_t=-\lambda\); outside \(A\), \(r_t=0\) and \(p_t\leq\lambda\). Since \(x\) and \(r\) both sum to \(1\),
\[ (r-p)\cdot(x-r) = -\lambda\sum_t(x_t-r_t) +\sum_{t\notin A}(\lambda-p_t)x_t \geq0. \]
Expanding the square gives
\[ \|x-p\|_2^2 = \|r-p\|_2^2+\|x-r\|_2^2 +2(r-p)\cdot(x-r), \]
which proves the asserted inequality. In particular, \(r\) is the unique closest simplex point.

Computing \(r\). Sort the coordinates of \(p\) as \(b_1\geq\cdots\geq b_\tau\). For each \(j\), compute
\[ \lambda_j=\frac{\sum_{i=1}^{j}b_i-1}{j}. \]
Find a \(j\) satisfying
\[ b_j>\lambda_j,\qquad j=\tau\ \text{or}\ b_{j+1}\leq\lambda_j. \]
Such a \(j\) exists: take the number of sorted coordinates strictly greater than the unique root \(\lambda\). The equation \(F(\lambda)=1\) then gives \(\lambda=\lambda_j\).

Conversely, either displayed condition guarantees that precisely the first \(j\) coordinates exceed \(\lambda_j\), and their excesses sum to \(1\). Thus the computed value is the required root. All calculations and comparisons use rational arithmetic.

4. Correctness under the promise

Compute the projection \(r\) above and output
\[ w_t=\frac{r_t}{\mu_t},\qquad q=\frac12. \]

The promise supplies a reasonable scheme with limiting vector \(r^\star\) satisfying
\[ \|r^\star-p\|_2\leq\varepsilon/2. \]
By Section 1, \(r^\star\in\Delta_\tau\). Since \(r\) is the closest simplex point,
\[ \|r-p\|_2\leq\|r^\star-p\|_2\leq\varepsilon/2. \]

Section 2 shows that the output scheme is rational and reasonable, its limits exist, and its limiting vector equals \(r\). Consequently it satisfies the stronger guarantee
\[ \|\Phi-p\|_2\leq\varepsilon/2<\varepsilon. \]

5. Bit complexity and the discrete results

Write each input coordinate as \(p_t=u_t/v_t\), with positive integer denominator \(v_t\). A common denominator \(B=\prod_t v_t\) has bit length at most the total input length. Each prefix sum can therefore be represented over \(B\) using integers of bit length \(O(L+\log\tau)\). Each candidate \(\lambda_j\), and each output coordinate \(r_t\), likewise has polynomial bit length.

Dividing \(r_t\) by the positive input rational \(\mu_t\) preserves polynomial bit length. Sorting uses \(O(\tau\log\tau)\) rational comparisons; the remaining construction uses polynomially many exact arithmetic operations on integers of polynomial bit length. The entire algorithm therefore runs in time polynomial in \(\tau,L\).

Very small masses may produce numerically large weights, but their binary encoding lengths remain polynomial.

The cited [discrete approximation algorithm](https://arxiv.org/pdf/1212.5132) and [discrete inversion hardness result](https://arxiv.org/pdf/1812.11712) concern finite voting games. Here the target consists of type aggregates after replication to arbitrarily large populations. The forward limit proved above makes those aggregates exactly normalized weight shares, which enables the polynomial algorithm.

⟨structured verdict parsed — rendered above⟩

The output establishes the promised polynomial-time result. The cited theorem applies, the limiting identity follows, and the rational construction satisfies the stronger error bound \(\varepsilon/2\). There is one minor wording error in the projection algorithm; it does not affect the algorithm as specified.

1. Cited forward theorem

The stated version of Neyman’s theorem matches Theorem 1.1 of [Kurz, *Approximating power by weights*](https://arxiv.org/pdf/1802.00497). Its hypotheses allow nonnegative real weights, including zero weights, and its conclusion controls the total absolute error. The constants depend on the requested accuracy and apply uniformly over the number of voters, the normalized weights, and qualifying quotas.

This uniformity justifies applying the theorem to the varying population sizes and auxiliary quotas in the output. No additional theorem hypothesis is missing.

2. Normalization and admissible sizes

These steps are correct:

• Rational masses have a common denominator, whose positive multiples are admissible population sizes.
• The total weight at size \(N\) is \(NW>0\), so normalization is legitimate.
• Every supported type occurs at each admissible size, since \(N\mu_t\) is a positive integer. Consequently the stated maximum normalized weight is exactly \(\rho_N=\max_t w_t/(NW)\).
• With a fixed finite support and fixed real weights, \(\rho_N\) tends to zero along all admissible sizes.

The argument does not require the original weights to be rational.

3. Weak versus strict threshold conventions

The threshold conversion is rigorous.

Because \(\alpha\geq\eta>0\), the empty coalition belongs to the finite set of coalition weights strictly below \(\alpha\). Thus \(s_N\) exists and satisfies \(s_N<\alpha\). Also \(\eta/2<\alpha\), so the specified interval for \(b_N\) is nonempty.

Every coalition weight below \(\alpha\) is at most \(s_N<b_N\), while every coalition weight at least \(\alpha\) exceeds \(b_N\). Therefore the two conventions give the same game, including exact ties at the original quota. Their pivotal probabilities consequently agree.

The bounds needed for Neyman’s theorem also hold. Once \(K\rho_N<\eta/2\), the lower bound follows from \(b_N>\eta/2\). For the upper bound, \(b_N<1-\eta\) and \(K\rho_N<\eta\) imply \(b_N<1-K\rho_N\).

For every positive accuracy parameter, the theorem therefore bounds the total absolute error at all sufficiently large admissible sizes. This establishes convergence, not merely convergence along a selected subsequence. Computing \(s_N\) or \(b_N\) is unnecessary because they appear only in the proof.

4. Type aggregation and attainable vectors

The aggregation inequality is a direct application of the triangle inequality. The sum of normalized weights within type \(t\) equals \(\mu_tw_t/W\), so the claimed type limits follow.

The characterization of attainable vectors is also correct. For any simplex vector \(r\), positivity of every \(\mu_t\) permits the construction \(w_t=r_t/\mu_t\). It gives \(W=1\), and \(q=1/2\) is reasonable because \(\eta<1/2\). The forward proposition then gives limiting vector \(r\).

Zero coordinates cause no difficulty: zero weights are permitted by both the task and the cited theorem. This also covers \(\tau=1\).

5. Projection argument and computation

The existence and uniqueness argument for the root of \(F(\lambda)=1\) is valid. Continuity, the stated limiting behavior, and strict decrease whenever the later value is positive suffice.

The projection calculation has the correct sign. Outside the active set, both \(\lambda-p_t\) and \(x_t\) are nonnegative. The displayed inner-product identity therefore yields the asserted squared-distance inequality and uniqueness of the closest simplex point.

The computational rule is correct when its two displayed requirements are imposed together. Taking the number of coordinates strictly above the root gives a positive valid index, including when coordinates equal the root.

Minor issue — Section 3, “Computing \(r\),” converse sentence. The sentence “Conversely, either displayed condition guarantees that precisely the first \(j\) coordinates exceed \(\lambda_j\)” is false if “either” means that either requirement alone suffices.

For example, with sorted coordinates \(b=(2,2)\) and \(j=1\), one has \(\lambda_1=1\) and \(b_1>\lambda_1\), but both coordinates exceed \(\lambda_1\). The first requirement alone is insufficient.

Minimum clarification: Replace “either displayed condition” with “the two displayed conditions together.” The preceding algorithm already requires both, so this is an expositional correction rather than a mathematical gap.

6. Promise and output guarantee

The promise supplies a limiting vector in the simplex by the established forward proposition. The projection property therefore gives \(\|r-p\|_2\leq\varepsilon/2\).

The output weights and quota are rational, have \(W=1>0\), are reasonable, and have the proved limits. Since \(\varepsilon>0\), the stronger guarantee implies the required error bound.

No additional restriction on the signs or normalization of the input vector \(p\) is used.

7. Bit complexity and scope

The bit-complexity argument is sound. The product of input denominators has polynomial bit length; prefix sums, candidate thresholds, and projected coordinates consequently admit polynomial-length rational representations. Division by a positive input mass preserves that bound.

Sorting and scanning require polynomially many exact arithmetic operations on polynomial-length integers. The procedure does not enumerate populations or coalitions and does not need an effective convergence rate from Neyman’s theorem. Its dependence on the encoding of \(\varepsilon\) is already included in \(L\).

The distinction from the supplied discrete results is valid: the requested outputs concern limits of replicated type aggregates. The proof settles this continuous promised problem.

⟨structured verdict parsed — rendered above⟩