Answer: Every specified input satisfies \(R\ge 2/\sqrt{k}-1/k\). Producing \(\widehat W\) and the exact ratio \(R\), or testing \(R\ge q\), is polynomial-time solvable.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe Greedy Justified Candidate Rule completed with AV has a utilitarian guarantee of $\frac{2}{\sqrt{k}} - \frac{1}{k}$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), committee size \(k\), explicit approval types \(T\), rational masses \(\mu\in\Delta(T)\), and fixed tie-breaking, compute the committee produced by mass-based GJCR followed by AV completion, and compute or threshold-test its normalized utilitarian welfare against the best integral \(k\)-committee.
Let \(C\) contain \(m\ge 1\) candidates and let \(1\le k\le m\). A society is given by its support: the list of the \(\tau\) distinct approval types \(A_t\subseteq C\) with positive masses \(\mu_t\), each a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible approval sets. Fix a total order on candidates for all tie-breaking; let \(L\) be the total input bit length.
Mass-based GJCR starts with \(W=\varnothing\). For every \(c\in C\setminus W\) and integer \(1\le\ell\le k\), define \(s_{c,\ell}(W)=\sum_{t:\,c\in A_t,\ |A_t\cap W|<\ell}\mu_t\). Among pairs satisfying \(s_{c,\ell}(W)\ge\ell/k\), select a candidate whose pair maximizes \(s_{c,\ell}(W)\), using the fixed order for candidate ties, and add it to \(W\). Stop when no pair qualifies or \(|W|=k\).
AV completion retains \(W\) and fills its remaining seats with candidates of highest mass approval score, using the same order; denote the resulting integral committee by \(\widehat W\).
Define \(U(S)=\sum_t\mu_t|A_t\cap S|\), \(U^*=\max_{S\subseteq C,\ |S|=k}U(S)\), and \(R=U(\widehat W)/U^*\), with \(R=1\) when \(U^*=0\). The computational question is to produce \(\widehat W\) and \(R\), or test \(R\ge q\) for an input binary rational \(q\in[0,1]\); state running times in \(m,\tau,k,L\).
Does mass-based GJCR followed by AV completion guarantee \(R\ge \frac{2}{\sqrt{k}}-\frac{1}{k}\) on every such input, or is there a counterexample?
For finite voter lists, GJCR followed by AV completion guarantees a utilitarian ratio of at least \(\frac{2}{\sqrt{k}}-\frac{1}{k}\). [Brill and Peters](https://arxiv.org/pdf/2312.08187)
The literature search located no result explicitly addressing this mass-based welfare guarantee.
1. Proven result
Yes. On every input specified in the question, mass-based GJCR followed by AV completion guarantees \(R\ge 2/\sqrt{k}-1/k\). Moreover, the committee, its exact ratio, and the threshold test are computable in polynomial time from the support representation.
The proof uses exact replication of rational masses. No approximation or continuity argument is needed.
2. Exact correspondence with a finite electorate
Write each mass as \(\mu_t=a_t/b_t\), where \(a_t,b_t\) are positive integers. Set \(D=\prod_{t=1}^{\tau}b_t\) and \(n_t=a_t(D/b_t)\). Then \(n_t=D\mu_t\) is a positive integer, and normalization gives \(\sum_t n_t=D\).
Construct, conceptually, a finite electorate containing \(n_t\) voters with approval set \(A_t\), for every type \(t\). Its total number of voters is \(n=D\).
Fix a committee \(W\), an unselected candidate \(c\), and \(\ell\in\{1,\ldots,k\}\). Let \(Q_{c,\ell}(W)\) be all replicated voters who approve \(c\) and have fewer than \(\ell\) approved members of \(W\). By construction,
\( |Q_{c,\ell}(W)|=\sum_{t:\,c\in A_t,\ |A_t\cap W|<\ell}n_t=D\,s_{c,\ell}(W). \)
In finite-voter GJCR, a witness group for this candidate and level is a subset \(N'\subseteq Q_{c,\ell}(W)\) satisfying \(|N'|\ge \ell n/k\). Such a group exists exactly when the entire set \(Q_{c,\ell}(W)\) satisfies that inequality. Consequently,
\( |Q_{c,\ell}(W)|\ge \ell n/k\quad\Longleftrightarrow\quad s_{c,\ell}(W)\ge \ell/k. \)
For a fixed pair, the largest possible witness group is \(Q_{c,\ell}(W)\). Thus maximizing witness-group cardinality in finite-voter GJCR is exactly equivalent to maximizing \(s_{c,\ell}(W)\): every score is multiplied by the same positive factor \(D\).
Starting from the empty committee, induction now proves that the two procedures select the same candidate at every step. Indeed, whenever their current committees agree, their qualifying pairs agree, their maximizing candidates agree, and the fixed candidate order resolves ties identically. Their stopping conditions therefore agree as well.
For AV completion, define the mass approval score \(p_c=\sum_{t:\,c\in A_t}\mu_t\). Candidate \(c\)'s finite approval score is \(Dp_c\). Completion therefore also selects exactly the same candidates, with identical tie-breaking.
3. Transfer of the welfare guarantee
The finite-voter result we use is Theorem 9 of [Brill and Peters](https://arxiv.org/pdf/2312.08187): for every finite approval profile and valid committee size, GJCR followed by AV completion has utilitarian ratio at least \(2/\sqrt{k}-1/k\). Their formulation allows tied outputs, so the specified candidate order is covered.
All hypotheses hold for the replicated electorate: it has a positive finite number \(D\) of voters, approval ballots over the same candidate set, and \(1\le k\le m\). The preceding correspondence identifies its output with \(\widehat W\).
For every candidate set \(S\), its finite utilitarian welfare is
\( \operatorname{uw}_{D}(S)=\sum_t n_t|A_t\cap S|=D\,U(S). \)
Taking maxima over all sets of size \(k\) gives \(\operatorname{uw}_{D}^{*}=D\,U^*\). If \(U^*>0\), the finite theorem therefore yields
\( R=\frac{U(\widehat W)}{U^*}=\frac{\operatorname{uw}_{D}(\widehat W)}{\operatorname{uw}_{D}^{*}}\ge \frac{2}{\sqrt{k}}-\frac{1}{k}. \)
If \(U^*=0\), the prescribed ratio is \(R=1\). This also satisfies the bound, since \(1-(2/\sqrt{k}-1/k)=(1-1/\sqrt{k})^2\ge 0\).
This completes the proof for every input in the question.
4. Exact computation and running time
The electorate need not be expanded. Although \(D\) can be exponentially large numerically, its binary length is \(O(L)\), because \(\log_2 D=\sum_t\log_2 b_t\). Each integer weight \(n_t\) likewise has \(O(L)\) bits.
Maintain \(r_t=|A_t\cap W|\). At each greedy step, for each unselected candidate form the bins
\( h_{c,j}=\sum_{t:\,c\in A_t,\ r_t=j}n_t,\qquad 0\le j<k. \)
Their prefix sums give \(S_{c,\ell}=\sum_{j=0}^{\ell-1}h_{c,j}=D\,s_{c,\ell}(W)\). Test qualification using the exact integer inequality \(kS_{c,\ell}\ge \ell D\), and maximize \(S_{c,\ell}\) among qualifying pairs. After selecting \(c\), increment \(r_t\) for precisely the types approving \(c\).
Building the bins and checking their prefixes takes \(O(m(\tau+k))\) arithmetic operations per step. There are at most \(k\) steps. Precompute \(P_c=\sum_{t:\,c\in A_t}n_t\), and sort candidates by \(P_c\), breaking ties by the given order. This supplies both AV completion and an optimal size-\(k\) committee \(S^*\), because
\( U(S)=\sum_{c\in S}p_c. \)
Set \(T=\sum_{c\in\widehat W}P_c\) and \(H=\sum_{c\in S^*}P_c\). Output \(R=T/H\) when \(H>0\), and \(R=1\) otherwise. For \(q=u/v\), with \(v>0\), the positive-denominator case is decided exactly by \(vT\ge uH\).
Including common-denominator preprocessing, the arithmetic-operation bound is
\( O\!\left(\tau+km(\tau+k)+m\log(m+1)\right). \)
All integers used have \(O(L+\log(k+1))\) bits. With schoolbook integer arithmetic, a conservative bit-operation bound for producing \(\widehat W\) and the exact rational ratio, or testing the threshold, is
\( O\!\left(L+\left[\tau+km(\tau+k)+m\log(m+1)\right]\left[L+\log(k+1)\right]^2\right). \)
Here the algorithm scans only the \(\tau\) listed approval types.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The rational replication preserves the specified greedy rule, AV completion, and welfare ratios exactly. The cited finite-voter theorem applies, and the support-based algorithm has the claimed polynomial running time. No major or minor mathematical issues were found.
The construction assumes only the stated input conditions: positive rational masses summing to \(1\). With \(D=\prod_t b_t\), every denominator divides \(D\), so each \(n_t=a_t(D/b_t)\) is a positive integer. The identity \(\sum_t n_t=D\sum_t\mu_t=D\) is correct.
Thus the conceptual electorate is finite and nonempty. Its potentially enormous cardinality does not invalidate the welfare argument, which does not require constructing the electorate explicitly.
For every current committee, unselected candidate, and allowed level, the equality \(|Q_{c,\ell}(W)|=D\,s_{c,\ell}(W)\) follows directly from replication.
The witness-group argument is valid: every eligible witness is a subset of \(Q_{c,\ell}(W)\), while the entire set itself satisfies the approval and representation conditions. Consequently, a qualifying witness exists precisely when \(|Q_{c,\ell}(W)|\ge \ell D/k\). This reasoning remains valid when \(\ell D/k\) is not an integer.
Maximizing witness cardinality therefore agrees exactly with maximizing mass support over qualifying pairs.
The induction comparing the two procedures is sound. Equal current committees give equal qualifying pairs and equal maximizing candidates. The fixed candidate order resolves candidate ties consistently. Ties between levels for the same candidate require no further rule because only the candidate is added.
The paper’s finite GJCR definition uses the witness conditions and cardinality maximization stated by the prover; its framework treats outputs as committees of size at most \(k\). Its AV completion retains the existing committee and optimizes approval welfare over the remaining seats. These definitions support the claimed correspondence, including stopping and completion. [Brill and Peters, Sections 2–3](https://arxiv.org/pdf/2312.08187)
Multiplying all approval scores by \(D>0\) preserves rankings and ties, so AV completion agrees exactly.
Theorem 9 is correctly identified and states the claimed utilitarian guarantee for GJCR completed with AV. The paper defines voting rules as allowing multiple outputs and guarantees as applying to those outputs, so the specified tie-breaking is covered. [Brill and Peters, Theorem 9 and Section 2](https://arxiv.org/pdf/2312.08187)
The replicated instance satisfies the required conditions: finitely many candidates, a positive finite electorate, approval ballots, and a valid committee size. The prover states the theorem sufficiently precisely and verifies its hypotheses.
The identity \(\operatorname{uw}_D(S)=D\,U(S)\) holds for every candidate set \(S\). Maximization uses exactly the same family of size-\(k\) committees, so the optimum also scales by \(D\). Cancellation is valid when \(U^*>0\).
When \(U^*=0\), the prescribed convention gives \(R=1\). The calculation
\(1-(2/\sqrt{k}-1/k)=(1-1/\sqrt{k})^2\ge 0\)
is correct for every \(k\ge 1\), including \(k=1\).
The maintained values \(r_t\), bins, and prefix sums compute precisely the support quantities used by the rule. Before any selection, \(r_t\le |W|<k\), so the stated bin range includes every relevant type.
The qualification test \(kS_{c,\ell}\ge \ell D\) is equivalent to the original rational inequality. Maximization and tie-breaking can therefore be performed exactly.
The identity \(U(S)=\sum_{c\in S}p_c\) justifies obtaining an optimum from the \(k\) highest approval scores. It also justifies the stated completion procedure. The ratio \(T/H\) is exact when \(H>0\), and the cross-multiplication test is valid because both denominators are positive. When \(H=0\), the already specified value \(R=1\) determines the threshold answer for every allowed \(q\).
Building bins costs \(O(m\tau)\) arithmetic operations per iteration, and inspecting prefixes costs \(O(mk)\). Initialization, count updates, completion scans, and welfare sums fit within the claimed bound. Sorting costs \(O(m\log(m+1))\) comparisons.
The denominator product has \(O(L)\) bits. Normalization implies \(n_t\le D\), and support sums are at most \(D\). Qualification products and committee welfare totals require at most an additional \(O(\log(k+1))\) bits. Threshold products also fit the stated bound when \(L\) includes the threshold input.
The schoolbook bit-operation bound is conservative and valid. It does not depend on expanding the electorate or enumerating unlisted approval types.
Required clarification: None.
⟨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.