| paper | Justified Representation: From Hare to Droop |
| authors | M. Casey, Edith Elkind |
| venue | WINE 2025 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: Polynomial-time solvable in \(m,\tau,k,L\) by a weighted implementation of Droop GJCR. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given finite \(C\), \(k\), \(T\subseteq 2^{C}\), and rational \(\mu\in\mathbb{Q}_{\ge 0}^{T}\) with \(\sum_{t\in T}\mu_t=1\), compute \(W\subseteq C\) with \(|W|=k\) such that for every \(\ell\in[k]\) and \(x\) satisfying \(0\le x_t\le\mu_t\), \(\sum_t x_t>\ell/(k+1)\), and \(\left(\bigcap_{x_t>0}t\right)\setminus W\ne\varnothing\), some \(t\) with \(x_t>0\) has \(|t\cap W|\ge\ell\); equivalently, compute a committee returned by mass-Droop-GJCR using \(g_{W,\ell}(c)=\sum_{t:\,c\in t,\ |t\cap W|\le\ell-1}\mu_t\) and trigger \(g_{W,\ell}(c)>\ell/(k+1)\).
Complete approval ballots are types \(t\subseteq C\), \(\mu_t\) is their mass, \(W\) is an integral \(k\)-committee, and \(g_{W,\ell}(c)\) is the eligibility mass. The task is constructive feasibility: find \(W\) satisfying continuous \( \mathrm{Droop\text{-}EJR}^{+} \), with no objective function.
The mass charging proof is not stated in the paper and should be formalized carefully at strict quota boundaries; this limits the evidentiary strength of the proposed extension but does not invalidate the question.
fatal: False
The mirror directly covers Theorem 2 and formulates a continuous local-search extension of Theorem 1; it leaves the Monroe, priceability, MES/EES, GCR, negative-result, and experimental claims aside.
The strongest mirror is a continuous version of Droop-EJR\(^+\) committee selection, with the Greedy Justified Candidate Rule as the lead algorithm.
Take a finite candidate set \(C\), committee size \(k\), and approval types \(T\subseteq 2^C\). A type \(t\in T\) is a complete approval ballot, and \(\mu_t\) is its population mass, with \(\sum_t\mu_t=1\). This represents, for example, a large electorate of residents distributed among a modest number of recurring neighbourhood, workplace, or constituency profiles. Millions of voters may be present, but only \(\tau=|T|\) distinct approval types. The committee remains an ordinary integral \(k\)-subset of \(C\); only the population is continuous.
Represent a coalition by a vector \(x\) with \(0\le x_t\le\mu_t\). Its mass is \(|x|=\sum_t x_t\), and its common approvals are \(\bigcap_{x_t>0}t\). The natural continuous Droop threshold is obtained by normalising the paper’s condition \(|S|>\ell n/(k+1)\): a coalition is relevant at level \(\ell\) when \(|x|>\ell/(k+1)\).
The continuous Droop-EJR\(^+\) requirement is therefore:
\[ |x|>\frac{\ell}{k+1} \quad\text{and}\quad \left(\bigcap_{x_t>0}t\right)\setminus W\neq\varnothing \]
must imply that some type with \(x_t>0\) satisfies \(|t\cap W|\ge\ell\).
This is a faithful population mirror. It preserves the candidates, approval ballots, committee size, coalition logic, quota, and representation guarantee. The only change is that a coalition has a mass rather than a named voter set.
My lead anchor is Theorem 2, proved in this paper: “Droop GJCR selects a committee of size \(k\) and satisfies Droop-EJR\(^+\).” The theorem concerns the rule that starts with \(W=\varnothing\) and \(\ell=k\); whenever some unelected candidate \(c\) has a group \(S\subseteq N_c\) of size greater than \(\ell n/(k+1)\), with every voter in \(S\) approving at most \(\ell-1\) members of the current committee, it adds \(c\). If no such candidate exists, it decreases \(\ell\), and at \(\ell=0\) fills the remaining seats arbitrarily.
The continuous problem I would hand to a prover is:
Continuous Droop-EJR\(^+\) Selection. Given \((C,k,T,\mu)\), output a committee \(W\subseteq C\) with \(|W|=k\) satisfying the continuous Droop-EJR\(^+\) condition above.
The continuous Droop-GJCR is immediate. At level \(\ell\), define
\[ g_{W,\ell}(c) = \sum_{\substack{t\in T:\ c\in t\\ |t\cap W|\le \ell-1}}\mu_t. \]
If \(g_{W,\ell}(c)>\ell/(k+1)\), add \(c\); otherwise decrease \(\ell\). This uses only type masses and can be implemented in time polynomial in \(m\), \(\tau\), \(k\), and the encoding length of \(\mu\).
The paper’s proof also has a natural mass version. Charge one unit of cost for each selected candidate equally across the types supporting it. If a candidate is selected at level \(\ell\), its supporting mass exceeds \(\ell/(k+1)\), so each participating unit of mass pays less than \((k+1)/\ell\). A type participating at that point has fewer than \(\ell\) previously selected approved candidates, so its total charge is less than \(k+1\). Since there are finitely many positive-mass types, the aggregate charge is strictly less than \(k+1\); hence fewer than \(k+1\) candidates can be selected before completion. If the final committee failed continuous Droop-EJR\(^+\), the violating coalition would make its common unelected candidate eligible at the corresponding level, a contradiction.
I would therefore classify this mirror as Class A: the continuous problem is tractable by a direct type-level greedy algorithm. This is not an artificial simplification. The original authors’ rule already depends only on approval counts, current committee membership, and the quota. Replacing counts by type-mass sums is exactly the high-multiplicity version of their computation.
A second, more delicate anchor is Theorem 1, also proved here: “\(1/k^2\)-lsPAV is polynomial-time computable and satisfies Droop-EJR\(^+\).” The paper’s rule starts from an arbitrary size-\(k\) committee and repeatedly swaps \(w\in W\) for \(c\notin W\) whenever the PAV score rises by at least \(1/k^2\). The theorem states both that this process is polynomial-time computable and that its terminal committee satisfies Droop-EJR\(^+\).
The corresponding continuous problem would retain the PAV objective
\[ \Phi_\mu(W)=\sum_{t\in T}\mu_t H_{|t\cap W|}, \qquad H_j=\sum_{r=1}^{j}\frac1r, \]
and ask for a size-\(k\) committee \(W\) with no improving single swap:
\[ \Phi_\mu(W-w+c)\le \Phi_\mu(W) \]
for every \(w\in W\) and \(c\notin W\). Such a committee automatically satisfies continuous Droop-EJR\(^+\): a violating coalition of mass \(s>\ell/(k+1)\) would create a strictly positive aggregate gain from swapping in its commonly approved unelected candidate.
This is a genuine mirror of the PAV-local-search problem, but I would not claim that Theorem 1’s polynomial bound transfers unchanged. In the finite proof, the \(1/k^2\) score increment gives a polynomial bound on the number of iterations. After normalising scores by population size, that increment becomes \(1/(nk^2)\), and a pure continuum has no canonical \(n\). Positive score improvements can be arbitrarily small. Thus I would treat exact continuous PAV local search as a Class C candidate, or at least an open boundary problem: its difficulty arises from the loss of finite atomic slack, not from any change to the approval or committee model. The weaker continuous Droop-EJR\(^+\) selection problem remains Class A because Theorem 2 supplies a different direct algorithm.
The high-multiplicity regime is plausible rather than universal. A national election, participatory-budgeting process, or university-wide representative body may have very many agents but relatively few recurring approval profiles. The type must include everything relevant to the problem—here, the complete approval set—so this is not pretending that idiosyncratic voters are identical. It is precisely the regime in which the finite election is naturally described by proportions such as “\(16.8\%\) approve this project set,” rather than by a list of named individuals.
The paper contains no numbered NP-hardness or parameterized-hardness theorem of its own; the NP-hardness of computing PAV is cited externally. Consequently, this paper cannot provide a hardness-dissolution anchor in the strongest ChoCo sense. Its positive contribution to the continuization programme is instead that a named, proved polynomial-time representation result has a clean high-multiplicity analogue, and that the paper’s own rule can be executed directly over masses.
My weakest point is the treatment of strict quotas. Several other results in the paper, especially those involving integer divisibility or the \(+1\) supplied by Lemma 1, may not survive naively in the continuum. The lead GJCR mirror avoids that problem through strict mass inequalities and finite type aggregation, but it still deserves a formal proof rather than being assumed from the finite theorem. That caveat does not undermine the main case: for Theorem 2, the continuous question is natural, precise, computationally meaningful, and tractable for exactly the high-multiplicity reason the programme is designed to study.
The strongest case against the proposal is that the paper’s contribution is principally axiomatic. The genuinely new claims are that particular rules satisfy stronger Droop representation axioms; the polynomial-time facts are either routine properties of the rules or inherited from earlier work. Thus the paper offers no hardness, approximation, parameterized-complexity, or optimization theorem whose population dependence it studies. That makes it a weak source for the ChoCo programme.
Theorem 1 also does not transfer cleanly. PAV’s finite score is an unnormalised sum over voters. After normalising to population mass, the paper’s improvement threshold \(1/k^{2}\) becomes \(1/(nk^{2})\). There is no canonical \(n\) in the continuum, and the threshold tends to zero under replication. The proof only guarantees a positive improvement: after normalisation, its key bound is essentially
\[ \frac{|S|}{n}\frac{k+1}{\ell}-1, \]
which can be arbitrarily close to zero as \(|S|/n\) approaches \(\ell/(k+1)\). Consequently, the proposed exact continuous local-search problem is a new problem, not the polynomial-time algorithm proved in Theorem 1. It may be an interesting Class C boundary, but it cannot support the proponent’s tractability claim.
That argument does not defeat the first anchor, however; it only removes the second.
Theorem 2 has a much stronger continuous mirror. For a committee \(W\), define
\[ g_{W,\ell}(c) = \sum_{\substack{t\in T:\ c\in t\\ |t\cap W|\le \ell-1}}\mu_t. \]
The mass version of Droop GJCR adds \(c\) whenever \(g_{W,\ell}(c)>\ell/(k+1)\). Its proof genuinely survives. Charge one unit of cost for \(c\) across the eligible mass. Every participating unit of mass pays less than \((k+1)/\ell\); because the algorithm visits levels in descending order, a type eligible at level \(\ell\) has been charged for at most \(\ell-1\) earlier approved candidates, each at no greater per-unit rate. Its total charge is therefore less than \(k+1\). Since total mass is \(1\), fewer than \(k+1\) candidates can be selected.
If the final committee violated continuous Droop-EJR\({}^{+}\), a coalition of mass \(s>\ell/(k+1)\) would have a common unelected candidate \(c\), while every participating type had fewer than \(\ell\) approved winners. Those types would contribute at least \(s\) to \(g_{W,\ell}(c)\), so \(c\) would have been selected. This is a valid contradiction.
Nor is there a modelling objection available. Approval ballots are complete types for this problem; repeated approval profiles are entirely plausible in a large electorate; identities play no role; and rational masses correspond exactly to finite elections after clearing denominators. The strict Droop inequality is natural and avoids the finite \(+1\) issue.
So the best negative case is a substantial downgrade: Theorem 1 is not a transferred polynomial-time result, and the paper lacks the kind of computational landscape ChoCo normally seeks. But the universal claim fails. The continuous Droop-GJCR selection problem is a legitimate high-multiplicity population mirror, and its direct polynomial algorithm survives. Saying that it merely replaces counts by masses would not defeat it: that is precisely the accepted high-multiplicity operation.
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.