| paper | Completing Priceable Committees: |
| authors | — |
| venue | AAAI 2024 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 9
statement extracted from the paper’s text layer
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.
Weighted high-multiplicity approval voting with approval types and rational mass; the decision variable is an indivisible committee, mass-GJCR supplies the partial committee, AV supplies completion, and weighted utilitarian welfare is the objective.
Theorem 9's continuous computation is essentially fixed-rule evaluation with weighted sums, introducing no new population-driven complexity boundary; the proponent concedes this limitation.
fatal: False
The mirror directly covers Theorems 9 and 17, while leaving the paper's other welfare, representation, trade-off, and completion guarantees untreated.
There is a credible mirror, and it is especially clean because this paper’s only voter-level input is an approval set. I would make Theorem 9 the lead anchor and Theorem 17 a secondary one. The supplied paper has no numbered theorem whose headline is NP-hardness or membership in P; these are named algorithmic approximation theorems instead.
The natural regime is a large constituency choosing a small committee of representatives or projects. Millions of residents may fall into a few stable approval archetypes: neighbourhood coalitions, unions, departments, professional associations, or recurring participatory-budgeting blocs. A type is an approval set \(A_t\subseteq C\), and \(\mu_t\) is the fraction of the population with that approval set. Here \(n\) may be millions while \(\tau\), the number of distinct approval types, is tens or hundreds. Approval sets are a complete description of voters for this paper, so no information is lost by grouping identical voters.
The committee remains indivisible: the decision variable is still \(W\subseteq C\), \(|W|=k\). Only the population is continuized. Define
\[ a_\mu(c)=\sum_{t:c\in A_t}\mu_t, \]
\[ \operatorname{uw}_\mu(W)=\sum_t\mu_t|A_t\cap W|, \qquad \operatorname{cov}_\mu(W)=\sum_t\mu_t\mathbf 1[A_t\cap W\neq\varnothing]. \]
Thus AV maximizes \(\operatorname{uw}_\mu\), while CC maximizes \(\operatorname{cov}_\mu\). For rational \(\mu\), this is exactly the high-multiplicity version of the discrete profile: choose a common denominator \(D\), create \(D\mu_t\) copies of each type, and normalize all voter counts by \(D\). Conversely, every discrete profile collapses to such a distribution. The continuous input is therefore a compressed high-multiplicity instance, not merely an analogy.
My lead problem is Continuous GJCR–AV Completion.
An instance consists of a candidate set \(C\), committee size \(k\), a finite support of approval types \((A_t)_{t\in T}\), rational masses \(\mu_t\), and a fixed tie-breaking order. For a partial committee \(W\), define
\[ q_W(c,\ell)= \sum_{\substack{t:c\in A_t\\ |A_t\cap W|<\ell}}\mu_t. \]
This is the mass of approvers of \(c\) who currently have fewer than \(\ell\) approved committee members. Continuous GJCR repeatedly selects a candidate \(c\notin W\) for which \(q_W(c,\ell)\ge \ell/k\) for some \(\ell\in[k]\), choosing the eligible candidate with maximum such mass, and stops when no eligible pair remains. It then completes \(W\) to size \(k\) by adding the \(k-|W|\) remaining candidates with largest approval masses \(a_\mu(c)\).
The output is the resulting exhaustive committee \(\widehat W\), together with the GJCR selection trace if verification is required. The objective is the same as in the paper:
\[ \frac{\operatorname{uw}_\mu(\widehat W)} {\max_{|S|=k}\operatorname{uw}_\mu(S)} \ge \frac{2}{\sqrt{k}}-\frac1k. \]
This is a faithful mirror of Theorem 9, quoted in the paper as:
“The Greedy Justified Candidate Rule completed with AV has a utilitarian guarantee of \(\frac{2}{\sqrt{k}}-\frac1k\).”
Theorem 9 is proved in this paper and answers the open question of Elkind et al. (2022). Its proof is expressed entirely through approval counts, proportionality thresholds, and inequalities between candidate scores. For rational masses, the theorem transfers exactly by expanding the distribution into repeated voters; in compressed form, the algorithm computes each \(q_W(c,\ell)\) by scanning the \(\tau\) types. Thus the expected classification is Class A for this approximation problem: the committee can be computed in time polynomial in \(m,\tau\), and the encoding length of the masses, without expanding the enormous population.
The proportionality interpretation also survives exactly. An \(\ell\)-large group becomes a submass of at least \(\ell/k\), and cohesion means that all types carrying positive submass share an approved candidate. The GJCR trigger is precisely the continuous version of finding such a needy group. The paper already identifies GJCR as satisfying EJR+; the natural mass formulation preserves that interpretation, and AV completion cannot destroy it.
Further questions are whether the factor \(2/\sqrt{k}-1/k\) remains tight when \(\tau\) is small, whether one can optimize over all EJR+-compatible continuous committees rather than follow GJCR, and whether the type-compressed representation yields an exact or parameterized algorithm when \(\tau\) is fixed.
A second, independent mirror is Continuous Affordable–MMS Completion, based on Theorem 17:
“Let \(W\) be an affordable committee. Then the committee obtained by completing \(W\) by running the maximin support rule approximates the maximin support objective by a factor of \(1/2\).”
This theorem is also proved in the paper, although its proof applies a lemma from Cevallos and Stewart (2021).
Here the instance is \(C,k,(A_t,\mu_t)\), together with a partial committee \(W_0\) and, if \(W_0\) is not generated internally, a payment certificate. A continuous payment system has values \(p_t(c)\) satisfying
\[ p_t(c)=0\quad\text{if }c\notin A_t, \]
\[ \sum_{c\in C}p_t(c)\le k\quad\text{for every type }t, \]
and
\[ \sum_t\mu_t p_t(c)= \begin{cases} 1,&c\in W_0,\\ 0,&c\notin W_0. \end{cases} \]
This is exactly the paper’s affordability definition after rescaling each voter’s budget from \(k/n\) to a per-unit-mass budget of \(k\).
Define continuous maximin support by
\[ \operatorname{mms}_\mu(W)= \min_{\varnothing\neq S\subseteq W} \frac{\sum_{t:A_t\cap S\neq\varnothing}\mu_t}{|S|}. \]
Starting from \(W_0\), repeatedly add the candidate maximizing \(\operatorname{mms}_\mu(W\cup\{c\})\) until \(k\) candidates have been selected. A valid solution is the resulting committee \(\widehat W\), required to satisfy
\[ \operatorname{mms}_\mu(\widehat W) \ge \frac12 \max_{|S|=k}\operatorname{mms}_\mu(S). \]
This is again expected to be Class A at the approximation level. The paper presents the discrete maximin-support method as a polynomial-time approximation; replacing voter counts by rational weighted sums gives the compressed high-multiplicity version. Exact maximin-support optimization is a separate question and may retain candidate-side hardness.
This second mirror is valuable because it preserves the paper’s priceability idea rather than merely weighting the welfare objective. A unit of population owns a continuous budget, candidates still cost one unit, and the partial committee must be supportable by a mass-based payment certificate. Natural follow-up questions include whether the \(1/2\) factor is tight for small \(\tau\), whether affordability plus continuous types permits a stronger approximation, and whether maximin support can be solved exactly under a fixed-type- support parameter.
I would not claim that this paper covers the whole continuization programme. These mirrors cover Theorem 9 and Theorem 17 emphatically; they do not turn the committee into a fractional vector, nor do they replace the election by probabilistic social choice. The selected candidates remain discrete, and the continuous object is solely the electorate.
The weakest point is that the positive results may look formally easy: for rational masses, one can expand the instance back into a discrete election, so the proofs of Theorems 9 and 17 contribute little new continuum-specific mathematics. An opponent could fairly call this “weighted high-multiplicity approval voting in new notation.” I concede that. The case is therefore not that this paper already demonstrates a new continuous complexity phenomenon. The case is that its problem is a particularly legitimate continuous mirror: the high-multiplicity regime is socially plausible, the type definition is exact, the proportionality thresholds become cleaner, and the paper’s named guarantees survive as compressed computational questions with the candidate-side combinatorics intact.
The strongest negative case is that the proponent has shown a faithful weighted high-multiplicity reformulation, but not a worthwhile ChoCo computational mirror.
Theorem 9 is a guarantee theorem, not a complexity theorem. It does not define a new input problem whose exact, approximation, or parameterized complexity is open. “Compute continuous GJCR–AV” is simply evaluation of a fixed greedy rule followed by sorting candidate approval masses. Given approval types, every quantity
\[ a_\mu(c)=\sum_{t:c\in A_t}\mu_t,\qquad q_W(c,\ell)=\sum_{t:c\in A_t,\ |A_t\cap W|<\ell}\mu_t \]
is obtained by scanning the support. The resulting committee is exactly the committee obtained from a finite election formed by blowing up rational masses. Theorem 9 therefore transfers unchanged, but only because the theorem is already invariant under cloning voters.
That is not a defect in the model: large approval electorates are a perfectly sensible high-multiplicity regime. It does mean, however, that the proposed “continuous question” contributes no population-level optimization, separation problem, or complexity boundary. It replaces integer counts by rational coefficients in a rule whose sufficient statistics were already those counts. The paper’s substantive theorem is the inequality, not the computation of the output, and the inequality remains a direct corollary of the discrete theorem.
A stronger repair would ask for the best committee satisfying EJR+ or affordability while maximizing welfare, rather than mechanically running GJCR. That would be a legitimate weighted approval-committee problem, but it is no longer Theorem 9. It changes the fixed rule into an existential candidate-selection problem. Its difficulty comes from choosing a discrete committee, not from continuizing the electorate; the continuous version is merely the weighted high-multiplicity formulation of that new problem. It may deserve separate study, but it cannot rescue the claimed mirror of this paper’s result.
Theorem 17 has the same problem. The proposed mass payment certificate is mathematically sound: after rescaling, constraints C1–C4 become linear constraints over approval types, and
\[ \operatorname{mms}_\mu(W) = \min_{\varnothing\ne S\subseteq W} \frac{\mu(\{t:A_t\cap S\ne\varnothing\})}{|S|}. \]
For rational masses this is exactly the discrete theorem on a blown-up electorate. But if \(W\) is supplied, affordability is only certificate checking; if it is generated by MES or GJCR, the paper already supplies the rule. Completing it by maximin support is again a known candidate-side greedy procedure with weighted support calculations. The factor \(1/2\) is inherited pointwise; it is not a new continuous optimization result.
The best repair would optimize over affordable or EJR+-compatible partial committees and then complete one with maximum MMS. That is a potentially interesting weighted committee-selection problem, but it is an invented strengthening, not a computational consequence of Theorem 17. It also confirms the central weakness: the continuous population is only a coefficient compression, while every difficult decision remains the choice of a subset of candidates. A fractional committee, a lottery over committees, or a mass allocation of candidates might create genuine continuous optimization, but those are outcome-space continuizations explicitly outside ChoCo’s scope.
Thus the opponent cannot honestly claim that this paper has no plausible high-multiplicity interpretation, nor that its axioms collapse or depend on voter identity. Those objections would be wrong. The narrower and stronger objection is that both anchors are clone-invariant welfare/representation guarantees whose proposed continuous versions are immediate weighted restatements, not named computational problems from the paper. Under ChoCo’s strict screening criterion requiring a computational result to mirror, that is enough for rejection. Under a broader criterion that admits any meaningful weighted approval-election question, the negative case is weak: the paper would deserve at least an orange verdict, and perhaps green for an explicitly redesigned constrained-committee optimization problem.
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.