| paper | Robustness Among Multiwinner Voting Rules |
| authors | Robert Bredereck, Piotr Faliszewski, Andrzej Kaczmarczyk, R. Niedermeier, P. Skowron, Nimrod Talmon |
| venue | SAGT 2017 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: NP-hard, already for equal masses. An optimal committee containing the distinguished candidate can be returned when one exists; polynomial time with an NP oracle suffices. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), distinguished candidate \(c^\star\), and a rational distribution \(\mu\) over complete rankings \(t\in S_m\), define \(\operatorname{CC}_\mu(S)=\sum_t\mu_t\bigl(m-\min_{c\in S}\operatorname{pos}_t(c)\bigr)\). Decide whether \(c^\star\in S\) for some \(S\subseteq C\) with \(|S|=k\) maximizing this score, and return such a witnessing committee when one exists.
A high-multiplicity \(\beta\)-CC electorate in which ranking types \(t\in S_m\) carry masses \(\mu_t\), committees remain integral, and the objective is the mass-weighted representative Borda score; the decision variable is the committee \(S\), with membership of \(c^\star\) queried.
Theorem 10 is covered exactly through the normalized \(\beta\)-CC membership problem. Theorem 7 is covered as a plausible \(k\)-Borda mass-transport extension, and Theorem 9 as a repaired mass-robustness question without an established hardness transfer. The robustness-level propositions, STV-specific results, experiments, and other rule-specific results remain unmirrored.
The strongest honest case is a high-multiplicity mirror of the paper’s \(\beta\)-CC results, with robustness as the genuinely population-continuous extension.
Consider a large professional association choosing a committee of \(k\) candidates. Millions of members submit rankings, but many use the same complete ranking template because they occupy the same role, region, or institutional constituency. A type is therefore a complete ranking \(t\in S_m\), and \(\mu_t\) is the fraction of members using it. The intended regime has \(N\gg\tau\), where \(N\) is the population size and \(\tau\) is the number of distinct ranking types.
My lead anchor is Theorem 10, proved in the paper’s appendix. It states that \(\beta\)-CC Member is \(\theta_2^p\)-complete: given an election, committee size \(k\), and distinguished candidate \(c^\star\), deciding whether \(c^\star\) belongs to some winning Chamberlin–Courant committee is \(\theta_2^p\)-complete. The paper proves membership using polynomially many non-adaptive NP queries and proves hardness by reduction from Vertex Cover Member on regular graphs.
The direct continuous problem is:
Continuous \(\beta\)-CC Member. Given \(m\), \(k\), a distinguished candidate \(c^\star\), and a rational distribution \(\mu\) over complete rankings, define
\[ \operatorname{CC}_\mu(S) = \sum_{t}\mu_t \left(m-\min_{c\in S}\operatorname{pos}_t(c)\right) \]
for every committee \(S\subseteq C\) of size \(k\). Ask whether \(c^\star\in S\) for some committee \(S\) maximizing \(\operatorname{CC}_\mu(S)\).
The solution is a yes/no answer together with a witnessing committee when the answer is yes. This is recognisably the authors’ problem: committees remain integral, rankings remain complete, and only the electorate is represented by type masses.
This mirror is Class B. Given any finite election with \(n_t\) voters of type \(t\), set \(\mu_t=n_t/n\). Then
\[ \operatorname{CC}_\mu(S) = \frac{1}{n}\operatorname{CC}_V(S), \]
so winner sets, ties, and candidate membership are preserved exactly. Conversely, rational masses can be cleared to denominators and realised as a finite high-multiplicity election. Thus the paper’s \(\theta_2^p\)-hardness transfers directly. The hard combinatorics lie in candidate selection and the vertex-cover structure, not in the individuality of voters. The continuous formulation is also computationally meaningful because it gives a succinct representation of an electorate with potentially enormous multiplicities.
The more ambitious mirror is anchored in Theorem 9, also proved in the paper. It states that \(\beta\)-CC Robustness Radius is NP-hard and W[1]-hard when parameterized by the committee size, even when the robustness radius is one. The reduction is from Regular Multicolored Independent Set and uses committee size \(h+2\); the graph’s independent sets correspond to alternative winning committees, while a single adjacent swap can change the set of winning committees.
Its continuous version should use mass transport rather than an arbitrary perturbation norm. Given \(\mu\), let \(x_{t,t'}\) be the mass converted from ranking type \(t\) to ranking type \(t'\). The resulting society is
\[ \mu'_{t'}=\sum_t x_{t,t'}, \qquad \sum_{t'}x_{t,t'}=\mu_t, \]
and the intervention cost is
\[ \operatorname{cost}(x) = \sum_{t,t'} d_{\mathrm K}(t,t')x_{t,t'}, \]
where \(d_{\mathrm K}\) is Kendall–\(\tau\) distance, equivalently the number of adjacent swaps needed to convert \(t\) into \(t'\). Define
\[ \mathcal W_\mu = \arg\max_{|S|=k}\operatorname{CC}_\mu(S). \]
The problem, Continuous \(\beta\)-CC Robustness Radius, asks for the minimum cost of a coupling \(x\) such that
\[ \mathcal W_{\mu'}\neq \mathcal W_\mu. \]
A solution is the mass-transfer plan together with the resulting changed winner family. This is a natural population analogue of the paper’s robustness radius: one adjacent swap applied to one voter has normalized cost \(1/N\), whereas changing a positive fraction of a large electorate has a nonvanishing cost.
I would expect this problem to be Class B, because the paper’s independent-set gadget is driven mainly by committee structure and candidate-side interactions. But this expectation requires a new proof. The paper’s one-swap hardness does not automatically survive fractional transfers: infinitesimal mass can break a tie, and fractional mass can simulate a fractional independent-set choice. The appropriate follow-up is therefore a margin-stable version, or a reduction with strict score gaps that forces transferred mass to behave like integral selector choices. That is a real open continuous-complexity question, not something the paper itself establishes.
For contrast, Theorem 7 supplies a clean algorithmic anchor. Proved in the paper, it states that Robustness Radius is polynomial-time solvable for SNTV, Bloc, and \(k\)-Borda. The corresponding continuous problem is:
Continuous \(k\)-Borda Robustness Radius. Given a rational ranking distribution \(\mu\), committee size \(k\), and rational budget \(\varepsilon\), determine whether there is a mass-transfer plan of Kendall cost at most \(\varepsilon\) that changes the top-\(k\) Borda committee family.
Here
\[ \operatorname{Borda}_\mu(c) = \sum_t \mu_t\bigl(m-\operatorname{pos}_t(c)\bigr). \]
I expect this version to be Class A. To change the outcome, some committee candidate \(p\) and noncommittee candidate \(d\) must cross the relevant Borda boundary. For a fixed pair, the effect of moving mass from ranking \(t\) to ranking \(t'\) is linear:
\[ \Delta_{t,t'}(p,d) = \bigl(\operatorname{Borda}_{t'}(p)-\operatorname{Borda}_{t'}(d)\bigr) - \bigl(\operatorname{Borda}_{t}(p)-\operatorname{Borda}_{t}(d)\bigr). \]
Because Borda depends only on positions, not the entire order of the other candidates, the possible target states for \(p\) and \(d\) can be represented with polynomially many position pairs. The minimum-cost mass needed to cross each boundary is then a rational fractional-knapsack or LP computation, followed by enumeration of candidate pairs. This should give a polynomial algorithm in \(m\), the number of represented types, and the encoding length of the masses.
The mirror deliberately covers only Theorems 7, 9, and 10. It does not claim that the paper’s robustness-level propositions, experiments, or every STV result have continuous counterparts. Theorem 10 is my strongest anchor: it gives an exact high-multiplicity mirror with hardness transferring cleanly. Theorem 9 supplies the more programme-defining mass-intervention problem, while Theorem 7 shows a plausible tractable boundary.
The weakest point is the robustness anchor. The atomless model removes the paper’s one-voter granularity, and Theorem 9’s \(B=1\) result may collapse because an arbitrarily small mass shift can alter a tie. That is a serious qualification. It does not undermine the lead mirror, however: Continuous \(\beta\)-CC Member remains a faithful, compressed population problem whose \(\theta_2^p\)-hardness survives exactly, while the robustness formulation creates a substantive next question about whether fractional population interventions dissolve or preserve the paper’s hardness.
The negative case is not ultimately defensible. The robustness anchor is genuinely vulnerable, but the other two survive the strongest objections.
Theorem 9 does not transfer directly. Its hardness is tied to a single integral adjacent swap and delicate ties. Under the proposed atomless transport model, an arbitrarily small mass transfer can break a tie, so the robustness radius may have infimum \(0\) without attaining a minimum. Requiring a positive intervention threshold or a margin-stable winner would repair the definition, but that creates a new robustness problem rather than a direct continuous counterpart of the theorem. The paper therefore supplies no hardness evidence for this mirror.
Theorem 7 is stronger than the proponent’s case needs. For \(k\)-Borda, changing the committee can be expressed as making some outsider’s score meet or exceed some boundary member’s score. For each pair \(p,d\), mass transfers produce linear changes in the Borda gap and incur Kendall transport costs. This yields a fractional-knapsack or linear-programming formulation over the ranking types. The fact that the answer may be polynomial is not an objection: it is exactly the kind of Class A result the programme seeks.
Most decisively, Theorem 10 is a valid high-multiplicity mirror. For every rational distribution \(\mu\),
\[ \operatorname{CC}_{\mu}(S)=\frac{1}{N}\operatorname{CC}_{V}(S) \]
after clearing denominators, so winning committees and membership are preserved exactly. Ranking types fully describe everything \(\beta\)-CC uses; voter identity disappears without loss. A professional association with many members sharing ranking templates is a credible high-multiplicity regime, and the distribution is a compressed representation of a potentially enormous electorate.
Calling this “only a weighted restatement” would conflict with the programme’s rules: high-multiplicity equivalence and transferred hardness are intended deliverables, not collisions. Thus the honest conclusion is that the proposed continuous robustness question needs substantial redesign, but the \(\beta\)-CC Member mirror—and probably the \(k\)-Borda tractability mirror—survive. A universal negative case cannot defeat all three anchors.
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.