d4-conf-ijcai-2015-0386

The strongest honest mirror is narrow and comes from Theorem 3.3, proved in this paper. Given a collection of votes \(V\) and a societal axis \(L\), it gives polynomial-time algorithms to compute: (1) the smallest \(k\) for which \(V\) is a \(k\)-maverick-SP society with respect to \(L\); (2) the smallest \(k\) for which it is a Dodgson\(k\)-SP society; and (3) the smallest \(k\) for which it is a PerceptionFlip\(k\)-SP society. It also gives a polynomial-time algorithm to decide whether \(V\) is swoon-SP. That is a named computational result in the paper; my case does not rely on its unnumbered table entries.

A plausible regime is a large election or ballot survey on an issue with a known candidate axis: millions of voters, but perhaps hundreds or thousands of distinct rankings. A type is one complete ranking, and its mass is the fraction of voters with that ranking. This treats identical ballots as genuinely interchangeable for the properties in Theorem 3.3, and expresses the extent of deviation in per-capita terms.

I would ask the authors to study the Continuous Axis-Distance Profile. An instance consists of candidates \(C\), an axis \(L\), and a finite support \(S\) of rankings with rational masses \(\mu_t>0\) summing to \(1\). The output has four coordinates. First, compute the minimum mass that must be removed to leave only single-peaked rankings:
\[ \kappa_{\mathrm{mav}}(\mu,L)= \min \sum_{t\in S}r_t \quad\text{such that}\quad 0\le r_t\le\mu_t,\qquad \mu_t-r_t=0\ \text{for every }t\notin\mathrm{SP}(L). \]
Here \(\mathrm{SP}(L)\) is the set of rankings single-peaked with respect to \(L\). This is the lead coordinate: it is the continuous version of the theorem’s smallest number of maverick voters, measured as a fraction of the society.

The other coordinates mirror the theorem’s remaining clauses. Let \(\operatorname{KT}\) denote adjacent-swap distance. Report
\[ d_{\mathrm{Dodg}}=\max_{t\in S}\min_{\pi\in\mathrm{SP}(L)}\operatorname{KT}(t,\pi), \]
and
\[ d_{\mathrm{PF}}=\max_{t\in S}\min_{L':\,t\in\mathrm{SP}(L')} \operatorname{KT}(L,L'). \]
Finally, report whether every supported ranking becomes single-peaked with respect to the restricted axis after its top-ranked candidate is removed—the continuous society’s swoon-SP test. These maxima are deliberate: the paper’s Dodgson\(k\)-SP and PerceptionFlip\(k\)-SP conditions require every voter to meet the same bound, so replacing the maximum with an average would change the question.

I expect this profile to be tractable. The maverick coordinate is the sum of the masses of non-single-peaked types. For the typewise distance coordinates and the swoon test, run the paper’s algorithms on each supported ranking and take the appropriate maximum or conjunction; then do rational arithmetic on the masses. With \(m\) candidates, support size \(\tau\), and mass bit length \(L\), this gives polynomial time in \(m,\tau,L\). It is a direct high-multiplicity formulation: a discrete election with \(n_t\) voters of type \(t\) has \(\mu_t=n_t/n\), while the continuous input allows those proportions to be given directly.

The authors could reasonably recognize this as their problem: the paper explicitly computes how far a society is from single-peakedness, and the mirror changes the unit from a voter count to a population fraction. This case covers Theorem 3.3 only; it does not claim to mirror the manipulation or control complexity results in Tables 1–3. Its weakest point is that Theorem 3.3 is a tractable measurement result, and most of its coordinates depend on which types occur rather than on their masses. So this is a credible continuous-population mirror, but not evidence that continuization changes the complexity of the paper’s harder attacks. Natural follow-ups are to measure mass-weighted repair cost instead of a worst-case distance, or to ask what changes when the axis must be inferred rather than supplied.