| paper | Completing Priceable Committees: Utilitarian and Representation Guarantees for Proportional Multiwinner Voting |
| authors | Markus Brill, Jannik Peters |
| venue | AAAI 2024 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
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. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
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.
Finite approval types \(t\) carry population mass \(\mu_t\); the committee remains an integral \(k\)-subset, GJCR selects candidates using eligible approver mass \(q_{c,\ell}(W)=\sum_{t:c\in A_t,\,|A_t\cap W|<\ell}\mu_t\), AV completion maximizes \(a_\mu(c)=\sum_{t:c\in A_t}\mu_t\), and the objective is normalized utilitarian welfare.
The mirror is largely an exact histogram compression of the finite profile, so explicit-type computation introduces no new complexity boundary or optimization challenge.
fatal: False
The mirror covers Theorem 1 and the GJCR--AV utilitarian guarantee; it leaves the paper's other completion, proportionality, coverage, and maximin-support results unmirrored.
The strongest honest case is a qualified one, centred on Theorem 1, proved in this paper:
“The Greedy Justified Candidate Rule completed with AV has a utilitarian guarantee of \(\frac{2}{\sqrt{k}}-\frac{1}{k}\).”
More explicitly, for every finite approval profile \((A,C,k)\), if \(W\) is the committee produced by GJCR and \(\overline{AV}(W)\) is obtained by filling the remaining seats with the highest-approval candidates, then
\[
\frac{\operatorname{sw}(\overline{AV}(W))}
{\operatorname{sw}(AV(\mathcal I))}
\ge \frac{2}{\sqrt{k}}-\frac{1}{k}.
\]
This theorem is proved here; the paper presents it as answering an open question from earlier work.
The natural mirror is Continuous GJCR–AV. An instance consists of candidates \(C\), committee size \(k\), a finite list of approval types \(T\subseteq 2^C\), and rational masses \(\mu_t\) with \(\sum_t\mu_t=1\). Type \(t\) represents a positive fraction \(\mu_t\) of a large electorate and has approval set \(A_t\). The committee remains an integral \(k\)-subset; only the population is continuous.
For a committee \(W\), define
\[
u_t(W)=|A_t\cap W|
\quad\text{and}\quad
a_\mu(c)=\sum_{t:c\in A_t}\mu_t.
\]
Continuous GJCR starts with \(W=\varnothing\). For each candidate \(c\notin W\) and \(\ell\in[k]\), let
\[
q_{c,\ell}(W)
=
\sum_{\substack{t:c\in A_t\\u_t(W)<\ell}}\mu_t.
\]
This is the mass of approvers of \(c\) whose current representation is below \(\ell\). If \(q_{c,\ell}(W)\ge \ell/k\), the pair \((c,\ell)\) is eligible; the rule adds an eligible candidate maximizing \(q_{c,\ell}(W)\), with fixed tie-breaking, and stops when no candidate is eligible or \(k\) candidates have been chosen. It then completes \(W\) with the \(k-|W|\) candidates of largest \(a_\mu(c)\).
The computational problem is: given \((C,k,T,\mu)\), compute the resulting committee \(\widehat W\) and its exact ratio
\[
R_\mu(\widehat W)
=
\frac{\sum_t\mu_t|A_t\cap \widehat W|}
{\max_{|X|=k}\sum_t\mu_t|A_t\cap X|},
\]
or decide whether \(R_\mu(\widehat W)\ge q\) for a rational threshold \(q\).
This is a genuine high-multiplicity mirror. If \(\mu_t=n_t/n\), then
\[
q_{c,\ell}(W)
=
\frac{|\{i\in N_c:|A_i\cap W|<\ell\}|}{n},
\]
so the continuous eligibility condition \(q_{c,\ell}(W)\ge\ell/k\) is exactly the discrete GJCR condition \(|N'|\ge \ell n/k\). Likewise, utilitarian welfare becomes the population-normalized version of the paper’s welfare. Nothing has been fractionalized except the electorate: candidates, seats, approval sets, and representation levels remain discrete.
The plausible regime is a large election with many repeated approval ballots: for example, a national or organizational election where millions of voters fall into a few hundred recurring approval patterns generated by party, region, occupation, or issue coalition. The relevant comparison is \(n\gg\tau\), where \(\tau=|T|\), not that every election is high-multiplicity.
I would expect this mirror to be Class A for explicit type support. Every \(q_{c,\ell}(W)\) is computable by summing over \(T\), there are at most \(k\) rounds and \(mk\) candidate-level tests per round, and AV completion is just sorting the \(a_\mu(c)\). Thus the rule-output problem is solvable in polynomial time in \(m\), \(k\), \(\tau\), and the encoding length of \(\mu\). Theorem 1’s proof should transfer essentially verbatim after replacing normalized voter counts by masses, yielding the same guarantee
\[
\frac{2}{\sqrt{k}}-\frac{1}{k}.
\]
The mirror generates worthwhile follow-up questions: whether this bound is tight over continuous societies; whether one can optimize over GJCR tie-breaking; how much finite-population rounding changes the guarantee; and what happens when the type distribution is implicit rather than explicitly listed. Replacing AV completion by exact CC completion would also move the problem toward candidate-selection hardness, showing that the useful tractability here comes from the particular completion objective rather than from continuity alone.
The weak point is substantial. Theorem 1 is an approximation-guarantee theorem, not a named NP-hardness, membership-in-\(\mathrm P\), FPT, or parameterized-complexity result. The paper’s statements that CC is computationally intractable and that certain approximation bounds are best possible are attributed to earlier literature, not proved as named computational results here. Therefore, if the programme’s anchor gate requires an explicit complexity classification, this paper has no fully compliant anchor. If approximation guarantees count as computational anchors, Continuous GJCR–AV is a credible positive mirror; otherwise the correct verdict is that the paper supplies a natural continuous problem but not a qualifying computational result.
The decisive objection is that this paper supplies no qualifying computational anchor under ChoCo’s strict gate. Theorem 1 is a guarantee about a fixed rule, not a complexity classification or an exact, approximation, or parameterized algorithm for a computational problem. GJCR is already an explicitly specified greedy procedure, and AV completion is just sorting candidates by approval score. The paper’s statement that CC is computationally intractable is background attributed to earlier work, not a numbered result proved here. The remaining theorems are welfare, coverage, and proportionality guarantees.
The proposed Continuous GJCR–AV model is nevertheless well-defined. That is precisely why it is not a strong negative case: approval voting has a natural high-multiplicity regime. If \(A\subseteq C\) is an approval type, a finite profile induces
\[ \mu_A=\frac{|\{i:A_i=A\}|}{n}. \]
Then
\[ a_\mu(c)=\frac{|N_c|}{n} \]
and the continuous eligibility mass is exactly the discrete eligible-group size divided by \(n\). GJCR makes the same choices, AV has the same ordering, and the normalized welfare ratio is unchanged. Conversely, every rational mass vector can be expanded into a finite electorate using a common denominator. Thus this is a legitimate high-multiplicity compression of the paper’s anonymous approval profile.
What it does not provide is a new computational question generated by continuization. Computing all \(q_{c,\ell}(W)\), running the greedy rule, completing by AV, and evaluating the ratio is a straightforward polynomial-time simulation over the explicit type list. There is no mass-transfer optimization, separation problem, fractional feasibility issue, or new complexity boundary. The continuous input merely replaces repeated ballots by their histogram. That may be a useful dictionary or implementation perspective, but it is a weak claim to present as a substantive ChoCo mirror of this paper.
A stronger proposal does not repair the missing anchor. Weighted CC completion would give a genuine high-multiplicity problem, but it would mirror weighted maximum coverage and the paper’s cited background, not a computational theorem established here. Optimizing over EJR+ or affordable committees would be a worthwhile new research problem, but it would be invented beyond the paper’s results. Making candidates or committee membership fractional would leave population continuization and move to outcome-space continuity. Refining types by individual identities would add information that the paper’s rules and objectives never use.
The negative case is therefore strong only under the programme’s strict anchor requirement: this paper does not contain a named computational result that demands a continuous mirror. It is not honest to claim that no worthwhile continuous formulation exists in any scenario. The proponent’s mirror is natural and admissible as a high-multiplicity restatement; if approximation-guarantee theorems count as anchors, the universal negative fails.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.