| paper | Voting in Two-Crossing Elections |
| authors | Andrei Constantinescu, Roger Wattenhofer |
| venue | IJCAI 2022 |
| filed under | voting · structured |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Corollary 8
Given a finite candidate set \(C\), ranking types \(T\subseteq L(C)\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), a piecewise-constant circular witness \(\varphi:\mathbb S^1\to T\) whose pairwise preference sets are circular intervals, and a target \(c^\star\), decide whether some minimizer of \(K_\mu(\pi)=\sum_{t\in T}\mu_t d_{\mathrm{KT}}(\pi,t)\) ranks \(c^\star\) first.
A high-multiplicity society is represented by ranking types \(T\) and masses \(\mu\), with \(\varphi\) certifying the two-crossing domain; the decision variable is a candidate ranking \(\pi\), and the objective is mass-weighted Kendall–tau disagreement \(K_\mu(\pi)\).
The formulation supplies a circular witness or promise but does not provide a corresponding continuous recognition algorithm or settle complexity under compressed witnesses.
fatal: False
The mirror directly captures Corollary 8's Kemeny hardness and gives a weaker mass version of Theorems 9–10 for Young; it leaves Theorem 6's recognition algorithm, Theorem 14's Chamberlin–Courant algorithm, and the axiomatic tournament results aside.
The strongest positive case is that this paper admits a genuine population-continuous version of its two-crossing model, and that the resulting problems naturally split between Class B and Class A. My lead anchor is the hardness result, because it tests whether continuity actually dissolves the paper’s discrete complexity.
Take a finite set \(T\subseteq L(C)\) of complete ranking types. A continuous two-crossing society consists of a distribution \(\mu\) over \(T\), together with a circular population coordinate. Formally, let \(\varphi:\mathbb S^1\to T\) be piecewise constant on finitely many rational-length arcs, with
\[ \mu_t=\lambda\bigl(\{z\in\mathbb S^1:\varphi(z)=t\}\bigr), \]
where \(\lambda\) is normalized arc length. For every pair \(c,c'\), require
\[ \{z:c\succ_{\varphi(z)}c'\} \]
to be a circular interval, up to measure-zero boundaries. This is the exact continuous counterpart of the paper’s observation that two-crossing is equivalent to each pairwise preference set being circularly consecutive. A ranking type may occur on several arcs; those arcs are not different types, merely different locations occupied by agents with the same relevant description.
The natural regime is a large election or public consultation with \(N\) in the millions, but only \(\tau\ll N\) recurring complete rankings: for example, a population distributed along a horseshoe-shaped ideological spectrum. This is especially plausible because the paper’s Lemma 2 explicitly identifies circle-distance preferences as two-crossing. A mass \(\mu_t\) is then the fraction of the population with ranking \(t\), not a probability over outcomes and not a noise model.
My lead problem is Two-Crossing Kemeny Winner\(_\infty\).
An instance consists of \(C\), a finite list of ranking types \(T\), rational masses \(\mu_t\), a finite circular witness \(\varphi\), and a target candidate \(c^\star\). For a ranking \(\pi\in L(C)\), define its population Kemeny cost by
\[ K_\mu(\pi)=\sum_{t\in T}\mu_t\,d_{\mathrm{KT}}(\pi,t), \]
where \(d_{\mathrm{KT}}\) is Kendall–tau distance. The question is whether there exists a Kemeny-optimal ranking \(\pi\) with \(c^\star\) in its first position. A solution is either a negative answer or an optimal ranking witnessing that \(c^\star\) is a Kemeny winner.
This is not a weakened problem. It is exactly Kemeny’s objective with voter multiplicities replaced by population masses. The weighted majority margins are simply
\[ M_\mu(c,c') = \sum_{t\in T}\mu_t \bigl([c\succ_t c']-[c'\succ_t c]\bigr), \]
so the continuous instance induces the same weighted majority tournament as any finite realization of \(\mu\).
The relevant anchor is Corollary 8, proved in this paper. It states that determining Kemeny winners is NP-hard even under two-crossing elections. The restricted hardness is proved here; the underlying unrestricted hardness of Kemeny is prior work. The mechanism is Theorem 7, also proved here: every weighted majority tournament with same-parity weights can be induced by a two-crossing election. Replacing each voter in that construction by a mass of \(1/N\), and aggregating identical rankings into \(\mu\), merely scales every Kemeny score by \(1/N\). The winner is unchanged.
Therefore Two-Crossing Kemeny Winner\(_\infty\) should be expected to be NP-hard, with hardness transferring from the discrete problem: Class B, not continuum-specific hardness. The reduction’s combinatorics live in the number of candidates and the majority tournament, not in the number of named voters. At the same time, the construction can be realized by arbitrarily many agents sharing the same finite collection of rankings, so this is compatible with a genuine high-multiplicity regime.
This anchor raises useful questions rather than ending the programme: does hardness remain with a compressed circular witness or very small support \(\tau\)? What is the parameterized complexity for fixed \(m\) or fixed \(\tau\)? What approximation and rounding guarantees connect rational \(\mu\) to a finite \(N\)-voter election?
A second, independent mirror comes from Theorem 9, proved in this paper; Theorem 10 gives a sharper running-time bound. The theorem says that weak and strong Young scores can be computed in polynomial time for two-crossing profiles.
The continuous weak version is Two-Crossing Young Mass Score\(_\infty\). Given \((C,T,\mu,\varphi,c^\star)\), choose retained masses \(x_t\) with \(0\le x_t\le\mu_t\), maximizing
\[ \sum_{t\in T}x_t \]
subject to
\[ \sum_{t\in T}x_t \bigl([c^\star\succ_t c]-[c\succ_t c^\star]\bigr)\ge0 \qquad \text{for every }c\neq c^\star. \]
The score is the minimum removed mass,
\[ 1-\max\sum_t x_t. \]
Equivalently, the action is to remove or abstain a fraction of the population so that \(c^\star\) becomes a weak Condorcet winner. The output is the optimal retained-mass vector and the resulting score.
This is a particularly natural continuization: the paper’s \(0\)-\(1\) decision \(x_v\) for keeping voter \(v\) becomes a fractional retained mass. The constraints and objective remain exactly the same pairwise-majority conditions. The continuous problem is therefore tractable by linear programming, hence Class A. The two-crossing structure additionally explains why the discrete problem has a totally unimodular formulation; the continuous version exposes the underlying mass optimization directly.
The main follow-up questions are how tightly this score rounds to the integer Young score for a finite population, how to formulate a useful strong-Condorcet version without strict-inequality pathologies, and what happens when participation costs or other attributes are incorporated into the type.
The weakest point is the circular witness. The distribution \(\mu\) alone has no canonical population order; the continuous model must either include a piecewise-constant circular witness or be posed as a promise problem saying that one exists. The paper supplies such an order algorithmically for finite profiles through Theorem 6, but it does not establish a corresponding continuous recognition theorem. That is a real open component of the mirror. It does not undermine the Kemeny case, however: the horseshoe interpretation is already present in the paper, the Kemeny objective is exactly mass-weighted Kendall disagreement, and Corollary 8’s hardness survives normalization and aggregation.
The strongest negative case is against the Young anchor, not the Kemeny anchor.
For Young, replacing each binary variable \(x_v\) by a retained mass \(x_t\) produces
\[ \max \sum_t x_t \]
subject to linear pairwise-majority constraints and \(0\le x_t\le \mu_t\). But this LP is polynomial for every finite type distribution, whether or not the society is two-crossing. The paper’s real content—the circular consecutive-ones structure and total unimodularity—has disappeared after aggregation. Thus the proposed problem is a valid fractional deletion problem, but it is a weak mirror of Theorems 9 and 10: it measures the generic ease of nonatomic intervention, not the algorithmic significance of two-crossingness. Adding removal prices preserves this objection; the problem remains an ordinary LP. Requiring whole-type deletion would restore combinatorial content, but that is a different, discrete high-multiplicity problem rather than the proposed continuous one.
That argument does not defeat the anchor completely. A population-level Young score is still a legitimate computational question, and strictness in the strong version can be handled by taking an infimum or imposing a margin threshold. So Young is merely a weak anchor, not an invalid one.
The Kemeny anchor is much harder to defeat. The obvious objections fail. The circular witness need not be an individual attribute; it is a latent certificate of the domain restriction, just as in the paper. Repeated rankings on separate arcs do not violate the type definition, because location is not used by Kemeny’s objective. And supplying the witness or asking for it to be recognized are both legitimate formulations of an existential domain restriction.
More decisively, for rational masses the proposed problem is exactly the normalized high-multiplicity version of the paper’s problem. If \(\mu_t=n_t/N\), replace type \(t\) by \(n_t\) voters in the witnessed circular order. Then for every candidate ranking \(\pi\),
\[ K_\mu(\pi) = \sum_t \mu_t d_{\mathrm{KT}}(\pi,t) = \frac{1}{N}\sum_{v=1}^{N}d_{\mathrm{KT}}(\pi,\succ_v). \]
Thus the set of Kemeny-optimal rankings, and hence whether \(c^\star\) can be first, is unchanged. Theorem 7’s construction can be converted in exactly this way: duplicate voters become mass, and its two-crossing witness becomes a piecewise-constant circular population map. No individual identity is used by Kemeny, and the objective does not degenerate when each agent has measure zero.
One could complain that this is “only” a high-multiplicity reformulation, or that the two-crossing promise becomes decorative because Theorem 7 realizes arbitrary weighted tournaments. But the programme explicitly treats high multiplicity as the intended bridge, and explicitly counts hardness that survives continuity as a worthwhile Class B outcome. Those therefore cannot serve as objections here.
So the honest negative conclusion is limited: the Young mirror is structurally uninformative, and the continuous recognition problem for a weighted circular witness remains unspecified. But the first anchor survives every stronger version of those objections. I cannot make a credible universal case that this paper has no worthwhile continuous mirror; Corollary 8 already supplies one.
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.