Putting a Compass on the Map of Elections

The strongest honest positive case is narrow: a Class A mirror of Section 3’s election-recovery problem. This paper has no named NP-hardness, coNP-hardness, W[1]-hardness, FPT, or approximation-complexity result, so there is no credible hardness-led mirror. The useful anchors are its two explicit polynomial-time reconstruction propositions.

Take \(C\) to be the candidate set and let a type be a complete ranking \(\pi\in S_C\). A continuous society is a rational distribution \(\mu=(\mu_\pi)_{\pi\in S_C}\), where \(\mu_\pi\) is the fraction of voters of type \(\pi\). Its sufficient statistic for this paper is the bistochastic frequency matrix \(X^\mu\), with \(x^\mu_{i,c}=\sum_{\pi:\operatorname{pos}_\pi(c)=i}\mu_\pi\). Thus the continuum changes the population representation; rankings remain integral, and no outcome space is fractionalized.

The plausible regime is a large election or repeated organizational ballot with \(N\) voters but only \(K\) substantially represented ranking templates, where \(N\gg K\). For example, party-line or institutionally standardized ballots might have millions of voters but only dozens of recurring complete rankings. The paper itself need not use this scenario: its explicit claim that elections and frequency matrices may be treated interchangeably provides the bridge.

My lead anchor is Proposition 2, the proposition named freqtopos, proved in this paper. It states: given an \(m\times m\) bistochastic matrix \(X\) and an integer \(n\), one can compute in polynomial time an election \(E\) with \(n\) voters and position matrix \(P\) satisfying \(\lvert nx_{i,j}-p_{i,j}\rvert\le 1\) for every \(i,j\); among matrices satisfying these coordinate bounds, the algorithm minimizes \(\sum_{i,j}\lvert nx_{i,j}-p_{i,j}\rvert\). The main text gives a dependent-rounding proof, and the appendix gives a deterministic minimum-cost-flow implementation.

The corresponding continuous problem is:

Best finite realization of a continuous frequency matrix. Given candidates \(C\), a rational continuous society \(\mu\) represented by its bistochastic matrix \(X^\mu\), and an integer \(n\), choose a compressed \(n\)-voter election—ranking types with integer multiplicities summing to \(n\)—whose position matrix \(P\) minimizes \(\sum_{i,c}\lvert nx^\mu_{i,c}-p_{i,c}\rvert\), subject to \(\lvert nx^\mu_{i,c}-p_{i,c}\rvert\le1\) for all \(i,c\). A solution is the list of rankings and multiplicities, not an explicit list of \(n\) voters.

This is a genuine population mirror of the paper’s question: start with a mass distribution, then find the best finite realization at a prescribed resolution. It is not merely “the outcomes are fractional.” The decision variable is the finite population representation, while the objective measures how faithfully it preserves the aggregate positional behaviour. I would expect this problem to be tractable, namely Class A, by Proposition 2’s rounding and flow machinery. It also gives a clean high-multiplicity interpretation: \(n\) is a discretization scale, not the source of combinatorial difficulty.

The supporting anchor is Proposition 1, the proposition named polyalgo, proved here algorithmically. It states: given an integer position matrix \(X\in\mathcal P(m)\), one can compute in \(O(m^{4.5})\) time an election \(E\) containing at most \(m^2-2m+2\) distinct votes such that \(\#\operatorname{pos}(E)=X\). The underlying decomposition fact is attributed to Leep and Myerson’s Theorem 7, but the paper supplies the matching-based algorithm and runtime.

Its continuous counterpart is:

Exact type compression. Given a rational bistochastic matrix \(X\) and an integer \(n\) such that \(nX\) is integral, find a distribution \(\widehat\mu\) over complete rankings, supported on at most \(m^2-2m+2\) types, satisfying \(X^{\widehat\mu}=X\). Equivalently, output ranking types with integer multiplicities whose position matrix is exactly \(nX\).

This is again Class A. Proposition 1 gives an exact compressed representative. For \(m=10\), the support bound is \(82\), while a general ranking space has \(10!\) possible types; in a regime with millions of voters and a small number of recurring ballot types, that compression is a meaningful computational object. Proposition 2 handles the nonintegral case, while Proposition 1 handles exact realizability when denominators permit it.

The authors should recognize both mirrors as their problems because Section 3 explicitly asks for the reverse direction—from a frequency or position matrix back to an election—and the paper repeatedly treats elections and frequency matrices interchangeably. The mirror therefore preserves the paper’s central object, the positionwise aggregate, rather than inventing a simpler voting rule. It covers the recovery and discretization results of Section 3, but not the empirical map, the compass visualizations, or the normalized Mallows experiments.

It also generates natural follow-up problems: computing positionwise distance directly between two continuous societies; finding the closest point on a compass path; fitting a normalized Mallows parameter to a continuous profile; and determining the minimum mass perturbation needed to cross a compass-region boundary.

The weakest point is substantial: this mirror is a compressed representation problem, not bribery, control, winner determination, or robustness. It does not show discrete hardness dissolving, because the paper supplies no discrete hardness result to begin with. Moreover, the output preserves only the position matrix, not the full ranking distribution \(\mu\). Thus this is a defensible but modest positive case: the paper contains a real continuous-population analogue of its algorithmic recovery problem, with explicit polynomial-time anchors, but not a flagship ChoCo complexity mirror.