| paper | What Do Multiwinner Voting Rules Do? An Experiment Over the Two-Dimensional Euclidean Domain |
| authors | Edith Elkind, Piotr Faliszewski, Jean-François Laslier, P. Skowron, A. Slinko, Nimrod Talmon |
| venue | AAAI 2017 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The proposed high-multiplicity \(\beta\)-CC problem is a coherent population mirror, with rational masses corresponding exactly to normalized finite elections. However, both anchors are unnumbered claims imported from cited work, so no computational result of this paper satisfies gate (a). The mirror is worthwhile as a follow-up, but it does not qualify under the stated rubric.
fails bit a — no named computational result to mirror
Neither the \(\beta\)-CC hardness claim nor the GreedyCC guarantee is a numbered computational result established by this manuscript; both are cited background results.
fatal: True
The proposed mirror covers the finite-voter \(\beta\)-CC objective and the cited GreedyCC approximation, but not a computational result established by this paper; the empirical histograms and application recommendations remain outside the mirror's computational coverage.
The strongest honest case is a direct high-multiplicity mirror of the Borda-based Chamberlin–Courant problem. There is, however, a serious source-discipline caveat: the supplied manuscript contains no numbered Theorem, Lemma, Corollary, or Proposition asserting a computational result. Thus it has no qualifying anchor under the stated rule, and I cannot honestly invent a theorem number. Its nearest anchor is an unnumbered claim in Section 2.
That claim says that computing the Borda-based Chamberlin–Courant rule, denoted \(\beta\)-CC, is NP-hard. The paper attributes this result to Lu and Boutilier [18], does not prove it itself, and says that it computes \(\beta\)-CC using an integer linear programming formulation. The underlying problem is: given candidates \(C\), voters with complete rankings, and committee size \(k\), choose \(k\) candidates and assign each voter to a representative in the committee so as to maximize the sum of the voters’ Borda scores for their representatives.
My lead mirror would be Continuous Borda Chamberlin–Courant, \(\beta\)-CC\(_\infty\).
An instance consists of a finite candidate set \(C=\{c_1,\ldots,c_m\}\), a committee size \(k\), a finite set \(T\) of complete ranking types, and rational masses \(\mu_t\ge 0\) satisfying \(\sum_{t\in T}\mu_t=1\). Here \(\mu_t\) is the fraction of the population having ranking \(t\), and \(\operatorname{pos}_t(c)\) is the position of candidate \(c\) in that ranking. The decision variable is an integral committee \(W\subseteq C\) with \(|W|=k\). Its value is
\[ F_\mu(W) = \sum_{t\in T} \mu_t \max_{c\in W} \beta_m\!\left(\operatorname{pos}_t(c)\right), \qquad \beta_m(j)=m-j. \]
The task is to output a committee \(W\) maximizing \(F_\mu(W)\), together with the induced representative assignment sending each type to a highest-ranked member of \(W\). Ties may be resolved arbitrarily.
This is a genuine population mirror. The paper’s Euclidean model can motivate the types without continuizing candidates: retain a finite candidate slate with fixed points \(p(c)\in\mathbb R^2\), let voter locations \(z\) be distributed over a region, and define rankings by Euclidean distance. The plane is partitioned by the \(\binom m2\) perpendicular bisectors into cells on which the ranking is constant; the mass of each cell becomes \(\mu_t\). Thus the paper’s finite sum over voters becomes an integral over the population:
\[ \int_D \max_{c\in W} \beta_m\!\left(\operatorname{pos}_z(c)\right) \,d\mu(z). \]
The many agents could be millions of voters facing a fixed slate of \(m\) candidates, with only a moderate number of distinct ranking cells. In a two-dimensional Euclidean domain, the number of cells induced by the candidate bisectors is at most \(O(m^4)\), so a regime with \(n\gg |T|\) is entirely plausible. The type is a complete ranking, since that is all the rule uses after the spatial preferences have been generated.
The mirror is not merely an outcome-space relaxation or a noise model. The society itself is the mass distribution. Candidates remain discrete, the committee remains an indivisible \(k\)-set, and each infinitesimal voter receives one representative. The paper’s finite elections with \(n_t\) voters of type \(t\) embed exactly by setting
\[ \mu_t=\frac{n_t}{n}. \]
For every committee \(W\),
\[ F_\mu(W) = \frac{1}{n} \operatorname{score}_{\beta\text{-CC}}(W). \]
Consequently, the maximizing committees and tie sets are identical. For the unrestricted ranking-type version, the paper’s NP-hardness transfers directly: this is a Class B mirror, with the hardness living in the candidate-side committee selection rather than in the number of individually named voters. Continuization does not dissolve the underlying combinatorics.
The same mirror also gives a clean algorithmic continuation of the paper’s Appendix B discussion. Its named GreedyCC algorithm starts with an empty committee and repeatedly adds the candidate giving the largest increase in the \(\beta\)-CC score; the paper attributes its \(1-1/e\) approximation guarantee to Lu and Boutilier. In the continuous problem, the marginal gain is simply
\[ \Delta(c\mid W) = F_\mu(W\cup\{c\})-F_\mu(W), \]
which is computable by summing over types. The objective is a monotone submodular function of \(W\), so the same greedy algorithm gives the same \(1-1/e\) guarantee. This is an additional Class A approximation result, although it is not a second qualifying anchor from the manuscript.
The most interesting follow-up is the Euclidean restriction itself. The paper does not prove that \(\beta\)-CC remains NP-hard when all rankings must arise from points in \(\mathbb R^2\). Thus there are two distinct questions:
That second problem is plausibly the best research question for ChoCo: it preserves the authors’ spatial setting while making the population itself continuous.
The weakest point is unavoidable. This manuscript is primarily an empirical study, not a complexity paper, and its relevant hardness statement is unnumbered, cited from elsewhere, and not restricted to the Euclidean domain. Under the strict named-anchor gate, the correct verdict is therefore “no qualifying anchor,” despite the quality of the mirror. Even if the unnumbered Section 2 claim is admitted, the mirror is scientifically modest: \(\mu\) is mainly a coefficient in an unchanged committee-selection problem, so there is no new mass-transfer LP or continuum-specific tractability phenomenon. What survives is nevertheless a faithful and useful Class B boundary case: a paper whose finite voter population can be replaced by a rational distribution without changing the rule, while the computational difficulty remains in the discrete committee structure.
The proponent’s case fails at the assignment’s decisive gate: this manuscript contains no qualifying computational result to mirror. Its numbered contributions are experiments, histograms, and application recommendations. The claims that \(\beta\)-CC and Monroe are NP-hard, that GreedyCC achieves \(1-1/e\), and that GreedyMonroe has an approximation guarantee are all literature summaries attributed to other papers; none is stated as a theorem proved here. The ILP formulations are computational machinery for running the experiments, not results about complexity.
The proposed \(\beta\)-CC\(_\infty\) is nevertheless a legitimate high-multiplicity formulation. For rational masses, clearing denominators produces a finite election with
\[ F_\mu(W)=\frac{1}{n}\operatorname{score}_{\beta\text{-CC}}(W). \]
That exact correspondence is not a modelling defect under ChoCo: Class B mirrors are allowed, and hardness may transfer. Thus I would not pretend that the mirror is meaningless merely because the committee remains integral or because its answer agrees with the finite problem.
But it is not a result of this paper. The unrestricted ranking-type version mirrors an external NP-hardness theorem cited in Section 2, not a theorem established by the manuscript. The stronger Euclidean version is a sensible new problem—one can replace the empirical voter sample by a density over the \(O(m^4)\) ranking cells induced by planar bisectors—but the paper proves no complexity result for that restriction. Its status is an open follow-up, not a continuization of one of the paper’s results.
GreedyCC does not rescue the case. Its weighted-mass extension follows immediately from the same monotone-submodular argument, and the guarantee is explicitly attributed to Lu and Boutilier. It supplies neither a named result of this paper nor a new continuum-specific computational phenomenon.
So the strongest negative verdict is procedural but conclusive under the stated rubric: this is an empirical spatial study with imported complexity facts, not a computational paper containing an anchor for ChoCo. The universal substantive claim is weaker: the Euclidean \(\beta\)-CC population model is genuinely plausible and could support a worthwhile new project. If the anchor requirement were relaxed to include cited background results, the proponent’s case would survive as a modest Class B mirror. Under the actual requirement, however, it should not qualify.
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.