| paper | Clone structures in voters' preferences |
| authors | Edith Elkind, Piotr Faliszewski, A. Slinko |
| venue | SIGECOM 2012 |
| 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 →
Theorem 6.4
statement extracted from the paper’s text layer
Given a finite candidate set \(C\), a finite set \(T\) of complete ranking types over \(C\), a rational distribution \(\mu\) on \(T\), and an integer \(k\), does there exist a sequence of valid declonings whose pushforward distribution \(\delta_{\#}\mu\) is single-crossing—its positive-mass types admitting an order in which every pairwise preference is a prefix or suffix—and whose resulting candidate set \(C'\) satisfies \(|C'|\ge k\)?
A finite-support high-multiplicity society \((T,\mu)\), where each type \(t\in T\) is a complete ranking and \(\mu_t\) is its population mass; decloning is a discrete candidate operation, masses are aggregated under the induced map, and the objective is to retain at least \(k\) candidates while obtaining a single-crossing type order.
The exact decision problem is invariant under changing positive masses while preserving \(\operatorname{supp}(\mu)\), so the mirror does not exploit aggregate mass computationally.
fatal: False
The mirror covers the NP-completeness result in Theorem \(6.4\), with Proposition \(6.2\) supporting verification of single-crossingness; it leaves the clone-structure characterization, PQ-tree representation, single-peaked decloning algorithm, and fixed-order result in Proposition \(6.5\) alone.
The strongest positive case is a continuous mirror of the paper’s single-crossing decloning problem, anchored on Theorem 6.4, which is proved in this paper. The theorem states:
Given a preference profile \(R\) over a candidate set \(C\) and a positive integer \(k\), it is NP-complete to decide whether there exists a single-crossing profile \(R'\), with \(c(R')\ge k\), that can be obtained from \(R\) by decloning.
The paper proves membership in NP using Proposition 6.2, which says that checking whether a profile is single-crossing is in P, and proves NP-hardness by a reduction from Exact Cover by 3-Sets.
My continuous problem would be Continuous Single-Crossing Decloning.
An instance consists of a finite candidate set \(C\), a finite set \(T\) of complete ranking types over \(C\), a rational mass distribution \(\mu\) on \(T\), and an integer \(k\). Here \(\mu_t\) is the fraction of the electorate having ranking type \(t\), with \(\sum_{t\in T}\mu_t=1\).
A continuous society is called single-crossing if its positive-mass types can be ordered as \(t_1,\ldots,t_\tau\) so that, for every pair of candidates \(c,d\), the types preferring \(c\) to \(d\) form a prefix or a suffix of this order. Equivalently, assign type \(t_i\) an interval of length \(\mu_{t_i}\) on \([0,1]\); every pairwise preference changes at most once along this ideological interval.
The decision variable is a valid sequence of declonings. A decloning replaces a clone set \(D\subseteq C\) by one new candidate in every ranking. The mass is pushed forward accordingly: if several original ranking types become the same ranking after decloning, their masses are added. The question is whether there exists such a sequence producing a candidate set \(C'\) with \(|C'|\ge k\) for which the resulting mass distribution is single-crossing.
This is a faithful continuous version of Theorem 6.4. The candidates remain discrete, clone sets remain exactly the paper’s clone sets, and the operation remains decloning. Only the voter population changes: an explicit list of voters is replaced by masses of indistinguishable ranking types. The single-crossing order is the continuous counterpart of the paper’s order \(\triangleright\) over voters.
A natural regime is a very large electorate divided into ideological or demographic cohorts. Each cohort contains many voters with the same complete ranking over a fixed menu of candidate variants. For example, a national electorate may contain millions of voters but only a moderate number of distinct preference types, while several nearly identical candidates form clone sets. The cohort masses may be represented by rational proportions, and the cohorts can be arranged along a left-to-right ideological axis. This is a genuine high-multiplicity regime: the number of agents is much larger than the number of ranking types, while individual identities do not matter.
The hardness transfers directly. Given a finite profile \(R\), let
\[ \mu_t=\frac{\#\{i:R_i=t\}}{|R|}. \]
Every decloning operation produces the same transformed rankings and the same number of surviving candidates in both formulations. Moreover, a finite profile is single-crossing exactly when its distinct ranking types can be arranged in the continuous prefix/suffix order above. Thus the finite instance is a yes-instance of Theorem 6.4 if and only if its mass-distribution instance is a yes-instance of Continuous Single-Crossing Decloning. Repeating every voter \(M\) times leaves \(\mu\) unchanged while making the physical population \(M|R|\) arbitrarily larger than the number of types. I would therefore expect the finite-support rational version to remain NP-complete: this is a Class B mirror, where the discrete hardness survives continuization.
The authors should recognise this as their problem rather than as a weakened surrogate. The objective is still to preserve as many alternatives as possible while restoring single-crossingness; the only relaxation is replacing repeated voters by their aggregate masses. It does not make candidates fractional, replace decloning by a different intervention, or move continuity into the outcome space.
The mirror covers Theorem 6.4 specifically, not every result in the paper. It also generates useful follow-up questions: does hardness persist when the number of ranking types is bounded; what happens when the ideological order is supplied rather than existential; and can one obtain approximation or fixed-parameter algorithms in terms of \(\tau\), the number of candidates, or the number of clone blocks?
The weakest point is that the hardness reduction is driven mainly by candidate-side clone gadgets, not by voter multiplicity. Consequently, this mirror demonstrates that the continuous-population formulation is meaningful and that hardness can survive it, but it does not yet exhibit the algorithmic advantage of continuization. If the programme demands a mirror in which masses create new LP or convex-optimization leverage, this is a modest case. It is nevertheless a strong, precise continuous analogue of the paper’s central NP-complete problem, and its high-multiplicity interpretation is natural rather than artificial.
The strongest case against this anchor is that its proposed continuum disappears from the mathematics. Theorem \(6.4\) is a real computational result, and the proponent’s finite-to-rational reduction is correct. But the continuous instance is not genuinely a problem about population mass.
Let \(S=\operatorname{supp}(\mu)\). For any decloning sequence \(\delta\), the transformed distribution has support
\[ \operatorname{supp}(\delta_{\#}\mu)=\delta(S). \]
Both relevant conditions depend only on this support:
Consequently, whenever \(\mu\) and \(\nu\) have the same support,
\[ \operatorname{Ans}(\mu,k)=\operatorname{Ans}(\nu,k), \]
even if their masses differ from \(1/2\)–\(1/2\) to \(1-10^{-100}\)–\(10^{-100}\). An arbitrarily small positive cohort has exactly the same logical force as a majority cohort. The mass vector is used only to decide whether a type is present.
This is stronger than saying that continuization fails to make the problem easier. The continuous quantity has no role in the problem at all. The formulation is a support-compressed representation of a finite consecutive-ones problem: duplicate voters can be deleted immediately, and the rational weights can then be discarded. Proposition \(6.2\), the fixed-order variant in Proposition \(6.5\), and the decloning operation all have the same invariance.
Changing the type space cannot repair this while preserving the paper’s problem. With finitely many candidates, every complete-ranking type belongs to the finite set of \(m!\) rankings. Introducing a continuous ideological coordinate merely pushes a distribution forward to those rankings; exact single-crossing still depends only on which ranking regions have positive measure. Making identity, location, or private data relevant would produce a different problem, since the paper’s clone and single-crossing notions do not use them.
A genuinely mass-sensitive rescue would be to allow an \(\varepsilon\)-mass of voters to be discarded or to minimize the mass violating single-crossing after decloning. That could be an interesting robust-repair problem, but it changes both the exact property and the intervention studied in Theorem \(6.4\). It is not the high-multiplicity mirror of the theorem; it is a new population-editing problem.
This objection does not rely on the fact that the hardness survives, which would be an impermissible objection. The transferred NP-hardness is perfectly valid. The issue is that the transfer proves only that a finite support problem can be encoded as a distribution problem. It does not give ChoCo a computational question in which population mass, divisibility, or aggregate uncertainty is operative.
That said, the negative case is not airtight. If ChoCo regards a support-only high-multiplicity quotient as worthwhile in its own right, then the proponent has a legitimate Class B anchor, and Theorem \(6.4\) survives. The strongest honest conclusion is therefore that this is a weak continuous mirror rather than no mirror whatsoever; the universal negative claim cannot be proved from the paper’s structure alone.
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.