| paper | An Experimental Comparison of Multiwinner Voting Rules on Approval Elections |
| authors | Piotr Faliszewski, Martin Lackner, Krzysztof Sornat, Stanisław Szufa |
| venue | IJCAI 2023 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given candidates \(C\), approval types \(T=\{A_1,\ldots,A_\tau\}\) with rational masses \(\mu_i\) summing to \(1\), committee size \(k\), threshold \(q\), and \(d_\mu\) equal to normalized Hamming or Jaccard distance, decide whether integral size-\(k\) committees \(X,Y\subseteq C\) satisfy \(D_\mu(X,Y)=\min_{\pi:X\to Y\text{ bijective}}\sum_{c\in X}d_\mu(c,\pi(c))\ge q\), or optimize \(D_\mu(X,Y)\).
A rational distribution \(\mu\) over complete approval-ballot types, with candidates and committees remaining indivisible; the decision variables are two integral committees and their minimum-weight bijection, and the objective is \(D_\mu\).
The mirror is largely denominator-clearable to a finite election and introduces no new mass-transfer or separation structure, so its independent computational novelty is limited.
fatal: False
The mirror covers Theorem 1 and Theorem 2 for FARTHEST COMMITTEES, with Theorem 2 predicting Class A and Theorem 1 predicting Class B; it leaves Proposition 1, Theorem 3, the axioms, the rule maps, and the experiments alone.
A credible mirror exists, although it is deliberately a “light” continuization: the population becomes a rational distribution over approval-ballot types, while candidates and committees remain indivisible. That is exactly the population continuization ChoCo permits, and it preserves the paper’s central computational object.
My lead anchor is Theorem 2, proved in this paper. It states that FARTHEST COMMITTEES is FPT parameterized by \(n+k\), for any candidate pseudodistance \(d(x,y)\) depending only on the voters approving \(x\) and \(y\).
Define \(\textsc{FarthestCommittees}_{\infty}[\tau+k]\) as follows. The instance consists of a candidate set \(C\), a finite list of approval types \(T=\{A_1,\ldots,A_\tau\}\) with \(A_i\subseteq C\), rational masses \(\mu_i\ge 0\) summing to \(1\), an integer \(k\), and either normalized Hamming or Jaccard distance. For candidates \(c,d\), let
\[ h_\mu(c,d)=\sum_{i=1}^{\tau}\mu_i\left|\mathbf 1[c\in A_i]-\mathbf 1[d\in A_i]\right|. \]
For Jaccard distance, let
\[ j_\mu(c,d)=1- \frac{\sum_i\mu_i\mathbf 1[c,d\in A_i]} {\sum_i\mu_i\mathbf 1[c\in A_i\lor d\in A_i]}, \]
with a fixed convention when the denominator is zero. For two size-\(k\) committees \(X,Y\), define
\[ D_\mu(X,Y)=\min_{\pi:X\to Y\text{ bijective}} \sum_{c\in X}d_\mu(c,\pi(c)). \]
The task is to output two size-\(k\) committees maximizing \(D_\mu(X,Y)\), or decide whether \(D_\mu(X,Y)\ge q\). A solution is a pair of integral committees, together with an optimal matching if a certificate is desired; it is not a fractional committee or a lottery over committees.
The expected result is
\[ \textsc{FarthestCommittees}_{\infty}\in \mathrm{FPT}(\tau+k), \]
with running time \(f(\tau,k)\operatorname{poly}(m,\tau,L)\), where \(L\) is the encoding length of the rational masses. The reason is precisely the structural observation behind Theorem 2. Each candidate has a signature
\[ R(c)=\{i\in[\tau]:c\in A_i\}. \]
There are at most \(2^\tau\) candidate signatures, and candidates with the same signature have identical distances to every candidate. One can enumerate how many candidates of every signature enter each committee and then solve the resulting minimum-weight matching problem. Thus Theorem 2’s finite-voter argument has a natural high-multiplicity version in which the relevant parameter is the number of approval types, not the number of individual voters. I would classify this mirror as Class A, parameterized tractability.
The regime is plausible in recommendation, participatory shortlisting, or large-scale committee selection: a fixed catalogue of \(m\) candidates is evaluated by millions of users, while users fall into relatively few exact approval cohorts generated by common institutional, demographic, or application-specific profiles. The type description is complete because this paper’s distance uses nothing about a voter beyond the candidates they approve. Here \(N\) may be millions while \(\tau\) is moderate. The paper’s \(n=100\) experimental instances are not themselves evidence of this regime, but the same approval-election problem has a perfectly sensible large-cohort interpretation.
The second anchor is Theorem 1, also proved in this paper. It states that FARTHEST COMMITTEES is NP-hard and W[1]-hard with respect to \(k\), even for Hamming or Jaccard distance. The corresponding continuous problem is the decision version of the definition above:
\[ \textsc{FarthestCommittees}_{\infty}^{d} \]
asks, given \((C,T,\mu,k,q)\), whether two size-\(k\) committees \(X,Y\subseteq C\) satisfy \(D_\mu(X,Y)\ge q\), for \(d=h_\mu\) or \(d=j_\mu\).
This is a Class B mirror. If \(\mu_i=a_i/N\), replace type \(A_i\) by \(a_i\) cloned voters. Then normalized Hamming distances are exactly the original Hamming distances divided by \(N\), while Jaccard distances are unchanged. Consequently the maximizing committees, optimal matchings, and threshold answers correspond exactly after scaling \(q\). Conversely, every finite approval election becomes such a rational type distribution by grouping identical approval ballots.
The hardness therefore transfers without any distortion. In the paper’s reduction, the combinatorics live in the candidate set: graph vertices become candidates, and approval patterns encode the biclique instance. The continuous population does not erase that structure. The cited NP-hardness of BALANCED BICLIQUE comes from Garey and Johnson, and its W[1]-hardness from Lin, but Theorem 1’s transfer to FARTHEST COMMITTEES is proved here.
The authors should recognize this as their problem rather than a generic fractional reformulation. Their candidate distance is already defined from approval-set cardinalities, and the paper even discusses normalized Hamming distance. Replacing voter counts by a probability mass over approval ballots changes the society into the continuous object while leaving the committee objective, candidate matching, and Hamming/Jaccard semantics intact. It also avoids the common mistake of making committees fractional merely because voters are divisible.
The mirror covers only the computational results about FARTHEST COMMITTEES: Theorem 1 and Theorem 2. It does not claim to continuize the maps of voting rules, the statistical cultures, the proportionality experiments, or Proposition 1’s pseudometric observation. A natural follow-up is whether the stronger voter-parameter result in Theorem 3 extends to an FPT algorithm parameterized by \(\tau\) alone, using the paper’s fixed-dimension ILP construction over candidate signatures.
The weakest point is that this is a modest mirror. Rational type masses can be denominator-cleared, so much of the model is exactly a high-multiplicity encoding of finite approval elections rather than a new continuous optimization problem. Moreover, Theorem 1’s hardness is candidate-driven, not population-driven. But that is a limitation of novelty, not of legitimacy: the programme explicitly treats high multiplicity as a meaningful instance regime, and Theorem 2 shows that the regime can expose a genuine compression parameter—approval-type count—in the paper’s own farthest-committee problem.
The strongest case against is that this mirror is formally valid but too thin to justify ChoCo’s time. For Theorem 2, once voter types are complete approval ballots, each candidate is represented by its signature \(R(c)\subseteq[\tau]\). Weighted Hamming and Jaccard distances depend only on these signatures and on \(\mu\). Thus the proposed \(f(\tau,k)\operatorname{poly}(m,L)\) algorithm is essentially the paper’s existing finite enumeration argument with repeated voters compressed into weighted types. There is no new mass-transfer problem, separation oracle, or continuous optimization phenomenon.
The same objection applies even more strongly to Theorem 1. For rational masses \(\mu_i=a_i/N\), cloning type \(i\) into \(a_i\) voters reproduces normalized Hamming distances exactly up to scaling, and reproduces Jaccard distances exactly. Conversely, any finite election becomes such a distribution by grouping identical approval ballots. Allowing arbitrary real masses would require an additional real-number or approximation model before “complexity” was even defined. Hence the continuous formulation is either denominator-clearable back to the finite problem or formally underspecified.
One might also argue that enriching the type space cannot rescue the mirror. The distance in the paper uses nothing beyond approval incidence, so approval type is already a complete type. Adding identity, demographics, or private information changes the problem rather than continuizing it; coarsening types changes the distances. The faithful mirror therefore has no additional population structure to study.
That is the best negative case, but it does not defeat the anchors under the programme’s rules. A large electorate of users sharing a modest number of exact approval profiles is a plausible high-multiplicity regime, and the masses remain semantically meaningful even though committees are integral. Theorem 1 is a legitimate Class B mirror, while Theorem 2 exposes a genuine parameter change from individual voters to voter types. The hardness being candidate-driven cannot count against it, and high-multiplicity equivalence is explicitly supporting evidence rather than a novelty objection.
So the honest verdict is that the universal negative claim fails. The mirror is modest and largely a weighted high-multiplicity reformulation, but it is well-posed, plausible, and anchored in two named computational results. At most, this is an argument for ranking it below problems whose continuization creates a richer optimization landscape—not for rejecting it outright.
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.