Answer: \(\rho=29/32\); fractional coalition membership does not change the worst-case approximation ratio.
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximatePRR satisfies 29/32-AS in expectation for any m.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) candidates, a finite-support society of approval types \(S\subseteq C\) with rational masses \(\mu_S\), and a fractional coalition \(z_S\in[0,\mu_S]\) of mass \(q=\sum_S z_S\), where \(q\ge \ell/m\) and the coalition unanimously agrees on the placement of at least \(\ell\) candidates, what is PRR's exact worst-case ratio of expected average satisfaction to \(\ell\)? In particular, does this ratio equal \(29/32\) over all such societies and coalitions?
Let \(C\) contain \(m\ge1\) candidates. A society is given by its support \(\mathcal T\subseteq2^C\): the list of its \(\tau\) approval types with positive binary rational masses \(\mu_S\), normalized by \(\sum_{S\in\mathcal T}\mu_S=1\). Here \(\tau\) is the support size, not the number of possible types; state any running times in \(m,\tau,L,\ell\), where \(L\) is the total input bit length.
PRR independently includes each candidate \(c\) in a committee \(W\subseteq C\) with probability \(p_c=\sum_{S\ni c}\mu_S\); every subset, including the empty and full committees, is allowed.
A fractional coalition has real masses \(0\le z_S\le\mu_S\) and total mass \(q=\sum_S z_S\). For an integer \(1\le\ell\le m\), it is admissible when \(q\ge\ell/m\) and \(\left|\bigcap_{z_S>0}S\right|+\left|\bigcap_{z_S>0}(C\setminus S)\right|\ge\ell\).
Its average satisfaction is \(\operatorname{avs}_W(z)=q^{-1}\sum_S z_S\bigl(|S\cap W|+|(C\setminus S)\cap(C\setminus W)|\bigr)\). Define \(\rho\) as the infimum of \(\mathbb E_{W\sim\mathrm{PRR}}[\operatorname{avs}_W(z)]/\ell\) over all such societies, admissible coalitions, and integers \(m,\ell\).
What is the exact worst-case approximation ratio \(\rho\) of PRR? Does \(\rho=29/32\), or does fractional coalition membership change this ratio?
For finite electorates, PRR guarantees expected average satisfaction at least \((29/32)\ell\) for every qualifying coalition, and this constant is tight. [Source](https://www.rupertfreeman.com/vnw-full.pdf)
No result explicitly treating the fractional-coalition model above was located in the literature search.
Fractional coalition membership does not change the ratio: \(\rho=29/32\).
We prove the lower bound directly for real coalition masses and give a rational instance attaining equality. The instance also appears in Theorem 6 of the [cited paper](https://www.rupertfreeman.com/vnw-full.pdf).
Fix a society and an admissible coalition \(z\) of mass \(q\ge\ell/m\). Define
\(z'_S=\frac{\ell}{mq}z_S\).
The scaling factor lies in \((0,1]\), so \(0\le z'_S\le\mu_S\), and the new coalition has mass exactly \(\ell/m\). Its positive support is unchanged, so it remains cohesive. Moreover, for every committee \(W\), scaling both the numerator and denominator in average satisfaction gives
\(\operatorname{avs}_W(z')=\operatorname{avs}_W(z)\).
Consequently, it suffices to consider coalitions with
\(q=\ell/m\in(0,1]\).
This reduction is exact even when the coalition masses are irrational.
Fix a candidate \(c\). Choose a stance—approval or disapproval—held by at least half of the coalition, breaking ties arbitrarily. Let \(x\in[1/2,1]\) be the fraction of coalition mass holding this stance.
Let \(s\) be the mass outside the coalition holding the same stance. Here the outside mass of type \(S\) is \(\mu_S-z_S\), so
\(0\le s\le1-q\).
Under PRR, the probability that the decision on \(c\) agrees with the chosen stance is
\(d=qx+s\).
For approval this is the inclusion probability; for disapproval it is the exclusion probability.
Thus the expected contribution of \(c\) to coalition average satisfaction is
\(e_c=xd+(1-x)(1-d)\).
Expanding gives
\(e_c=2qx^2-(1+q)x+1+(2x-1)s\).
Since \(2x-1\ge0\) and \(s\ge0\),
\(e_c\ge F_q(x)\), where
\(F_q(x)=2qx^2-(1+q)x+1\).
We now minimize this quadratic on \([1/2,1]\).
\(F'_q(x)=4qx-(1+q)\le3q-1\le0\).
Hence its minimum is \(F_q(1)=q\).
\(x_*=(1+q)/(4q)\).
The inequalities \(q\ge1/3\) and \(q\le1\) imply \(x_*\le1\) and \(x_*\ge1/2\), respectively. Therefore its minimum is
\(g(q)=1-\frac{(1+q)^2}{8q}=\frac{6q-q^2-1}{8q}\).
In addition, if the coalition is unanimous on \(c\), then \(x=1\), and the exact expression yields
\(e_c=q+s\ge q\).
These bounds use only the defining inequalities on real masses.
By linearity of expectation,
\(\mathbb E[\operatorname{avs}_W(z)]=\sum_{c\in C}e_c\).
If \(q\le1/3\), every candidate contributes at least \(q\). Therefore
\(\mathbb E[\operatorname{avs}_W(z)]\ge mq=\ell\).
Now suppose \(q\ge1/3\). Cohesiveness supplies at least \(\ell\) unanimous candidates. Select exactly \(\ell\) of them. Each selected candidate contributes at least \(q\), and each remaining candidate contributes at least \(g(q)\). Thus
\(\mathbb E[\operatorname{avs}_W(z)]\ge\ell q+(m-\ell)g(q)\).
Using \(q=\ell/m\), we obtain
\(\frac{\mathbb E[\operatorname{avs}_W(z)]}{\ell}\ge q+\frac{1-q}{q}g(q)=\frac{9q^3-7q^2+7q-1}{8q^2}\).
The following factorization certifies the desired bound:
\(\frac{9q^3-7q^2+7q-1}{8q^2}-\frac{29}{32}=\frac{(3q-2)^2(4q-1)}{32q^2}\).
For \(q\ge1/3\), the denominator is positive and \(4q-1>0\), so the right-hand side is nonnegative. Consequently, every admissible fractional coalition satisfies
\(\mathbb E[\operatorname{avs}_W(z)]\ge\frac{29}{32}\ell\).
Hence \(\rho\ge29/32\).
Let \(C=\{c_1,c_2,c_3\}\) and \(\ell=2\). Define the society and coalition by:
| Approval type \(S\) | Society mass \(\mu_S\) | Coalition mass \(z_S\) |
|---|---:|---:|
| \(\{c_1,c_2,c_3\}\) | \(5/12\) | \(5/12\) |
| \(\{c_1,c_2\}\) | \(1/4\) | \(1/4\) |
| \(\varnothing\) | \(1/3\) | \(0\) |
The society masses are positive rationals summing to one. The coalition has mass \(q=2/3=\ell/m\), unanimously approves \(c_1,c_2\), and disagrees on \(c_3\). It is therefore admissible.
PRR has inclusion probabilities
\(p_{c_1}=p_{c_2}=2/3\) and \(p_{c_3}=5/12\).
Within the coalition, the approval fraction for \(c_3\) is
\((5/12)/(2/3)=5/8\).
Its expected average satisfaction is consequently
\(\mathbb E[\operatorname{avs}_W(z)]=2\cdot\frac23+\frac58\cdot\frac5{12}+\frac38\cdot\frac7{12}=\frac{29}{16}\).
Dividing by \(\ell=2\) gives \(29/32\), proving \(\rho\le29/32\). Together with the universal lower bound, this settles the question.
⟨structured verdict parsed — rendered above⟩
The prover fully resolves the assigned question. The lower bound applies to arbitrary real coalition masses, and the rational equality instance satisfies every constraint. No major or minor mathematical issues were found.
Admissibility implies \(q\ge\ell/m>0\), so the scaling factor \(\ell/(mq)\) is well-defined and belongs to \((0,1]\).
Consequently, the scaled masses satisfy \(0\le z'_S\le\mu_S\) and sum to \(\ell/m\). Because the scaling factor is strictly positive, the positive support is unchanged. Both intersections defining cohesiveness therefore remain unchanged.
The numerator and denominator of average satisfaction scale by the same factor. Thus the claimed equality of average satisfaction holds for every committee, and hence also in expectation.
This reduction preserves all relevant constraints, including when the original coalition masses are irrational.
For each candidate, a majority stance exists because the two stance fractions sum to one. Its fraction \(x\) lies in \([1/2,1]\).
The outside masses \(\mu_S-z_S\) are nonnegative and sum to \(1-q\). Therefore the stated bound \(0\le s\le1-q\) is correct.
The probability of agreement with the chosen stance is \(d=qx+s\). This identity applies to both approval and disapproval: in the latter case, \(d\) is the exclusion probability.
The expected contribution
\(e_c=xd+(1-x)(1-d)\)
correctly averages the agreement probabilities of the two coalition fractions. Substitution and expansion give exactly
\(e_c=2qx^2-(1+q)x+1+(2x-1)s\).
Since the last term is nonnegative, the bound by \(F_q(x)\) follows.
Both minimization cases are correct:
The formulas agree at \(q=1/3\). At \(q=1\), the stationary point is the permitted endpoint \(1/2\).
For a unanimous candidate, setting \(x=1\) yields the exact expression \(e_c=q+s\ge q\).
Linearity of expectation applies to the finite sum of candidate contributions. Independence between candidates is unnecessary for this step.
When \(q\le1/3\), summing the candidate bounds gives \(mq=\ell\), as claimed.
For \(q\ge1/3\), the positive coalition support is nonempty. The unanimously approved and unanimously disapproved candidate sets are disjoint. Thus the cohesiveness condition supplies at least \(\ell\) distinct unanimous candidates, justifying the selection of exactly \(\ell\) of them.
Applying the unanimous bound to those candidates and the general bound to the remaining candidates gives the stated inequality. Substitution of \(q=\ell/m\) correctly yields
\(\bigl(9q^3-7q^2+7q-1\bigr)/(8q^2)\).
The factorization is correct: expanding its numerator gives
\((3q-2)^2(4q-1)=36q^3-57q^2+28q-4\),
which matches the numerator obtained after subtracting \(29/32\).
On the stated range, the denominator is positive and \(4q-1>0\). The lower bound therefore follows. The argument includes \(q=1\), \(\ell=m\), and \(m=1\); no endpoint is omitted.
The society masses are positive binary-encoded rationals and sum to one. Every coalition mass lies within its corresponding society mass.
The coalition has mass \(2/3=\ell/m\). Its positive support unanimously approves exactly the two candidates \(c_1,c_2\), so it satisfies cohesiveness for \(\ell=2\).
The inclusion probabilities and the coalition approval fraction \(5/8\) for \(c_3\) are correct. The expected contribution of \(c_3\) is
\((5/8)(5/12)+(3/8)(7/12)=23/48\).
Adding the other two contributions gives
\(4/3+23/48=29/16\),
and division by \(\ell=2\) gives \(29/32\).
Thus the instance attains the universal bound. The attribution is also accurate: Theorem 6 of the [cited paper](https://www.rupertfreeman.com/vnw-full.pdf) uses the corresponding twelve-voter profile.
The proof establishes the exact ratio for the specified fractional-coalition model without relying on a transfer theorem from finite electorates. No repair or additional clarification is needed.
No running time is asserted, so the task’s requirements concerning running-time parameters are not triggered. The output establishes an exact approximation guarantee, rather than a computational complexity classification.
⟨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.