Diversity of Structured Domains via k-Kemeny Scores

There is a credible mirror, and my strongest anchor is Theorem 3.1.

The natural type is a complete ranking \(v\) of the candidates. Fix a societal axis \(\lhd\) and a balanced group-separating tree \(\mathcal T\), and let \(\mathcal D=\mathrm{SP}(\lhd)\cap\mathrm{GS}(\mathcal T)\). A continuous society is a rational mass distribution \(\mu\) over \(\mathcal D\), where \(\mu_v\) is the fraction of the population with ranking \(v\). The action is to choose two representative rankings \(R=\{r_1,r_2\}\), exactly as in the paper; representatives need not themselves lie in \(\mathcal D\). The objective is the average swap distance

\(K^{(2)}_\mu=\min_{\{r_1,r_2\}\subseteq\mathcal L(C)}\sum_{v\in\mathcal D}\mu_v\min\{\swap(v,r_1),\swap(v,r_2)\}.\)

The continuous decision problem, which I would call \(\textsc{Continuous-2-Kemeny}_{\mathrm{SP}\cap\mathrm{GS/bal}}\), asks whether \(K^{(2)}_\mu\le q\), for a rational threshold \(q\), and returns the two rankings attaining the minimum.

This is a sensible high-multiplicity regime. Imagine a large electorate with a fixed, moderate candidate set, a common left-right axis, and recurring preference cohorts: party supporters, regional blocs, or institutional constituencies whose members have identical rankings for every purpose relevant to \(k\)-Kemeny. The population may contain millions of voters but only \(\tau\) distinct ranking types, with \(n\gg\tau\). In the paper’s reduction there are \(2m\) candidates and at most \(2^m\) aligned ranking types, so repeated cohorts are entirely plausible even though the worst-case reduction need not itself have repeated strings.

Theorem 3.1 states that \(k\)-Kemeny is \(\mathrm{NP}\)-complete even for \(k=2\) and elections whose votes are simultaneously single-peaked and balanced group-separable. This theorem is proved in the paper, by reduction from Hypercube 2-Segmentation. Its underlying question is precisely whether two rankings can serve as representatives with total adjacent-swap cost at most a given threshold.

The continuous version preserves the problem exactly. If a finite election \(E\) has \(n_v\) voters of type \(v\), set \(\mu_v=n_v/n\). Then

\(K^{(2)}_\mu=\frac{1}{n}\kappa_E(2).\)

Thus an election with \(\kappa_E(2)\le q\) is equivalent to a continuous society with \(K^{(2)}_\mu\le q/n\). The discrete problem embeds directly into the mass problem, so I would expect hardness to transfer: this is a Class B mirror, with the combinatorics living in the candidate-ranking geometry rather than in the individuality of voters. The paper’s authors should recognise this as their own question, since they explicitly describe \(k\)-Kemeny as a clustering problem and already normalize scores by \(|V|\).

This is not a collision with the paper’s statistical cultures. Those cultures are distributions used to sample finite elections; the finite election remains the computational object. Here \(\mu\) is the society itself, and the swap objective is integrated over population mass. Likewise, treating a domain as an election with one copy of each vote is not the same as allowing arbitrary high-multiplicity mass distributions.

A second, more tractable mirror is anchored in Corollary 3.4. The corollary states that, for every fixed dimension \(d\) and fixed \(k\), \(d\)-Embeddable \(k\)-Kemeny is polynomial-time solvable. The problem considered there gives a \(d\)-Euclidean election, an embedding function for the candidates, and a threshold \(q\), and asks whether there is a set of \(k\) rankings from the induced Euclidean domain whose total \(k\)-Kemeny score is at most \(q\). This result is established in the paper using the fact that a fixed-dimensional Euclidean domain contains only \(O(m^{2d})\) rankings.

The continuous problem is \(\textsc{Continuous-}d\textsc{-Euclidean-}k\textsc{-Kemeny}\). The instance consists of candidate points \(x:C\to\mathbb Q^d\), the induced ranking-type set \(\mathcal D_x\), and a rational mass distribution \(\mu\) over \(\mathcal D_x\). The question is whether there are \(k\) rankings \(R\subseteq\mathcal D_x\) such that

\(\sum_{v\in\mathcal D_x}\mu_v\min_{r\in R}\swap(v,r)\le q.\)

The regime is a large population of residents or consumers distributed in a fixed-dimensional policy or geographic space, with candidate locations fixed. Ideal-point space is partitioned into preference cells; every resident in one cell has the same complete type, namely its induced ranking. For fixed \(d\), there are only \(O(m^{2d})\) such types, so a very large population naturally becomes a mass distribution over relatively few cells.

I would expect this mirror to remain polynomial for fixed \(d\) and \(k\). Enumerate the \(O(m^{2d})\) realizable rankings, enumerate \(k\)-subsets, and evaluate the weighted swap objective. Rational masses only replace integer counting by exact rational addition. The resulting complexity is polynomial in the candidate count, the number of represented types, and the encoding length of the masses. This gives a genuine Class A mirror.

The weakest point is that both mirrors replace a finite sum by a weighted sum, so the opposing case can fairly say that the new problem is a weighted or high-multiplicity reformulation of \(k\)-Kemeny rather than a radically new model. I would concede that. But here that is also the correct abstraction: the paper’s objective depends only on rankings and pairwise swap distances, never on voter identities, arrival times, or other individual attributes. Treating recurring ranking cohorts as masses therefore preserves the authors’ problem rather than weakening it. The lead result remains especially strong because the exact continuous analogue inherits Theorem 3.1’s hardness, while the Euclidean anchor shows that the same continuization can expose a clean tractable regime.