| paper | Core-Stable Committees Under Restricted Domains |
| authors | Grzegorz Pierczy'nski, P. Skowron |
| venue | WINE 2022 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,k,L\) on each of the four promised domains. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Corollary 2
Given candidates \(C\), committee size \(k\), finite voter types \(\Theta\), rational masses \(\mu_\theta\), and a promised restricted-domain witness, output a committee \(W\subseteq C\) with \(\lvert W\rvert=k\) such that no mass vector \(\lambda\) with \(0\leq\lambda_\theta\leq\mu_\theta\) and no candidate set \(B\subseteq C\) with \(\lvert B\rvert\leq k\sum_\theta\lambda_\theta\) satisfies that every type with \(\lambda_\theta>0\) lexicographically prefers \(B\) to \(W\).
A finite-support high-multiplicity society represented by \(\mu\), with integral committee \(W\) as the decision variable and \(\lambda,B\) as a proportional blocking certificate; the objective is to find any mass-core committee efficiently.
With finitely many candidates and ordinal types, an atomless geographic continuum collapses to its pushforward distribution over types, so the mirror may offer compression rather than new population-dependent combinatorics.
fatal: False
The mirror covers the polynomial-time core-construction results for voter-interval, candidate-interval, single-peaked, and single-crossing populations, plus \(\extord^{\max}\)-core verification; it leaves the structural characterizations, counterexamples, and standard lexicographic membership question largely untouched.
I think there is a credible mirror here, with the strongest version keeping the committee itself discrete and continuizing only the electorate. The most natural setting is a large facility-location or representative-body problem in which many residents have exactly the same approval set or ranking over a fixed set of candidate facilities. The number of residents \(N\) is very large, while the number of distinct preference types \(\tau\) is moderate.
Let \(C\) be the candidates and \(k\) the committee size. A type \(\theta\) is a complete approval set \(A_\theta\subseteq C\), or a complete strict ranking \(r_\theta\) of \(C\). The society is a rational distribution \(\mu\in\mathbb{Q}^{\Theta}\), where \(\mu_\theta\) is the fraction of residents of type \(\theta\). For approval profiles, the positive-mass types should satisfy VI or CI; for strict profiles, they should satisfy single-peakedness or single-crossingness, with the relevant witnessing order supplied or found as a preprocessing step.
The continuous core problem is the following. Choose a genuinely discrete committee \(W\subseteq C\) with \(|W|=k\) such that there is no coalition of mass \(\lambda(\Theta)\), where \(0\leq\lambda_\theta\leq\mu_\theta\), and no candidate set \(B\subseteq C\) satisfying
\[ |B|\leq k\lambda(\Theta) \]
for which every type with \(\lambda_\theta>0\) lexicographically prefers \(B\) to \(W\). Equivalently, the question is whether a proportional mass of the population can jointly replace \(W\) by a smaller set \(B\) that every member of that mass prefers. This is exactly the paper’s core definition with \(|S|/n\) replaced by population mass. The outcome is not fractional: \(W\) remains a set of \(k\) candidates. Any fractional committee used by the algorithm is only an internal certificate, as in the paper.
My lead anchor is Corollary 2, proved in this paper. It states that the core is always non-empty and can be found in polynomial time for four domains: voter-interval and candidate-interval approval profiles, and single-peaked and single-crossing strict profiles. The result is supported by the paper’s proved Theorem 2 for approval LC elections and Theorem 3 for strict recursive single-top-crossing elections. Thus the paper is not merely asserting existence: it supplies the CommitteeCore algorithm.
The corresponding problem is Restricted-Core-Find\(_\infty\):
I expect this to be Class A: tractable. CommitteeCore has a natural weighted version. BestRepresentative processes population mass in the relevant order, assigning each infinitesimal unit to its best still-available candidate; candidate \(c\) becomes full after representing mass \(1/k\), so the internal fractional value is \(p(c)=k\) times represented mass. A type may be split at such a boundary without changing anyone’s preferences. The median phase then uses mass quantiles rather than voter indices. With rational masses, this should run in time polynomial in \(m\), \(\tau\), and the encoding length of \(\mu\), rather than in the expanded population size.
This is a plausible continuation of the authors’ question, not a relaxation that discards it. The candidates, committee size, lexicographic comparison, domain restrictions, and proportional blocking condition all remain intact. Only the cardinality of a coalition becomes its mass. A facility-location interpretation is especially convincing: many households in the same neighbourhood may have the same ranking over possible facility sites, and VI, CI, or single-peakedness can arise from geography. A political or ideological interpretation gives the analogous single-crossing regime.
The second anchor is Proposition 5, also proved here. It states that, under the \(\extord^{\max}\) preference extension, deciding whether a given committee belongs to the core is polynomial-time solvable: one checks each candidate \(c\notin W\) and counts the voters who prefer \(c\) to every member of \(W\), comparing that count with the quota \(\lceil n/k\rceil\).
Its continuous analogue is Max-Core-Membership\(_\infty\). Given \((C,k,\Theta,\mu)\) and a committee \(W\), define
\[ \rho_W(c)= \sum_{\theta:\,c\succ_\theta w\text{ for every }w\in W}\mu_\theta . \]
Under the exact continuous core quota, \(c\) blocks \(W\) whenever \(\rho_W(c)\geq 1/k\). Therefore the membership question is decided by computing \(\rho_W(c)\) for every \(c\notin W\). This is plainly polynomial in \(m\), \(\tau\), and the encoding length of the masses. It is a separate mirror from the first one because it concerns verification rather than construction, and because the paper explicitly treats the \(\extord^{\max}\) extension separately from the standard lexicographic extension.
The high-multiplicity bridge is exact for rational profiles. If \(\mu_\theta=n_\theta/n\), expanding each type into \(n_\theta\) identical voters gives the corresponding discrete election. Conversely, aggregating identical voters gives \(\mu\). The continuous formulation therefore asks for the compressed, high-multiplicity version of the paper’s problem, not for a probabilistic outcome or a smoothed profile. Existing high-multiplicity work would support the modelling premise rather than create a novelty objection.
There is also an honest boundary. Theorem 4, proved here, gives a strict top-monotonic election with empty core. Its six symmetric voter groups can be assigned mass \(1/6\), preserving the same blocking argument for \(k=7\). So I would not claim that every continuous top-monotonic population has a core. The mirror should cover the domains in Corollary 2, and perhaps recursive single-top-crossing, while treating unrestricted top-monotonicity as a negative boundary case.
My weakest point is that the paper contains no comparable NP-hardness result whose difficulty might dissolve under continuization. Its central result is already polynomial-time, so the continuous mirror may be viewed as a weighted generalization of an existing algorithm rather than a dramatic new complexity landscape. The authors also already use fractional committees internally, which could invite the objection that the paper is “already continuous.” The reply is that the proposed problem does not continuize the committee or its outcomes: it keeps \(W\) integral and makes the population itself the continuous object. Still, the computational novelty is modest. The strongest positive claim is therefore not that this paper reveals a new hardness transition, but that its core-stability theorem has a natural, exact, compressed-population analogue whose algorithm should operate on masses and type classes rather than on named voters.
The strongest case against the mirror is that this paper has no genuinely population-dependent computational object to continuize. Its core is anonymous: once candidates are fixed, a voter matters only through her approval set or ranking. Thus any population—finite, very large, or literally atomless—projects exactly to a finite vector of masses over preference types. A continuum of geographic locations would add nothing unless locations affected utilities beyond the ordinal preferences, which would be a different problem.
This makes Corollary 2, and its supporting Theorems 2 and 3, a weak anchor for ChoCo. The proposed weighted CommitteeCore algorithm is entirely plausible: process types with cumulative masses, split a type when a \(1/k\) quota is reached, and replace median voters by mass quantiles. For rational masses, one can also clone the types into a sufficiently large finite election and recover the same statement. But this is essentially a weighted implementation of the existing proof. The paper already performs the relevant fractional assignment internally; replacing \(k/n\)-sized increments by rational mass increments introduces no new optimization problem, separation problem, or population-level combinatorics. It is a sensible high-multiplicity reformulation, but its main contribution would be an exact weighted restatement of an existing polynomial algorithm.
The natural “better” version using a continuum of ideological or geographic positions does not rescue the mirror. With finitely many candidates and ordinal preferences, the position measure is computationally visible only through its pushforward distribution over finitely many rankings or approval sets. If positions themselves are to matter, one must add cardinal utilities, distances, or a continuum of candidate sites; that changes the paper’s core problem rather than continuizing its electorate.
Proposition 5 is an even weaker anchor. Its continuous analogue is literally the same computation after collecting equal terms:
\[
\rho_W(c)=
\sum_{\theta:\,c\succ_\theta w\ \forall w\in W}\mu_\theta.
\]
The discrete proposition counts voters satisfying a predicate; the proposed version sums their masses. This is a useful compressed representation, but not a new computational question generated by continuization.
One could instead promote the paper’s open Question 2 and study lexicographic core membership over a mass distribution. That would be more substantial, but its difficulty would come from searching over candidate sets \(T\), not from replacing voters by mass. Aggregating identical types preserves the entire search problem exactly. The resulting question may be worthwhile, but its contribution would be a solution to lexicographic core membership, not a meaningful continuous-population phenomenon.
Theorem 4 also transfers unchanged: assign mass \(1/6\) to each of its six voter groups and the same blocking argument proves emptiness. This confirms that continuous notation can faithfully reproduce the paper’s examples, but it does not create a new boundary or mechanism.
This is not a novelty-collision claim, and it is not the mistaken objection that high-multiplicity elections are illegitimate. The high-multiplicity regime is perfectly sensible here. The negative claim is narrower: for this paper, the regime appears to yield compression and weighted bookkeeping, while the paper contains no result whose computational content is transformed by making the population continuous. That is a respectable reason to decline the mirror if ChoCo requires a new complexity landscape.
Still, the universal negative is not airtight. The weighted core theorem is well-posed, and a polynomial algorithm in \((m,\tau,L)\) could be useful when the expanded electorate is enormous. If that kind of exact high-multiplicity algorithm counts as a worthwhile contribution, then Corollary 2 survives; I do not see an honest fundamental obstruction that defeats it.
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.