| paper | Incomplete Preferences in Single-Peaked Electorates |
| authors | Zack Fitzsimmons, M. Lackner |
| venue | AAAI 2014 |
| 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; polynomial-time solvable in \(m,\tau,L\) if and only if \(\mathrm{P}=\mathrm{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a fixed candidate set \(C\) and a finite-support rational distribution \(\mu\) over partial-order types \(P\) on \(C\), with at least one positive-mass type being a total order, decide whether there exists an axis \(A\) and, for every \(P\) with \(\mu_P>0\), a total-order completion \(L_P\supseteq P\) that is single-peaked with respect to \(A\).
Types are incomplete preference reports \(P\) over fixed candidates \(C\), with population mass \(\mu_P\); decision variables are one common axis \(A\) and one completion \(L_P\) per supported type; the objective is feasibility for all positive-mass types.
The mirror covers Theorems 1 and 2 as hardness results and Theorem 4 as a guided algorithm over supported weak-order types. It leaves the paper's other recognition variants, axiomatic comparisons, structural lemmas, and empirical implementation results without a separate mirror.
There is a credible continuous mirror here, with Theorem 2 as the strongest anchor. The mirror should continuize the population of incomplete-preference reports, not the candidate set, the axis, or the completion operation.
Fix candidates \(C\). Let a type be an information state \(P\): a partial order, local weak order, or weak order over \(C\), together with the interpretation that the missing comparisons may be completed arbitrarily. A society is a finite-support distribution \(\mu\) over such types. Thus \(\mu_P\) is the fraction of the population supplying exactly report \(P\). This is a complete type for the problem: agents with the same \(P\) are indistinguishable for single-peaked consistency.
The natural decision variable is still a finite axis \(A\), a total order on \(C\). A solution consists of \(A\), together with, for every positive-mass type \(P\), a total-order completion \(L_P\) such that \(P\subseteq L_P\) and \(L_P\) is single-peaked with respect to \(A\). Equivalently, the condition must hold for \(\mu\)-almost every agent. There is no fractional axis and no fractional ranking: only the population becomes continuous.
This is a sensible high-multiplicity regime. Imagine a large public consultation over a fixed set of policy alternatives. Different cohorts receive the same restricted questionnaire: one cohort reports \(a\succ c\) and \(b\succ c\), while leaving every other comparison unspecified; another cohort supplies a complete ranking; other cohorts give different comparison patterns. Thousands or millions of respondents may share each report type because they belong to the same questionnaire, demographic, or institutional cohort. The number of agents \(N\) can be much larger than the number \(\tau\) of distinct report types. A finite profile \(P_1,\ldots,P_n\) maps formally to
\[ \mu_P=\frac{|\{i:P_i=P\}|}{n}. \]
Conversely, a rational distribution can be expanded into a finite profile, and then duplicated arbitrarily many times without changing \(\mu\). This is exactly the discrete/high-multiplicity bridge.
My lead problem is Partial-Order Possible-Single-Peaked Consistency\(_\infty\):
Given a candidate set \(C\), a finite-support rational distribution \(\mu\) over partial-order types, and the promise that at least one positive-mass type is a total order, does there exist an axis \(A\) and a completion \(L_P\) for every positive-mass type \(P\) such that every \(L_P\) extends \(P\) and is single-peaked with respect to \(A\)?
This is a direct population version of the paper’s underlying problem. The promise about a total-order type is part of the problem, not an extra modelling convenience: it is the continuous counterpart of the paper’s “even if the profile contains a total order” restriction.
The anchor is Theorem 2, proved in this paper:
“The Partial Order Single-peaked Consistency problem is \(\mathrm{NP}\)-complete, even if the given preference profile contains a total order.”
The theorem says that, given a profile of partial orders, deciding whether there is a common axis and compatible total-order completions making the profile single-peaked is \(\mathrm{NP}\)-complete. The hardness remains even when one vote is already a complete ranking. The proof reduces from Set Splitting. For a Set Splitting instance \((X,Z)\), the construction uses candidates \(X\cup\{x\}\), one partial-order vote \(c_i\succ c_j\) and \(x\succ c_k\) for each triple \(\{c_i,c_j,c_k\}\in Z\), and the complete vote
\[ x\succ c_m\succ\cdots\succ c_1. \]
An axis places the elements of \(X\) on the two sides of \(x\). The partial-order votes ensure that no set in \(Z\) can lie entirely on one side, exactly encoding a valid Set Splitting partition.
The same reduction works for the continuous problem by assigning every constructed type positive rational mass, for example uniform mass after aggregating duplicate types. The existence of an axis is unchanged. Hence Partial-Order Possible-Single-Peaked Consistency\(_\infty\) is expected to be \(\mathrm{NP}\)-complete, in Class B: hardness transfers. The reduction’s combinatorics live in the candidate axis and the Set Splitting instance, not in the number of voters. Replicating every type by a huge cohort therefore preserves the hardness.
A second, narrower hardness mirror is worth keeping because it shows that the phenomenon is not caused by arbitrarily complicated partial orders. Define Local-Weak-Order Possible-Single-Peaked Consistency\(_\infty\) in exactly the same way, but restrict every positive-mass type to be a local weak order.
Its anchor is Theorem 1, proved here:
“Local Weak Order Single-peaked Consistency is \(\mathrm{NP}\)-complete.”
This result concerns profiles whose votes consist of a weak-order component together with completely isolated candidates. The proof reduces from Betweenness. For each constraint \((a,b,c)\), it introduces the two local weak orders
\[ \{a\succ c,\ b\succ c\} \qquad\text{and}\qquad \{b\succ a,\ c\succ a\}. \]
Together they forbid \(c\) from lying between \(a\) and \(b\), and forbid \(a\) from lying between \(b\) and \(c\); consequently \(b\) must lie between \(a\) and \(c\). Thus a common single-peaked axis exists exactly when the Betweenness instance is satisfiable.
In the continuous mirror, these two reports are simply positive-mass local-information cohorts. Again, uniform masses preserve the reduction, so the expected classification is \(\mathrm{NP}\)-complete and Class B. This is a distinct strengthening of the lead: the hardness survives when each incomplete report contains only very sparse comparison information.
There is also a genuine tractable mirror. Define Guided Weak-Order Possible-Single-Peaked Consistency\(_\infty\) by taking a rational distribution over weak-order types and requiring that one positive-mass type be a total order. The question is whether the whole distribution can be completed consistently with one axis.
The anchor is Theorem 4, proved here:
“If the profile contains a total order, the Weak Order Single-peaked Consistency problem can be solved in \(\mathcal O(m\cdot n)\) time.”
The paper’s Guided Algorithm uses the complete vote as a guiding order, then places candidates successively at the left or right end of the developing axis while checking the valley conditions imposed by the other votes. In the continuous version, duplicate voters are represented once, so the same procedure runs in \(\mathcal O(m\cdot\tau)\), apart from reading the rational masses. The expected classification is therefore Class A: a polynomial-time algorithm in the number of candidates and distinct types, independent of the total population size.
The authors should recognise these mirrors as their problems. The central object remains exactly theirs: a common axis, existential completion of every incomplete preference report, and recognition of possible single-peakedness. The distribution merely replaces repeated voters by their mass. This is not an outcome-space relaxation, a probabilistic social-choice model, or a noise model.
The weakest point is that, for the paper’s exact feasibility question, the numerical values of the masses are almost inert. Only whether \(\mu_P>0\) matters. A critic can therefore say that the mirror is support compression rather than a genuinely mass-sensitive problem. That criticism is fair. I would not claim that this paper alone yields a bribery-style continuous optimization problem.
But this weakness also identifies the right next questions rather than invalidating the mirror. A natural mass-sensitive continuation is
\[ \max_A \sum_{P}\mu_P\, \mathbf 1\!\left[ \exists L_P\supseteq P \text{ that is single-peaked with respect to }A \right], \]
which asks for the axis covering the largest fraction of society, or equivalently the minimum mass of reports that must be discarded. That is a continuous analogue of the paper’s discussion of nearly single-peaked profiles and robustness. Other natural variants ask for the best axis under type-dependent elicitation costs, or for parameterized complexity in \(m\), \(\tau\), or the width of the partial orders.
So the strongest honest claim is modest but solid: this paper admits a precise population-continuized recognition problem, with a strong NP-completeness anchor whose hardness transfers and a separate polynomial-time guided regime. The continuous mirror is not yet a weighted optimization theory, but it is a legitimate high-multiplicity computational problem in the paper’s own terms.
The strongest negative case is semantic, but it does not support the universal conclusion.
For any report type \(P\) and axis \(A\), let \(F(P,A)\) mean that \(P\) has a single-peaked completion on \(A\). The continuous feasibility condition is simply
\[ \mu\bigl(\{P:F(P,A)=0\}\bigr)=0. \]
With finite support, this is equivalent to requiring \(F(P,A)\) for every type with \(\mu_P>0\). The numerical masses disappear entirely. A population in which one report has mass \(0.001\) and one in which it has mass \(0.999\) induce exactly the same problem. Thus the proposed mirrors are support compression, not genuinely mass-sensitive continuous models.
This defeats the claimed force of Theorem 2. Its Set Splitting reduction can indeed be assigned positive rational mass, but the masses merely mark which gadget reports are present. Repeating a partial-order report creates no new computational object; it only duplicates the same axis constraint. The complete-order promise also has to be changed from “one voter” to “a positive-mass cohort,” since an isolated complete voter disappears in the continuum. That modification is possible, but it further confirms that the continuous model is not what drives the theorem.
Theorem 1 has the same defect. The two local weak orders associated with each Betweenness triple are constraint gadgets. Giving them positive mass produces the same conjunction of restrictions on the axis. The fact that a questionnaire cohort could plausibly submit the same sparse report is enough to make the high-multiplicity story admissible, but it does not make mass part of the problem. Theorem 4 is weaker still: the Guided Algorithm simply runs after duplicate reports have been removed. The claimed \(\mathcal O(m\tau)\) bound is a data-compression observation, not a continuous algorithm exploiting a society distribution.
A natural repair would be
\[ \max_A\sum_P \mu_P\,\mathbf 1[F(P,A)], \]
or equivalently, minimizing the mass of reports that must be discarded. That would make the population genuinely quantitative and connects to the paper’s discussion of nearly single-peaked profiles. But it is no longer the paper’s recognition problem; it is a new weighted robust-axis problem. Its interest would come from outlier tolerance or weighted optimization, not from continuizing this paper’s theorems. The same is true of elicitation costs or other mass-sensitive extensions.
That is the best negative case: all three proposed anchors collapse to the support of the profile, so none supplies a substantive continuous-population result. But the universal claim still overreaches. The cohort interpretation is coherent, and the weighted robustness variant is a legitimate continuous computational question. I therefore cannot honestly defend “no worthwhile mirror in any scenario”; I can defend only the narrower claim that the three exact mirrors proposed here are too degenerate to justify the programme’s time.
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.