| paper | The Complexity of Election Problems with Group-Separable Preferences |
| authors | Piotr Faliszewski, A. Karpov, S. Obraztsova |
| venue | IJCAI 2020 |
| filed under | voting · structured |
| 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: \(\mathrm{NP}\)-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Corollary 2
statement extracted from the paper’s text layer
Given candidates \(C\), a committee size \(k\), a rational distribution \(\mu\) over complete ranking types consistent with a group-separable clone decomposition tree \(G\), and a rational threshold \(\theta\), decide whether there is an integral committee \(W\subseteq C\) with \(|W|=k\) such that \(\sum_{\sigma}\mu_{\sigma}\min_{c\in W}(\operatorname{pos}_{\sigma}(c)-1)\le\theta\).
A high-multiplicity society whose ranking types \(\sigma\) carry masses \(\mu_{\sigma}\), with an integral committee \(W\) of size \(k\) as the decision variable and expected Borda dissatisfaction \(\sum_{\sigma}\mu_{\sigma}\min_{c\in W}(\operatorname{pos}_{\sigma}(c)-1)\) as the objective.
The mirrors cover the NP-hardness results for YOUNG-SCORE and CC-SCORE. They leave the moderate-height algorithms, the other control problems, and the remaining structural analysis untreated.
A strong positive case exists, and my lead mirror is the paper’s Young-score result.
The relevant anchor is Proposition 1, proved in this paper: “YOUNG-SCORE is NP-hard even for group-separable elections.” The problem asks, given an election, a candidate \(p\), and an integer \(t\), whether at most \(t\) voters can be deleted so that \(p\) becomes a weak Condorcet winner. The paper proves this by reducing from bounded-occurrence X3C. For \(X=\{x_1,\ldots,x_{3k}\}\) and a family of 3-sets \(\{S_1,\ldots,S_m\}\), it creates candidates \(X\cup\{p\}\), one voter \(X\setminus S_i\succ p\succ S_i\) for each set, and \(m-k-4\) additional voters ranking \(p\) first. All rankings are consistent with a caterpillar \(Q\)-tree, hence are group-separable. Deleting at most \(k\) voters makes \(p\) a weak Condorcet winner exactly when \(k\) sets cover \(X\).
My continuous problem is Continuous Group-Separable Young-Score. An instance consists of candidates \(C\), a target \(p\), a group-separable clone decomposition tree \(G\), and a rational population distribution \(\mu\) over complete rankings \(\sigma\) consistent with \(G\). Thus \(\mu_\sigma\) is the fraction of the population having ranking \(\sigma\), with \(\sum_\sigma\mu_\sigma=1\). Given a rational \(q\), ask whether there are deletion masses \(d_\sigma\), with \(0\le d_\sigma\le\mu_\sigma\) and \(\sum_\sigma d_\sigma\le q\), such that \(p\) is a weak Condorcet winner in the residual population. Equivalently, writing \(\nu_\sigma=\mu_\sigma-d_\sigma\), require, for every \(c\neq p\),
\[ \sum_{\sigma:p\succ_\sigma c}\nu_\sigma \;\ge\; \sum_{\sigma:c\succ_\sigma p}\nu_\sigma. \]
A solution is the vector of deleted masses \(d\); the optimization version minimizes \(\sum_\sigma d_\sigma\).
This is a faithful population mirror. A type is a complete ranking, and many agents share that ranking because they occupy the same position in a common feature hierarchy. The natural regime is a large election or representative consultation with a fixed candidate set and repeated ideological or demographic ranking types: \(n\gg\tau\), where \(\tau\) is the number of distinct rankings in the support. The paper’s own X3C construction already has one ranking type per set plus a filler type; replicating every type produces arbitrarily large electorates without changing the underlying combinatorics.
The continuous problem is in Class A. It is the linear program
\[ \min \sum_\sigma d_\sigma \]
subject to the deletion bounds and the \(m-1\) pairwise inequalities above. The group-separable restriction is retained, although the LP does not need it. The paper’s NP-hardness comes from choosing indivisible voters: a set-voter is either deleted or retained. In the mirror, deletion mass can be divided among identical types, so the X3C selection gadget becomes a rational polyhedron. This is precisely the kind of population-multiplicity hardness that continuization is meant to dissolve.
The high-multiplicity bridge is also exact in the intended sense. A finite election with \(n_\sigma\) voters of type \(\sigma\) becomes \(\mu_\sigma=n_\sigma/n\). Conversely, a rational continuous witness can be scaled by a common denominator into a finite replicated electorate. For a fixed finite electorate, the continuous optimum is a relaxation of the integer deletion problem; with moderate \(\tau\), it should support additive rounding and preprocessing for the discrete problem.
A second, useful anchor is Corollary 2, proved here by adapting the cited hardness constructions: “CC-SCORE, PLURALITY-CCAC, and PLURALITY-CCDC are NP-hard even for group-separable elections.” I use only the CC-SCORE entry. CC-SCORE asks whether there is a size-\(k\) committee \(W\) whose Borda-based Chamberlin–Courant dissatisfaction is at most \(t\). The paper explains that the hardness construction partitions candidates into “real” candidates \(A=\{a_1,\ldots,a_n\}\) and grouped dummy candidates \(D\), with rankings of the form
\[ a_i\succ a_j\succ D_x\succ C\setminus(D_x\cup\{a_i,a_j\}), \]
which are consistent with a caterpillar \(Q\)-tree.
Its continuous mirror is Distributional Group-Separable CC-SCORE. The input is \(C\), committee size \(k\), a rational distribution \(\mu\) over group-separable ranking types, and a rational threshold \(\theta\). The question is whether there exists an integral committee \(W\subseteq C\), \(|W|=k\), such that
\[ \operatorname{dissat}_\mu(W) = \sum_\sigma \mu_\sigma \min_{c\in W} \bigl(\operatorname{pos}_\sigma(c)-1\bigr) \le \theta. \]
The solution is the committee \(W\); committees are not fractional.
This second mirror is expected to be Class B. Given any finite election, aggregate identical rankings and set \(\mu_\sigma=n_\sigma/n\). Its CC dissatisfaction is exactly the discrete dissatisfaction divided by \(n\). Hence the paper’s group-separable hardness transfers by rational normalization. Replicating every voter type yields the same decision problem with arbitrarily high multiplicity. Here the combinatorics live in the candidate-side choice of \(W\), not in the individuation of voters, so continuity does not remove the hardness.
The two anchors therefore give a useful pair: Proposition 1 exhibits a genuine Class A collapse, while the CC-SCORE row of Corollary 2 shows that the mirror remains computationally meaningful and can preserve hardness. Neither mirror continuizes the outcome space: Young’s intervention still deletes population mass, and CC still chooses an ordinary \(k\)-element committee.
The main weakness is that the Young mirror could be dismissed as merely “weighted Young,” and the CC mirror as merely a weighted restatement. That objection would be serious if the weights were arbitrary modelling decoration. Here they are population proportions, obtained by aggregating indistinguishable voters, and the hardness construction itself survives arbitrary replication of types. The other qualification is representation: the LP is polynomial in the explicitly represented support size \(\tau\), not necessarily in a compact description of all \(m!\) rankings. Those are legitimate follow-up questions about encoding and high-multiplicity regimes, but they do not undermine the lead mirror.
I would therefore submit Continuous Group-Separable Young-Score as the main question for the programme, with Distributional Group-Separable CC-SCORE as a supporting Class B mirror.
The strongest negative case defeats the first anchor’s novelty, but not the existence of a mirror.
For Proposition 1, the proposed Continuous Group-Separable Young-Score is exactly the natural mass version of Young score: delete population mass until \(p\) becomes a weak Condorcet winner. It is a valid high-multiplicity model, and the objection cannot be that fractional deletion is artificial. However, the programme brief already identifies Young’s rule as an earlier continuous LP example. Moreover, group-separability contributes nothing to the proposed LP: the constraints use only the pairwise masses \(p\succ c\) and \(c\succ p\), so adding a clone-decomposition tree merely restricts the instances. Thus this is best viewed as an already-solved weighted Young problem, not a new mirror supplied by this paper. An implicitly represented distribution over all rankings could create a new pricing problem, but that would require a new encoding and new results not suggested by Proposition 1.
Corollary 2’s CC-SCORE anchor is much harder to defeat. The proposed problem keeps the committee \(W\) integral and continuizes only the electorate:
\[ \operatorname{dissat}_\mu(W) = \sum_\sigma \mu_\sigma \min_{c\in W}\bigl(\operatorname{pos}_\sigma(c)-1\bigr). \]
That is precisely a continuous population model, not outcome-space fractionalization. Voters with the same complete ranking are indistinguishable, population mass is meaningful, and rational finite elections map exactly to rational distributions. There is no identity-dependent objective and no degeneracy in the limit.
Calling this merely a weighted restatement would not defeat it: high-multiplicity aggregation is the programme’s intended bridge. Nor is it an objection that the hardness remains because the committee is an integral candidate-side object; that is exactly a legitimate Class B outcome, and the programme explicitly treats such hardness transfers as informative.
Consequently, the universal negative case cannot honestly be sustained. Proposition 1 is probably redundant with the programme’s existing continuous Young treatment, but the CC-SCORE mirror survives as a well-posed, paper-anchored Class B question. One surviving anchor is enough, so I would not recommend a negative verdict.
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.