Answer: Mass-GJCR completed by Approval Voting guarantees \(R\geq 2/\sqrt{k}-1/k\) on every society specified in the question.
Theorem 9 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe Greedy Justified Candidate Rule com- pleted with AV has a utilitarian guarantee of 2 √ k −1 k.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates C, committee size k, rational masses over explicit approval types, and a fixed tie-breaking order, compute mass-GJCR's partial committee, complete it with the k-|W| candidates of largest approval mass, and compute its exact weighted utilitarian ratio against the best size-k committee.
Let \(C\) contain \(m\geq1\) candidates, let \(1\leq k\leq m\) be an integer, and fix a strict candidate order for all ties. A society is given by its support: \(\tau\) distinct approval types \(A_j\subseteq C\), each with positive binary-rational mass \(p_j\), with \(\sum_jp_j=1\). Here \(\tau\) is the support size, not the number of possible approval types; \(L\) is the total input bit length. State any running times in \(m,\tau,L,k\). Assume at least one supported type is nonempty.
Mass-GJCR starts with \(W=\varnothing\). For each unselected candidate \(c\) and integer \(1\leq\ell\leq k\), define \(s_{c,\ell}(W)=\sum_{j:c\in A_j,\ |A_j\cap W|<\ell}p_j\). A pair is eligible when \(s_{c,\ell}(W)\geq\ell/k\). Repeatedly add the candidate belonging to an eligible pair of maximum mass, breaking candidate ties by the fixed order; stop when no pair is eligible or \(|W|=k\).
Set \(a(c)=\sum_{j:c\in A_j}p_j\). Complete \(W\) to \(\widehat W\) by adding the \(k-|W|\) unselected candidates with largest \(a(c)\), using the same tie order. Define \(U(S)=\sum_jp_j|A_j\cap S|\) and the exact weighted utilitarian ratio \(R=U(\widehat W)/\max_{S\subseteq C,\ |S|=k}U(S)\).
Does mass-GJCR completed by Approval Voting guarantee \(R\geq 2/\sqrt{k}-1/k\) on every such society, or can its worst-case ratio be smaller?
For finite unweighted electorates, GJCR completed by Approval Voting guarantees \(2/\sqrt{k}-1/k\) ([Brill and Peters](https://arxiv.org/html/2312.08187)). No result addressing exactly this rational-mass formulation was located in the literature search.
The guarantee holds: every society in the question satisfies \(R\geq 2/\sqrt{k}-1/k\). Rational masses cannot produce a smaller ratio.
The proof is an exact replication argument, using the finite-electorate guarantee in [Brill and Peters, Theorem 9](https://arxiv.org/html/2312.08187#S4.Thm9). We verify eligibility, maximization, stopping, ties, completion, and welfare scaling.
First, we prove that the greedy procedure cannot make more than \(k\) selections, even if the explicit size cap is removed.
At selection step \(t\), choose an eligible pair \((c_t,\ell_t)\) attaining the maximum mass, and write \(q_t=s_{c_t,\ell_t}(W_{t-1})\). Define its qualifying types by
\(T_t=\{j:c_t\in A_j,\ |A_j\cap W_{t-1}|<\ell_t\}\).
Every remaining pair’s mass is nonincreasing as the committee grows. Consequently, an ineligible pair cannot become eligible, and the successive selected masses satisfy \(q_1\geq q_2\geq\cdots\).
For bookkeeping, charge type \(j\) an amount \(p_j/q_t\) at step \(t\) when \(j\in T_t\), and zero otherwise. The total charge at each step is
\(\sum_{j\in T_t}p_j/q_t=q_t/q_t=1\).
We prove that each type’s cumulative charge never exceeds \(kp_j\). Suppose \(j\in T_t\), and put \(h=|A_j\cap W_{t-1}|\). This type has previously been charged at most \(h\) times, because each charge requires selecting a candidate it approves. Each previous charge is at most \(p_j/q_t\), by monotonicity of the selected masses. Its cumulative charge after this step is therefore at most
\((h+1)p_j/q_t\leq \ell_t p_j/q_t\leq kp_j\),
where the first inequality uses \(h<\ell_t\), and the second uses eligibility \(q_t\geq\ell_t/k\). Types outside \(T_t\) retain their previous charges, establishing the assertion inductively.
Thus \(t\) selections imply
\(t\leq\sum_jkp_j=k\).
An eligible pair after the \(k\)-th selection would permit one more selection and contradict this inequality. Hence stopping at size \(k\) agrees with stopping when no eligible pair exists.
Write each mass as \(p_j=u_j/v_j\), where \(u_j,v_j\) are positive integers. Choose a positive common multiple \(N\) of all denominators, and put \(n_j=Np_j\). Then every \(n_j\) is a positive integer and \(\sum_jn_j=N\).
Construct a finite unweighted electorate with \(n_j\) voters approving exactly \(A_j\). Keep the same candidates, committee size, and candidate tie order.
For any committee \(W\), unselected candidate \(c\), and level \(\ell\), let \(B_{c,\ell}(W)\) consist of all replicated voters who approve \(c\) and have fewer than \(\ell\) approved members in \(W\). Exactly,
\(|B_{c,\ell}(W)|=Ns_{c,\ell}(W)\).
Therefore,
\(s_{c,\ell}(W)\geq\ell/k\) if and only if \(|B_{c,\ell}(W)|\geq\ell N/k\).
Finite GJCR considers groups of voters approving a common candidate whose members all have fewer than \(\ell\) approved committee members. For fixed \(c,\ell,W\), every such group is a subset of \(B_{c,\ell}(W)\). Thus:
Maximizing eligible group size is consequently identical to maximizing eligible mass: every objective value is multiplied by the same positive integer \(N\). Candidate ties are preserved and resolved by the same order. Ties between levels for a single candidate have no effect on the committee.
Starting from the empty committee, induction now shows that both procedures select exactly the same candidate at every step. Section 1 verifies that their stopping conditions also agree. Hence their greedy committees \(W\) coincide.
In the replicated electorate, candidate \(c\)’s approval count is \(Na(c)\). Approval Voting completion therefore ranks all remaining candidates exactly as in the mass society, including ties. Both procedures produce the same completed committee \(\widehat W\).
Let \(\operatorname{SW}_N(S)\) denote unweighted utilitarian welfare in the replicated electorate. For every committee \(S\),
\(\operatorname{SW}_N(S)=\sum_j n_j|A_j\cap S|=NU(S)\).
It follows that
\(\max_{|S|=k}\operatorname{SW}_N(S)=N\max_{|S|=k}U(S)\).
The denominator is positive: a nonempty supported type has positive mass, and a candidate it approves can be included in a size-\(k\) committee.
Brill and Peters’ Theorem 9 states that finite unweighted GJCR completed by Approval Voting guarantees utilitarian ratio at least \(2/\sqrt{k}-1/k\).
The replicated instance satisfies its hypotheses: it has a positive finite number of voters, approval ballots over the same finite candidate set, and \(1\leq k\leq m\). Sections 1–3 identify our output with a permitted output of that rule and preserve its ratio exactly. Therefore,
\(R=U(\widehat W)/\max_{|S|=k}U(S)=\operatorname{SW}_N(\widehat W)/\max_{|S|=k}\operatorname{SW}_N(S)\geq 2/\sqrt{k}-1/k\).
The replication is purely a proof construction; its potentially large electorate introduces no approximation or limiting argument.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned question. The replication preserves the greedy procedure, Approval Voting completion, and welfare ratio exactly. No major or minor mathematical issues were found.
The monotonicity assertion is correct. For each fixed remaining candidate \(c\) and level \(\ell\), enlarging \(W\) can only remove qualifying types from the sum defining \(s_{c,\ell}(W)\). Thus an ineligible pair cannot become eligible.
Consequently, the selected masses satisfy \(q_{t+1}\leq q_t\): every pair eligible at the next step was eligible at the preceding step, with at least its current mass, and the preceding selection maximized eligible mass.
All divisions by \(q_t\) are valid because eligibility implies \(q_t\geq \ell_t/k>0\). The total charge at each selection is exactly one.
For a type charged at step \(t\), the bound on its previous number of charges is valid: each previous charge required selecting a distinct candidate in its approval set, and those candidates remain in the committee. Hence there were at most \(h=|A_j\cap W_{t-1}|\) previous charges. Monotonicity gives the stated upper bound on each previous charge, and
\[
(h+1)\frac{p_j}{q_t}\leq \ell_t\frac{p_j}{q_t}\leq kp_j
\]
follows from the integer inequality \(h<\ell_t\) and eligibility.
Types not charged retain their previously bounded charges. Summing the bounds therefore establishes \(t\leq k\). The contradiction argument excluding another eligible pair after the \(k\)-th selection is valid. This establishes the claimed agreement of stopping conditions.
A positive common multiple of the finitely many denominators exists. Each \(n_j=Np_j\) is a positive integer, and normalization gives \(\sum_j n_j=N\).
The construction allows repeated ballots, as required for an unweighted electorate. Distinctness of the original support types imposes no obstacle. Empty supported ballots also cause no difficulty: their voters are included in the electorate size but never enter a candidate’s qualifying group.
The identity
\[
|B_{c,\ell}(W)|=Ns_{c,\ell}(W)
\]
is exact. Multiplication by positive \(N\) preserves eligibility, including equality at the threshold. No divisibility assumption on \(N/k\) is needed.
For fixed \(c,\ell,W\), every admissible voter group is a subset of \(B_{c,\ell}(W)\), and the full group itself meets the approval and representation conditions. Thus an eligible subgroup exists exactly when the full group is eligible, and the full group has the largest possible size.
The cited paper’s GJCR definition uses precisely this maximum-group-size selection criterion, and its guarantee applies to permitted outputs of the rule. The fixed candidate order selects a permitted resolution of ties. [Brill and Peters, Sections 2 and 4.1](https://arxiv.org/html/2312.08187)
Multiplication by \(N\) preserves all comparisons and candidate ties. Different maximizing levels for the same candidate do not affect the next committee or future scores. The induction establishing identical greedy committees is therefore sound.
The replicated approval count of each candidate is exactly \(Na(c)\). Consequently, completion selects the same remaining candidates in the same tie order.
The welfare identity holds for every committee, so it also holds after maximizing over the identical family of size-\(k\) committees. The common positive scaling factor cancels from the ratio.
The denominator argument is sufficient: the assumptions supply an approved candidate of positive approval mass, and \(1\leq k\leq m\) permits a size-\(k\) committee containing it.
Theorem 9 states the claimed bound for finite GJCR completed with AV. The source permits arbitrary approval subsets and defines AV completion using the remaining candidates’ approval scores. Its guarantee covers all permitted outputs, so the specified tie order requires no additional hypothesis. [Brill and Peters, Theorem 9](https://arxiv.org/html/2312.08187#S4.Thm9)
The replicated instance satisfies the finite-instance hypotheses. The established output correspondence and welfare scaling justify the final inequality exactly.
The argument covers the stated domain, including \(k=1\), \(k=m\), empty supported ballots, and threshold equalities.
The potentially large replicated electorate does not invalidate an existence-based proof. No running time or polynomial-time claim is made, so there is no unsupported complexity assertion.
Repair feedback: None required. The output establishes the requested welfare guarantee; it does not establish 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.