| paper | Drawing a map of elections |
| authors | Stanislaw Szufa, N. Boehmer, Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, P. Skowron et al. |
| venue | AI 2025 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: The decision problem is in \(\mathrm{P}\); an optimal bijection and optimal position-transport plans are computable in polynomial time in the binary input length. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 3.2
statement extracted from the paper’s text layer
Given equal-sized candidate sets \(C,D\) and finitely supported rational societies μ and ν over complete rankings of \(C\) and \(D\), compute an optimal candidate bijection δ and position-transport plans minimizing \(∑_{c∈C}\operatorname{EMD}(p^μ_c,p^ν_{δ(c)})\), where \(p^μ_{c,i}=∑_{π:\operatorname{pos}_π(c)=i}μ_π\); equivalently, decide whether the optimum is at most a given rational threshold.
Types are complete rankings π carrying mass μ_π or ν_π; the decision variables are a candidate bijection and nonnegative transport plans between matched position-mass vectors, with total adjacent-position transport cost as the objective.
Because the paper explicitly treats frequency matrices as voter-number-independent election objects, the proposed μ-input may be viewed as a redundant encoding; the proponent identifies this concern but does not fully establish that the authors would regard the population formulation as a distinct contribution.
fatal: False
The mirror covers Proposition 3.2 and the positionwise-distance computation over population mass; it leaves the rounding interface of Proposition 3.4, embeddings, statistical cultures, winner-score maps, ILP timing, and approximation experiments untouched.
The strongest honest positive case is a narrow Class-A mirror centered on Section 3. The paper has no numbered hardness result: its NP-hardness claims about isomorphic distances, Dodgson, Harmonic Borda, and Chamberlin–Courant occur in prose and citations. But it does contain two qualifying numbered polynomial-time results.
My lead is the paper’s Proposition 3.2, proved in the paper: “There is a polynomial-time algorithm for computing the positionwise distance.”
The corresponding problem is Continuous Positionwise Distance. An instance consists of \(m\) candidates \(C\) and \(D\), together with two finitely supported rational societies \(\mu\) and \(\nu\). A voter type is a complete ranking \(\pi\) of the relevant candidate set; \(\mu_\pi\) and \(\nu_\pi\) are population fractions. For candidate \(c\) and position \(i\), define
\[ p^\mu_{c,i}=\sum_{\pi:\operatorname{pos}_\pi(c)=i}\mu_\pi, \]
and analogously for \(p^\nu\). Thus \(p^\mu_c\) is the distribution of positions occupied by \(c\) in the population.
The question is to find a candidate bijection \(\delta:C\to D\), together with transport plans moving the position mass of \(c\) to the position mass of \(\delta(c)\), minimizing
\[ \sum_{c\in C}\operatorname{EMD}(p^\mu_c,p^\nu_{\delta(c)}), \]
where moving mass from position \(i\) to position \(j\) costs \(|i-j|\). A solution is the optimal candidate matching and the associated position-transport plans; the decision version asks whether the optimum is at most a given rational threshold.
This is a genuine population mirror. The agents are, for example, millions of voters in a large consultation over \(10\) or \(20\) alternatives, with many voters sharing the same ballot type because they belong to recurring ideological, organizational, or demographic cohorts. The number of voters is enormous, while the number of distinct ranking types is moderate. Mass means fraction of voters, not fractional candidates or fractional outcomes.
The result remains in \(P\). The position vectors are computed from the type masses, each earth-mover distance is computed in polynomial time, and the optimal candidate correspondence is a minimum-cost bipartite matching. For rational masses, the running time is polynomial in \(m\), the explicit type support, and the encoding length. A rational finite election with \(n_\pi/n=\mu_\pi\) gives exactly the same answer, so this is also a clean high-multiplicity relaxation of the paper’s finite problem.
The authors should recognize this mirror because the positionwise distance is the paper’s central similarity measure, and the paper already defines it through normalized frequency matrices. The continuous version merely makes the underlying population distribution \(\mu\) the input object rather than treating it as a summary extracted from a named finite election.
The second anchor is Proposition 3.4, also proved in the paper: given an \(m\times m\) bistochastic matrix \(X\) and an integer \(n\), one can compute in polynomial time an election with \(n\) voters whose position matrix \(P\) satisfies
\[ |nx_{i,j}-p_{i,j}|<1 \]
for every cell and, subject to these inequalities, minimizes
\[ \sum_{i,j}|nx_{i,j}-p_{i,j}|. \]
This gives the problem Continuous-to-Finite Population Rounding. An instance is a rational population distribution \(\mu\) over complete rankings, a target population size \(n\), and its induced frequency matrix \(X\). The task is to output a compressed multiset of complete ranking types, with integer multiplicities summing to \(n\), whose position matrix \(P\) satisfies the cellwise error bounds and minimizes the total error above. The output is represented by type multiplicities, not by listing all \(n\) voters.
The paper’s algorithm solves the rounding part by a minimum-cost flow over the fractional parts of \(nX\), then realizes the resulting integer position matrix as actual rankings. The realization step uses Proposition 3.3 (⋆), proved in the paper: for an integer position matrix \(X\in P(m)\), an election with at most \(m^2-2m+2\) distinct votes can be computed in \(O(m^{4.5})\) time with position matrix exactly \(X\). Thus the continuous population can be converted into a compact finite high-multiplicity representation.
This second problem is also Class A. It asks how a mass society can be represented at a prescribed finite population scale while preserving all candidate-position marginals as accurately as integrality permits. It is useful when a large electorate is modelled by a distribution but an experimental or administrative procedure requires a finite ballot profile.
The scope is deliberately limited. These mirrors cover the paper’s positionwise-distance and frequency-matrix machinery, including its finite-to-continuous and continuous-to-finite interfaces. They do not claim to continuize Kamada–Kawai embedding, the statistical-culture experiments, the Borda and Copeland visualizations, or the ILP running-time experiments.
The main weakness is serious: the paper already works with frequency matrices, normalized voter fractions, convex combinations, and expected matrices. A referee could therefore say that Continuous Positionwise Distance is already implicit in the paper and that the mirror adds notation more than a new computational object. The second mirror is likewise close to the paper’s existing matrix-to-election interface.
So this is not a strong hardness-dissolution case. Its positive force is narrower: the paper contains a natural, author-recognizable population object and proves polynomial algorithms for computing with it and for translating between fractional population descriptions and compressed finite electorates. A further, more substantial question would be continuous Harmonic-Borda winner determination,
\[ \min_{S\subseteq C,\ |S|=k} \sum_{\pi}\mu_\pi\,\operatorname{HBScore}(\pi,S), \]
which would likely be Class B because the committee remains integral and rational masses reproduce finite multiplicities. But the paper states that hardness only in unnumbered prose, so I would not use it as an anchor here.
The strongest negative case is that both anchors are already continuous aggregate-matrix results in the paper, rather than new continuous-population problems.
For Proposition 3.2, let \(M_\mu(c,i)\) be the fraction of a society \(\mu\) placing candidate \(c\) at position \(i\). The proposed objective
\[ \min_{\delta}\sum_c \operatorname{EMD}\bigl(M_\mu(c,\cdot),M_\nu(\delta(c),\cdot)\bigr) \]
is exactly the paper’s \(POS(E,F)\) computation. If \(\mu_\pi=n_\pi/n\), then \(M_\mu\) is literally the paper’s frequency matrix \(\#\mathrm{freq}(E)\), with no limiting argument and no approximation. Proposition 3.2 already solves the resulting matching problem, while Sections 3.4, 3.6, and 3.7 explicitly treat arbitrary bistochastic matrices, convex combinations, and voter-number-independent representations as legitimate election objects.
Thus the proposed society distribution is only a redundant encoding. The algorithm immediately projects it to the same \(m\times m\) frequency matrix that the paper already uses. This is not a new high-multiplicity relaxation whose population structure creates a new complexity question; it is the paper’s existing quotient representation with \(\mu\) written in front of it.
The stronger version does not rescue this anchor. If one wants the continuous object to retain correlations between candidates’ positions, then positionwise distance is inadequate: the paper itself observes that impartial-culture and single-peaked-on-a-circle societies can have essentially identical frequency matrices despite very different internal structures. One could instead define an optimal-transport distance over complete ranking types, for example
\[ \min_{\delta}\ \inf_{\lambda\in\Pi(\mu,\delta_\#\nu)} \sum_{\rho,\sigma}\lambda_{\rho,\sigma}d_{\mathrm{swap}}(\rho,\sigma). \]
That would be a potentially interesting new problem, but it is no longer a continuous version of Proposition 3.2. It replaces the paper’s central positionwise metric by the richer isomorphic-swap metric that the paper deliberately avoids. The anchor therefore faces a dilemma: preserve the paper’s metric and obtain a collision, or preserve the population’s full structure and leave the paper’s result behind.
Proposition 3.4 is an even clearer collision. The proposed “Continuous-to-Finite Population Rounding” problem is precisely the proposition, followed by Proposition 3.3’s realization of the rounded position matrix as a compressed election. Its input is not really a society distribution \(\mu\), but a bistochastic matrix \(X\); all information about the ranking-type distribution has already been discarded. The min-cost flow is a generic rounding algorithm for fractional matrix entries, and the subsequent decomposition into rankings is already supplied by the paper.
Again, demanding more does not improve the mirror. If the output must preserve the full distribution over ranking types, then Proposition 3.4 does not solve that task: it preserves only candidate-position marginals, and many different societies produce the same \(X\). A full-type rounding problem would be a new histogram or transportation problem, not a continuization of this proposition. If preserving \(X\) is sufficient, the paper has already formulated and solved the continuous-to-finite interface.
The paper’s remaining contributions do not provide a hidden third anchor. The Kamada–Kawai maps are numerical embeddings of finite datasets; the Borda and Copeland colorings are experiments; the ILP running-time and approximation-ratio sections report empirical behavior. The NP-hardness statements for isomorphic distance, Dodgson, Harmonic Borda, and Chamberlin–Courant are cited in prose rather than established as numbered computational results in this paper.
So the negative case is not that elections lack repeated types, nor that a continuous version would have the same answer. Those would be mistakes. It is that the only numbered computational anchors already operate on normalized aggregate populations, and the proposed mirrors merely rename those objects. I would not claim that no conceivable new problem inspired by this paper could be worthwhile: full-profile transport or a high-multiplicity Harmonic-Borda study could be legitimate research. But those would be new problems, not worthwhile continuous mirrors of the two results actually raised.
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.