| paper | A Characterization of the Single-Peaked Single-Crossing Domain |
| authors | Edith Elkind, Piotr Faliszewski, P. Skowron |
| venue | AAAI 2014 |
| filed under | voting · structured |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\); decision and construction of inserted blocks, masses, and a witnessing candidate axis take \(O(L+\tau m^2)\) word-RAM time. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given candidates \(C\), a rational distribution \(\mu\) over finitely many complete ranking types \(T\subseteq S_m\), and an order of its positive-mass type blocks, decide whether finitely many added ranking blocks with rational masses \(\eta_j>0\) can be inserted without reordering the original blocks so that the resulting measure \(\nu=\mu+\eta\) is single-crossing and minimally rich, meaning \(\sum_{t:\operatorname{top}(t)=c}\nu_t>0\) for every \(c\); if so, construct the blocks, masses, and a witnessing candidate axis.
A high-multiplicity electorate in which ranking types \(T\) carry masses \(\mu_t\); variables choose inserted ranking blocks, insertion positions, and masses \(\eta_j\), while the objective is feasibility and reconstruction of an MRSC completion.
The completion predicate ignores the magnitudes of \(\mu_t\), and unrestricted positive added mass makes minimum-mass completion degenerate with infimum \(0\); the mirror is therefore support editing rather than mass optimization.
fatal: False
The mirror covers Theorem 10's pre-MRSC recognition and MRSC completion, together with the SPSC interpretation supplied by Theorem 9; it leaves the structural lemmas, Proposition 11, and other domain observations outside the computational mirror.
The strongest honest positive case is a modest Class A mirror anchored in Theorem 10. I would not claim that this paper contains a hardness result: its contribution is structural characterization plus polynomial-time recognition and reconstruction.
The anchor is Theorem 10, proved in this paper. It states that, given an election \(E=(C,V)\), one can decide whether \(E\) is pre-minimally-rich single-crossing (pre-MRSC) and, if so, construct a minimally-rich single-crossing election \(E'=(C,V')\) with \(V\subseteq V'\), in time \(O(nm^2)\). Here, pre-MRSC means that \(E\) can be obtained by deleting voters from an MRSC election. Theorem 9 supplies the semantic bridge, also proved in the paper: an election is single-peaked and single-crossing if and only if it is pre-MRSC.
My mirror would be Continuous MRSC Completion.
There are \(m\) candidates and a finite support of complete ranking types \(T\subseteq S_m\). The society is a rational distribution \(\mu=(\mu_t)_{t\in T}\), where \(\mu_t\) is the fraction of the population with ranking \(t\), \(\sum_t\mu_t=1\). In the natural single-crossing setting, the support types are arranged along a latent ideological or socioeconomic order. Equivalently, the input may include an order \(t_1\prec\cdots\prec t_\tau\); in an order-free version, the algorithm must find such an order.
A continuous profile is single-crossing if, for every pair of candidates \(a,b\), the types preferring \(a\) to \(b\) form a prefix of the order. It is minimally rich if every candidate receives positive top-ranked mass:
\[ \sum_{t:\operatorname{top}(t)=c}\mu_t>0 \qquad\text{for every }c\in C. \]
The action is to add a finite measure of new voter mass \(\eta\), inserting the new ranking blocks anywhere in the existing order while preserving the order of the original population. The resulting measure is \(\nu=\mu+\eta\). The question is whether one can choose \(\eta\) so that \(\nu\) is single-crossing and minimally rich. A solution consists of the added ranking blocks, their rational masses and insertion positions, together with a candidate axis witnessing that every positive-mass ranking is single-peaked. Normalizing \(\nu\) back to total mass \(1\) is immaterial; the original society is simply a subpopulation of the completed society.
For the exact analogue of the paper, the objective is feasibility plus reconstruction. If \(q\) candidates have zero top-ranked mass in \(\mu\), the canonical completion adds one positive-mass block for each of those \(q\) candidates. It uses at most \(m\) added blocks, and this is block-minimal because a ranking block has only one top-ranked candidate. The continuous theorem therefore asks for exactly the same underlying operation as Theorem 10—complete the electorate into an MRSC one—but replaces named voters by mass blocks.
This is a plausible high-multiplicity regime. Consider a large electorate on taxation or public-policy alternatives, with millions of voters grouped into a few dozen or few hundred income, occupation, or ideological brackets. Members of a bracket share the same complete ranking, and the brackets have a natural left-to-right order. Thus \(N\) can be millions while \(\tau\ll N\). The continuous object is genuinely the population: candidates and rankings remain discrete, while voter multiplicities become fractions. The model does not make outcomes fractional and does not introduce probabilistic rankings.
The expected classification is Class A. Theorem 10’s procedure can operate on the \(\tau\) distinct ranking blocks rather than on all \(N\) voters, giving a running time of roughly
\[ \operatorname{poly}(m,\tau,L), \]
where \(L\) is the encoding length of the rational masses. The masses do not affect the single-crossing inequalities except through whether a type has positive mass, so the algorithm is independent of the total electorate size and of the denominators of the population fractions. The output completion is a compact high-multiplicity certificate.
This would not demonstrate that discrete hardness dissolves: recognition is already polynomial in the paper’s finite model. Its value is instead that it turns the paper’s voter-extension theorem into a population-level algorithm whose complexity depends on the number of distinct social types, not on the number of people. It also gives a natural starting point for genuinely continuous optimization questions: minimum-cost mass augmentation to achieve prescribed top-share quotas, maximum-mass deletion restoring SPSC structure, robustness under deletion of a fraction of a type, and simultaneous inference of the voter order and candidate axis.
The weakest point is that the theorem’s combinatorial property is essentially support-based. Replacing \(n\) repeated voters by one type with mass \(\mu_t\) compresses the input, but does not yet make mass itself enter the structural decision. A skeptical referee could therefore call this a high-multiplicity encoding of an already tractable recognition problem rather than a major new continuous-complexity phenomenon. I would concede that. The positive case nevertheless survives: the paper’s central objects are precisely voter deletion, voter insertion, single-crossing order, and single-peaked axes, and all four have direct population-mass counterparts. This is a faithful continuous mirror of Theorem 10, though a modest one rather than a flagship example of hardness disappearing in the continuum.
The proponent has identified the only plausible anchor, but it does not produce a worthwhile continuous-computational problem. Theorem 10 is indeed a named algorithmic result; the difficulty is that its predicate is entirely support-based.
For a society \(\mu\), push the population forward onto its positive-mass ranking types. Single-crossing asks whether those types can be ordered so that every pairwise preference is a prefix; single-peakedness asks whether every supported ranking fits a common candidate axis; minimal richness asks whether every candidate appears as the top of at least one supported type. None of these conditions depends on \(\mu_t\) beyond whether \(\mu_t=0\) or \(\mu_t>0\). Thus the proposed algorithm simply lists each positive-mass type once and runs the paper’s finite algorithm, in time \(\operatorname{poly}(m,\tau)\). The masses and their encoding lengths play no computational role.
This is not an objection that high multiplicity is unnatural. Large electorates grouped into ideological or socioeconomic brackets are perfectly sensible. It is instead a degeneration of this particular continuum: because the paper studies only rankings, every distribution over rankings collapses to its finite support. Adding a latent ideological coordinate does not help unless the coordinate affects the problem; if it does, one has changed the problem rather than continuized this paper’s result.
The proposed completion also has no meaningful mass objective. If candidate \(c\) lacks a top-ranked type, any arbitrarily small positive mass \(\varepsilon\) assigned to a compatible new type suffices. Hence minimum added mass has infimum \(0\), with no optimizer. “One block per missing candidate” minimizes the number of new support atoms, not a continuous quantity, and is a representation-level statement. Imposing positive quotas would repair the degeneracy only by adding a new parameter absent from Theorem 10; the single-crossing constraints still would not interact with the block masses.
The suggested stronger variants do not rescue the anchor. With mass deletion, partially deleting a positive-mass type changes nothing until that type is removed entirely, so an optimum can be chosen by deleting whole support types. That yields a weighted finite support-editing problem, potentially worth studying, but it is not the completion theorem proved here. Likewise, mass-sensitive notions of approximate single-crossing or robustness would be new optimization problems, not continuous versions of the paper’s result.
So the negative case is strong against this anchor: the continuous society is reduced to a finite ordered support, and the mass disappears from the question. I would not honestly claim that every conceivable weighted repair or robustness problem is uninteresting; such a re-engineered problem could be worthwhile. But it would be an additional ChoCo problem, not a worthwhile continuous mirror of Theorem 10 or Theorem 9.
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.