| paper | The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality |
| authors | H. Aziz, Edith Elkind, Piotr Faliszewski, M. Lackner, P. Skowron |
| venue | IJCAI 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: \(\mathrm{NP}\)-complete when \(k\) is part of the input. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite candidate set \(C\), committee size \(k\), and a rational distribution \(\mu\) over complete ranking types \(\mathcal{T}\subseteq\mathcal{R}(C)\), decide whether there exists \(S\subseteq C\) with \(|S|=k\) such that, for every \(c\notin S\), \(\sum_{t:\,c\succ_t s\ \forall s\in S}\mu_t\leq \frac{1}{k+1}\).
A finite candidate set \(C\), integral committee variable \(S\) of size \(k\), and rational population mass \(\mu_t\) on complete ranking types; the task is feasibility of the local-stability inequalities, with no fractional committee or divisible outcome.
The mirror directly covers Theorems 3, 4, and 5, including weak Gehrlein stability, local stability, and full local stability; it leaves the paper's structural, restricted-domain, and axiomatic results unmirrored.
The strongest mirror is not a fractional committee. The committee remains an integral \(k\)-subset of candidates; what becomes continuous is the electorate supporting it.
Take a finite candidate set \(C\), with voter types \(\mathcal T\subseteq \mathcal R(C)\) consisting of complete rankings, and a rational distribution \(\mu\) over \(\mathcal T\). A type’s mass is the fraction of the population with that ranking. This is plausible for a large parliamentary electorate or membership organisation in which many voters belong to recurring party–ideology–issue blocs. The regime is \(N\gg |\operatorname{supp}(\mu)|\): millions of voters, perhaps hundreds of distinct complete ballot types. The type description is complete because voters sharing a type are indistinguishable for every predicate used in the paper.
My lead anchor is Theorem 4, proved in this paper using the cited NP-completeness of 3-Regular Vertex Cover. It says that, given an election \(E=(C,V)\) and committee size \(k\), deciding whether there exists a locally stable committee of size \(k\) is NP-complete. Here local stability uses the Droop quota \(q=\lfloor n/(k+1)\rfloor+1\): a committee \(S\) is invalid if some excluded candidate \(c\) is preferred to every member of \(S\) by at least \(q\) voters.
The corresponding problem is:
*Local-Stability\(_\infty\)-Existence.* Given \(C\), \(k\), and \(\mu\), does there exist \(S\subseteq C\) with \(|S|=k\) such that, for every \(c\notin S\),
\[ \sum_{\substack{t\in\mathcal T:\\ c\succ_t s\ \text{for every }s\in S}}\mu_t \leq \frac{1}{k+1}? \]
A solution is the committee \(S\). The inequality is exactly the continuous form of the paper’s quota: a violating coalition is any mass strictly greater than \(1/(k+1)\) that unanimously prefers \(c\) to the entire committee.
This is a particularly natural continuization because the paper already defines stability through the size of a voter group. If \(\mu_t=n_t/N\), then
\[ \sum_{t:\,c\succ_t S}\mu_t>\frac{1}{k+1} \]
holds exactly when the corresponding finite group has at least \(\lfloor N/(k+1)\rfloor+1\) voters. Conversely, every rational \(\mu\) can be converted into such a finite election by clearing denominators. Scaling all type counts by an arbitrary factor gives arbitrarily many agents without changing the continuous instance.
I expect Local-Stability\(_\infty\)-Existence to remain NP-hard, hence to fall in Class B rather than Class A. Theorem 4’s reduction is driven by the graph structure of the candidates and by carefully calibrated masses of edge and gadget types. In its construction, the \(xyz\)-voters and edge voters can simply be treated as ranking types with rational masses. The four-voter witnesses and three-voter upper bounds become strict mass comparisons against \(1/(k+1)\). The hardness is therefore not caused by the ability to target individual voters; it survives after individuals have been collapsed into mass.
The first companion anchor is Theorem 3, also proved in this paper. It states that deciding whether an election admits a weakly Gehrlein-stable committee of size \(k\) is NP-complete. A committee is weakly Gehrlein-stable when every member defeats or ties every non-member in the pairwise elections. The theorem reduces from Partially Ordered Knapsack, constructing strongly connected candidate blocks and majority edges encoding the partial order.
Its continuous version is:
*Weak-Gehrlein\(_\infty\)-Existence.* Given \(C\), \(k\), and \(\mu\), does there exist \(S\subseteq C\), \(|S|=k\), such that for every \(c\in S\) and \(d\notin S\),
\[ \sum_{\substack{t\in\mathcal T:\\c\succ_t d}}\mu_t \geq \frac12? \]
Again the solution is the committee \(S\). The majority graph is now computed from population mass rather than voter counts. This is an especially clean mirror: the paper’s predicate is already entirely about pairwise proportions.
I expect hardness to transfer here as well. The reduction’s combinatorics live in the candidate blocks and the majority relation, not in population multiplicity. McGarvey’s finite profiles become rational distributions over rankings, and multiplying all voter counts preserves the same distribution while making every type highly populated. This is a clear Class B boundary: continuization removes voter identities but does not remove the candidate-side knapsack structure.
The second companion anchor is Theorem 5, proved in this paper through a reduction from Multicolored Clique. It states that, given an election and a committee \(S\), deciding whether \(S\) provides full local stability is coNP-complete. Full local stability requires local stability simultaneously for every \(\ell\in[k]\): there must not be a group of at least
\[ \left\lfloor \frac{\ell n}{k+1}\right\rfloor+1 \]
voters and an \(\ell\)-candidate set \(Q\) such that every voter in the group prefers \(Q\) to \(S\) according to the paper’s Pareto-matching definition.
The continuous verification problem is:
*Full-Local-Stability\(_\infty\)-Verification.* Given \(C\), a distribution \(\mu\), and a committee \(S\) of size \(k\), decide whether, for every \(\ell\in[k]\) and every \(Q\subseteq C\) with \(|Q|=\ell\),
\[ \sum_{\substack{t\in\mathcal T:\\ t\text{ prefers }Q\text{ to }S}}\mu_t \leq \frac{\ell}{k+1}. \]
Here a type prefers \(Q\) to \(S\) precisely when there is a bijection from \(Q\) to its \(\ell\) most-preferred members of \(S\), with every member of \(Q\) weakly preferred to its matched committee member and at least one comparison strict.
I expect this continuous problem to remain coNP-complete, and W[1]-hard when parameterized by \(k\), following the paper’s Corollary 8 and its Theorem 5 reduction. A failure certificate is simply \((\ell,Q)\), because the relevant deviating mass is obtained by summing the masses of all types that prefer \(Q\) to \(S\). The Multicolored Clique structure again sits in the candidate gadgets and the possible deviations, so this is transferred hardness rather than continuum-specific hardness.
The authors should recognise all three as their problems. Every voter-count condition in these results is replaced by the corresponding population-mass condition; the ranking language, committee, quota logic, and Pareto comparison are unchanged. This is also genuinely within scope: the society is continuous, while the outcome remains an indivisible committee. The paper’s party-list and proportionality discussion supplies a particularly credible application setting, even though the general mirror should allow arbitrary finite ranking types.
The weakest point is that these mirrors may look like weighted-election reformulations rather than dramatic new continuous models. They do not promise that NP-hardness dissolves; in fact, all three anchors probably remain hard. But that is still a useful positive case for the programme. The continuous question is well-posed, faithful to the paper, and exposes a meaningful boundary: for these stability notions, the hard combinatorics live in candidates and deviations rather than in the multiplicity of individual voters.
The strongest case against these mirrors is that all three are already anonymous weighted-election problems. The proposed continuum contributes no mass transport, fractional allocation, or new optimization object: it merely replaces integer voter counts by rational weights. With explicit support, the input is a finite list of ranking types and weights, and every relevant quantity is a finite aggregate.
For Theorem 3, weak Gehrlein stability depends only on the weighted majority graph
\[ M_\mu(c,d)=\mathbf 1\!\left[\sum_{t:c\succ_t d}\mu_t\ge \frac12\right]. \]
Once this graph is computed, the distribution has disappeared. The reduction’s knapsack structure lives entirely in candidate blocks and graph reachability. A population with millions of voters in recurring preference blocs is plausible, but the continuous model has no computational content beyond constructing a weighted majority graph. A more ambitious version—say, minimum population mass that must change to create a stable committee—would be a new perturbation problem, not a mirror of Theorem 3.
Theorem 4 is only slightly better. For a fixed committee \(S\), local stability depends on the finitely many numbers
\[ a_{\mu,S}(c)=\sum_{t:\,c\succ_t s\ \forall s\in S}\mu_t. \]
The existence question is simply whether some integral \(k\)-subset satisfies \(a_{\mu,S}(c)\le 1/(k+1)\) for every excluded \(c\). The edge and \(xyz\) voters in the reduction can indeed be made into repeated ranking types and scaled arbitrarily, but that shows precisely why this is a weighted reformulation: increasing the population changes nothing. There is no limiting phenomenon and no reason to expect continuous-optimization machinery to enter. Optimizing the worst violation or adding population transfers would be worthwhile problems, but they would be robustness or bribery extensions rather than the paper’s result.
Theorem 5 has the same defect at a higher level. For each \((\ell,Q)\), full local stability depends only on
\[ b_{\mu,S}(\ell,Q) =\sum_{t:\,t\text{ prefers }Q\text{ to }S}\mu_t . \]
The voter group itself is irrelevant; only its total mass matters. The coNP-hardness comes from searching over candidate sets \(Q\) encoding a multicolored clique. Making the electorate continuous neither changes the object being verified nor introduces a meaningful population-side operation. Allowing fractional \(Q\) would make the question more interesting, but would continuize the outcome space, which is outside the programme’s stated goal.
Thus the negative verdict would be: these are not genuinely continuous computational questions but weighted versions of finite-profile questions, with complexity driven wholly by candidates and candidate subsets. They offer no obvious separation problem, configuration LP, or population-level algorithmic boundary. At best they establish that three anonymous multiwinner problems remain hard after voter duplication has been quotiented out.
That case is not airtight under ChoCo’s rules. The paper explicitly permits duplicate rankings, party-list elections give a credible high-multiplicity scenario, and each reduction uses rational voter blocks that can be scaled to arbitrarily large electorates. “The hardness survives” is a legitimate Class B result, not an objection. Consequently, the strongest honest negative conclusion is only that these mirrors are low-yield and vulnerable to a weighted-election novelty collision—not that no worthwhile continuous mirror exists. Theorem 4 in particular survives the attempted attack.
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.