| paper | Computational Aspects of Nearly Single-Peaked Electorates |
| authors | G. Erdélyi, M. Lackner, A. Pfandler |
| venue | AAAI 2013 |
| 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}\text{-complete}\), even for \(\tau\le 8\) with all masses integer multiples of \(1/8\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6.9
statement extracted from the paper’s text layer
Given candidates \(C\), ranking types \(T\), a rational distribution \(\mu\) over \(T\), and a rational budget \(b\), decide whether there exist an axis \(A\) and nonnegative transfers \(x_{\pi,\rho}\) such that \(\sum_{\rho}x_{\pi,\rho}=\mu_\pi\), \(x_{\pi,\rho}=0\) whenever \(\rho\notin\operatorname{SP}(A)\), and \(\sum_{\pi,\rho}d_K(\pi,\rho)x_{\pi,\rho}\le b\).
Types are complete rankings \(\pi\in T\); \(\mu_\pi\) is their population mass; \(x_{\pi,\rho}\) transfers mass to single-peaked rankings \(\rho\) on a common axis \(A\); the objective is total mass-weighted Kendall–tau cost.
The mirror covers the Global Swaps and Local Swaps consistency results and the supplied-axis evaluation result in Theorem 6.21. It leaves the other distance measures, their interrelations, structural propositions, and Candidate Partition consistency untouched.
My strongest case is a continuous mirror of the paper’s Global Swaps problem.
The paper’s anchor is Theorem 6.9, proved in this paper: Global Swaps Single-Peaked Consistency is NP-complete. Its instance is an election \(E=(C,P)\) and an integer \(k\); the question is whether at most \(k\) adjacent-candidate swaps, distributed arbitrarily across the votes, can transform \(P\) into a profile that is single-peaked with respect to some axis. The theorem is proved by reduction from Kemeny Optimal Aggregation; the Kemeny hardness result is cited from earlier work, but Theorem 6.9 itself is established here.
The corresponding continuous problem is Continuous Global-Swaps Single-Peaked Consistency. Let \(T\) be the set of complete rankings of \(C\), and let the society be a rational distribution \(\mu\) over \(T\). A unit of mass represents voters with the same ranking. For an axis \(A\), let \(\operatorname{SP}(A)\subseteq T\) be the rankings single-peaked on \(A\). We may transfer mass from an input type \(\pi\) to an output type \(\rho\), paying Kendall–tau cost \(d_K(\pi,\rho)\).
Formally, a solution consists of an axis \(A\) and nonnegative transfers \(x_{\pi,\rho}\) satisfying
\[ \sum_{\rho\in T}x_{\pi,\rho}=\mu_\pi \]
for every input type \(\pi\), with \(x_{\pi,\rho}=0\) whenever \(\rho\notin\operatorname{SP}(A)\). Its cost is
\[ \sum_{\pi,\rho\in T} d_K(\pi,\rho)x_{\pi,\rho}. \]
The optimization problem is to minimize this cost over all axes and transfers; the decision version asks whether the cost is at most a rational budget \(b\).
This is a genuine population continuization. Candidates and rankings remain discrete, and the axis remains a discrete permutation. What becomes continuous is the society and the amount of mass whose ranking is corrected. It is also exactly the paper’s question: “How many adjacent swaps are needed to make the electorate single-peaked?” becomes “What fraction of the electorate must undergo how much ranking correction?”
A plausible regime is a large electorate whose ballots come from repeated ideological or demographic cohorts. The number of voters \(N\) may be in the millions, while the number of distinct ranking types \(\tau\) is much smaller. Every member of a cohort has the same ranking and the same unit adjacent-swap cost, so treating the cohort as mass is precisely the high-multiplicity assumption rather than an artificial loss of identity.
The expected classification is Class B: hardness transfers. For a fixed axis \(A\), the continuous optimum is
\[ \sum_{\pi\in T}\mu_\pi \min_{\rho\in\operatorname{SP}(A)}d_K(\pi,\rho). \]
There is no capacity constraint coupling different source types, so splitting a type’s mass cannot improve on sending it to a nearest single-peaked ranking. If a finite profile \(P\) has \(n_\pi\) voters of type \(\pi\), and \(\mu_\pi=n_\pi/n\), then
\[ \operatorname{GS}_\infty(\mu) = \frac{\operatorname{GS}(P)}{n}. \]
Thus an algorithm for the continuous problem would solve the paper’s discrete problem after normalizing the vote counts. The correspondence remains valid in a genuinely high-multiplicity regime: replicate every voter type \(R\) times. The number of agents becomes \(Rn\), but the type distribution and the normalized optimum are unchanged. The hard combinatorics remain in the candidate arrangement and the choice of axis, not in population multiplicity.
A second, independently defensible mirror uses Theorem 6.8, also proved in this paper: Local Swaps Single-Peaked Consistency is NP-complete. Here the discrete question is whether every vote can be made single-peaked with respect to one common axis using at most \(k\) adjacent swaps in that vote. The theorem is proved through the paper’s reduction from Minimum Radius, whose hardness is cited from Frances and Litman.
The continuous problem, Continuous Local-Swaps Single-Peaked Consistency, has input \(C\), a rational type distribution \(\mu\), and \(k\). It asks whether there are an axis \(A\) and transfers \(x_{\pi,\rho}\) such that
\[ \sum_{\rho}x_{\pi,\rho}=\mu_\pi, \]
every used output ranking satisfies \(\rho\in\operatorname{SP}(A)\), and every used transfer satisfies
\[ d_K(\pi,\rho)\le k. \]
This says that every infinitesimal voter may change at most \(k\) adjacent pairs, while the resulting population is single-peaked. Splitting mass does not weaken the condition: a type is feasible exactly when it has at least one single-peaked ranking within Kendall distance \(k\). Consequently, for normalized finite profiles,
\[ \operatorname{LS}_\infty(\mu)\le k \quad\Longleftrightarrow\quad \operatorname{LS}(P)\le k. \]
This second mirror is therefore also expected to be NP-hard by direct transfer. It reinforces the interpretation that the hardness comes from finding a compatible candidate axis, not from having individually named voters.
The scope is deliberately limited. These mirrors cover the paper’s global- and local-swap consistency results, not every distance measure, and they do not reinterpret single-peakedness as a continuous outcome space. The paper’s evaluation results also suggest a useful boundary: once the axis is supplied, the corresponding weighted continuous evaluation problem should remain polynomial-time solvable by the same dynamic-programming ideas behind Theorem 6.21. The difficult part is selecting the axis.
The weakest point is that these mirrors may be criticized as weighted, normalized versions of finite profile problems rather than dramatic LP collapses. I think that criticism is fair. In particular, the discrete hardness reductions do not themselves require many repeated types. The response is that repetition can be added without changing the problem, and the resulting model asks a natural high-multiplicity question: what minimum population mass must be corrected before a latent one-dimensional ideological structure appears? Even when hardness survives, that is a meaningful ChoCo result: it identifies a problem where continuization does not dissolve the combinatorics because the obstruction lives in the alternative set and axis geometry rather than in population indivisibility.
The strongest negative case is that these mirrors are exact frequency encodings rather than genuinely new continuous-population problems. For a fixed axis \(A\), the proposed global-swap objective decomposes as
\[ G_A(\mu)=\sum_{\pi}\mu_\pi \min_{\rho\in \operatorname{SP}(A)} d_K(\pi,\rho). \]
There is no coupling between source types, so splitting mass creates no new option. For a finite profile with \(n_\pi\) voters of type \(\pi\),
\[ G_\infty(\mu)=\frac{\operatorname{GS}(P)}{n}. \]
The local-swap version is even more plainly support-wise:
\[ L_A(\mu)=\max_{\pi:\mu_\pi>0} \min_{\rho\in\operatorname{SP}(A)}d_K(\pi,\rho). \]
Thus both proposed “continuum” problems merely replace a list of voters by rational weights. They expose no population-level coupling, indivisibility phenomenon, or new mass-transport choice. Adding cohort budgets or other coupling constraints would create a more interesting problem, but it would no longer be the paper’s Global Swaps or Local Swaps problem.
That is the best available objection, but it does not defeat the anchors under the programme’s rules. Exact high-multiplicity reformulations are expressly in scope, and “continuity does not help” is itself not a disqualification. The paper’s costs depend only on rankings, so ranking types are complete types; the objectives do not track individual identity; and swap costs do not collapse in the atomless limit.
The multiplicity objection also fails. Remark 6.10 gives Global Swaps hardness with only eight voters. Repeating those eight ballot types arbitrarily many times produces a genuinely large electorate with bounded type support, while preserving the normalized problem exactly. The paper therefore supplies a particularly clean high-multiplicity regime, not merely a padded arbitrary profile.
Theorem 6.21 does not rescue the negative case either: with a supplied axis, its dynamic program yields the weighted continuous evaluation problem by summing per-type costs for Global Swaps and checking the support-wise bound for Local Swaps. That is another legitimate, if modest, continuous question.
So the honest negative verdict is weak. These mirrors may be Class B results with limited prospect of an LP collapse, but that is a possible outcome of the programme, not a modelling defect. I cannot defeat either Theorem 6.9 or Theorem 6.8, and therefore cannot sustain the universal claim that this paper has no worthwhile continuous mirror.
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.