Preferences Single-Peaked on a Circle

The strongest positive case is a two-part mirror: Theorem 7 gives a natural continuous problem whose hardness transfers, while Corollary 14 gives a genuinely tractable high-multiplicity version. The first is the lead.

For both mirrors, the alternatives remain finite. Only the population is continuized. Fix a finite candidate set \(A\) and, where relevant, a common circle \(\mathcal C\) on \(A\). A type is a complete preference description relevant to the rule, and \(\mu_t\) is the fraction of society of type \(t\). Rational masses give the usual high-multiplicity interpretation: \(\mu_t=n_t/n\) represents \(n_t\) copies of type \(t\).

Lead mirror: Continuous SPOC-Kemeny. A type is a complete linear order \(t\) that is single-peaked on the common circle \(\mathcal C\). The population is a rational distribution \(\mu\) over such orders. The decision variable is a consensus ranking \(r\) of \(A\). Its continuous Kemeny score is the expected number of pairwise agreements,

\[ \operatorname{KScore}_{\mu}(r) = \sum_t \mu_t \left| \{(x,y)\in A^2:x\succ_t y\text{ and }x\succ_r y\} \right|. \]

The precise problem is:

Given \(A\), a common circle \(\mathcal C\), a finite explicitly listed support of SPOC types with rational masses \(\mu_t\), and a rational threshold \(q\), decide whether there exists a linear order \(r\) with \(\operatorname{KScore}_{\mu}(r)\ge q\). A solution is such a ranking \(r\); the optimization version asks for one maximizing \(\operatorname{KScore}_{\mu}(r)\).

The anchor is Theorem 7, proved in this paper: given a SPOC profile of linear orders and a number \(k\), it is NP-complete to decide whether there exists a linear order with Kemeny score at least \(k\). The unrestricted NP-completeness used as the source is cited from Bartholdi, Tovey, and Trick (1989), but the transfer to SPOC profiles is proved here.

This theorem transfers directly to the continuous problem. The paper’s Lemma 6 constructs, for every pair of alternatives, a two-voter SPOC gadget with a prescribed majority margin and zero margin on every other pair. Repeating these gadgets realizes any weighted majority tournament using only SPOC votes on one fixed circle. If \(P'\) is the resulting profile and \(P\) is the original unrestricted Kemeny instance, the paper proves that for every ranking \(r\),

\[ \operatorname{KScore}_{P'}(r) = \operatorname{KScore}_{P}(r) + \binom{|A|}{2}\frac{n'-n}{2}. \]

After dividing by \(n'\), the normalized score of the distribution \(\mu'\) induced by \(P'\) is a positive affine transformation of the original score. The threshold can therefore be adjusted exactly. Aggregating repeated votes into rational masses gives a polynomial-size continuous instance, with only \(O(m^2)\) relevant gadget types.

This is a Class B mirror: hardness transfers from the discrete problem. It is not claiming that continuity makes Kemeny easy. That is precisely a useful outcome for the programme, since the continuous formulation identifies a natural boundary where the relaxation does not dissolve combinatorial hardness.

The high-multiplicity regime is credible in settings such as cyclic scheduling. Suppose many employees choose among \(m\) recurring shift times or meeting slots arranged around a daily cycle. Employees in the same contractual, geographic, or organizational cohort may have the same ranking, and the number of cohorts can be much smaller than the number of employees. Kemeny aggregation then asks for the best consensus schedule over the resulting distribution of cyclic preference types. The authors should recognize this as their problem: the ranking variable, pairwise-agreement objective, and SPOC restriction are unchanged; only voter multiplicities are represented by masses.

The main follow-up questions are how the complexity depends on \(m\), the support size \(\tau\), denominator size, and the number of distinct majority margins; whether approximation or parameterized algorithms are possible; and whether the hardness persists under stronger restrictions such as uniform masses or a particularly simple fixed circle.

A second, independent mirror comes from Corollary 14, proved here as an immediate consequence of Theorem 12: for SPOC profiles, Proportional Approval Voting can be computed in polynomial time. More generally, Theorem 12 proves that every OWA-based rule with a scoring vector and non-increasing OWA vector has a polynomial-time winner-determination algorithm on SPOC profiles.

For the continuous PAV problem, a type is an approval set \(A_t\subseteq A\) that is an interval of the common circle \(\mathcal C\). The population is given by rational masses \(\mu_t\). The action is to select a committee \(W\subseteq A\) of size \(k\). With \(H_j=\sum_{\ell=1}^{j}1/\ell\) and \(H_0=0\), the objective is

\[ \operatorname{PAV}_{\mu}(W) = \sum_t \mu_t H_{|A_t\cap W|}. \]

The precise problem is:

Given \(A\), \(k\), a common circle \(\mathcal C\), and an explicitly listed distribution of approval-interval types with rational masses, find a size-\(k\) committee \(W\) maximizing \(\operatorname{PAV}_{\mu}(W)\). A solution is the selected committee \(W\).

This is exactly the high-multiplicity form of PAV. If \(\mu_t=n_t/n\), then the ordinary PAV score of the profile with \(n_t\) copies of type \(t\) is \(n\operatorname{PAV}_{\mu}(W)\), so the maximizing committees are identical.

The polynomial result survives without expanding the masses into \(n\) individual voters. In the paper’s ILP, duplicate voters can be collapsed into one type row, while the coefficient of that type’s contribution in the objective is multiplied by \(\mu_t\). The constraint matrix still has the consecutive- or circular-ones structure used in the total-unimodularity proof. The committee variables therefore remain integral after LP relaxation, and the problem is solvable in time polynomial in \(m\), \(\tau\), and the encoding length of the masses. The committee itself remains discrete; only the population contribution is fractional.

A plausible regime is a large circular city or coastal region choosing \(k\) facility sites. Many residents may share the same interval of acceptable sites because they belong to the same neighborhood or service cohort. The number of residents can be enormous while the number of distinct approval intervals is modest. This uses the paper’s own facility-location motivation and makes the type-level interpretation natural.

Further questions include whether the result survives candidate-specific costs or a budget constraint, which the paper itself identifies as an open direction; whether non-monotone OWA vectors become hard in the continuous setting; and what happens when the type distribution is given implicitly rather than by explicit support.

The scope is deliberately limited. These mirrors cover the paper’s computational results on Kemeny and PAV, not its axiomatic impossibility theorems, forbidden-subprofile characterization, or recognition algorithm. The circle is a finite structure on the alternatives, not the continuous object. The population distribution is the continuous object.

The weakest point is that the Kemeny mirror is, structurally, a weighted reformulation of the paper’s own majority-margin construction. It does not produce a new continuum-specific algorithmic phenomenon; it shows that the high-multiplicity relaxation remains hard. The PAV mirror is likewise a fairly direct compression of the paper’s ILP. But that is a weakness of novelty, not of legitimacy: the paper genuinely studies finite voter profiles, while these questions study distributions over voter types, and the two directions—hardness transfer for Kemeny and LP tractability for PAV—are exactly the kind of complexity landscape the continuization programme is meant to expose.