| paper | Understanding Distance Measures Among Elections |
| authors | Niclas Boehmer, Piotr Faliszewski, Rolf Niedermeier, Stanisław Szufa, Tomasz Wąs |
| venue | IJCAI 2022 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given a candidate set \(C\) and a rational matrix \(P=(p_{cd})_{c\ne d}\), decide whether there exist masses \(\mu_\pi\ge0\) for rankings \(\pi\in S_C\) such that \(\sum_{\pi\in S_C}\mu_\pi=1\) and \(p_{cd}=\sum_{\pi:\,c\succ_\pi d}\mu_\pi\) for every pair \(c\ne d\).
Types are complete rankings \(\pi\in S_C\); decision variables are population masses \(\mu_\pi\); constraints impose the prescribed pairwise marginals \(P\); the objective is feasibility, equivalently membership in the linear-ordering polytope.
The RX3C gadget's whole-vote selection admits fractional mixing, so Theorem 2 provides no evidence that hardness survives continuization; the proponent anticipated possible dissolution but did not establish whether this specific collapse is complete.
fatal: False
The mirror directly covers Theorems 1 and 2 as realizability problems and extends the paper's aggregate representations and six metrics to normalized population masses; it does not separately cover the diameter, correlation, compass-election, or intrinsicness results.
My lead is Theorem 2. The paper states, and proves here, that deciding whether an \(m\times m\) matrix \(M\) is the weighted majority relation \(M_E\) of some election \(E\) is NP-complete. This is an unusually good anchor because the theorem already asks whether an aggregate representation comes from a population of rankings—the population object that ChoCo continuizes.
The natural regime is a large preference census or national consultation with \(N\) voters but only \(\tau\ll N\) distinct complete rankings. A type is one ranking \(\pi\in S_C\); \(\mu_\pi\) is the fraction of the population having that ranking. This is a credible high-multiplicity setting when voters follow a relatively small collection of institutional, demographic, or behavioural preference templates. It is not a claim about every election: a seven-person committee with idiosyncratic rankings would not be a useful limit object.
The continuous problem I would call Pairwise-Realizability\(_\infty\). Its input is a candidate set \(C\) and a rational matrix \(P=(p_{cd})_{c\ne d}\), where \(p_{cd}\) is intended to be the fraction of the population ranking \(c\) above \(d\), with \(p_{cd}+p_{dc}=1\). The question is whether there exists a distribution \(\mu\) over complete rankings such that, for every \(c\ne d\),
\(p_{cd}=\sum_{\pi\in S_C:\,c\succ_\pi d}\mu_\pi\),
with \(\mu_\pi\ge 0\) and \(\sum_\pi\mu_\pi=1\). A solution is the mass distribution \(\mu\), preferably given with finite support; a NO answer means that no society of ranking types realizes \(P\).
This is a direct mirror. A finite election with \(N\) voters maps to \(\mu_\pi=n_\pi/N\) and \(P=M_E/N\). Conversely, any rational solution \(\mu\) can have its denominators cleared to produce a finite high-multiplicity election. Nothing about the candidates, rankings, pairwise comparison semantics, or anonymity has changed. Only integer voter counts have become rational population masses.
The expected classification is Class C: continuum-specific hardness, although this is a conjectural research direction rather than a result established by the paper. Pairwise realizability is membership in the convex hull of the pairwise incidence vectors of all linear orders, i.e. the linear-ordering polytope. The continuous LP has exponentially many ranking variables, and its natural pricing problem is weighted linear-order optimization over permutations. Thus the population has become continuous, but the correlations among all pairwise comparisons still encode candidate-ordering combinatorics. I would not claim that Theorem 2’s NP-hardness automatically transfers: its reduction may rely on the requirement that the profile consist of integral voters with one common denominator. The honest claim is that the theorem opens a precise, nontrivial continuous membership problem whose residual difficulty is likely caused by the agenda of alternatives rather than by population multiplicity.
My second anchor is Theorem 1, also proved in this paper: given a nonnegative integer vector \(x\), deciding whether \(x=B_E\) for some election \(E\) is NP-complete. Its continuous mirror is Borda-Realizability\(_\infty\). The input is a rational vector \(b\in\mathbb Q^C\), interpreted as average Borda scores, with \(\sum_{c\in C}b_c=m(m-1)/2\). The question is whether there exists a distribution \(\mu\) over rankings satisfying
\(b_c=\sum_{\pi\in S_C}\mu_\pi\bigl(m-\operatorname{pos}_\pi(c)\bigr)\)
for every candidate \(c\). The solution is again the distribution \(\mu\), or a certificate that no such distribution exists.
This mirror is particularly clean. If \(E\) has \(N\) voters, then \(b=B_E/N\). The continuous feasible score vectors are exactly the convex hull of the permutations of \((m-1,m-2,\ldots,0)\), the corresponding permutahedron. Feasibility can be checked in polynomial time, for example by finding a doubly stochastic candidate-position matrix \(Q\) satisfying \(b_c=\sum_i(m-i)Q_{c,i}\), and then decomposing \(Q\) into permutation matrices. I therefore expect Borda-Realizability\(_\infty\) to be Class A.
That contrast is scientifically useful rather than a weakness: Theorem 1’s discrete NP-completeness can disappear when population masses are divisible, while Theorem 2 may retain difficulty because pairwise marginals must arise from one common distribution over rankings. It gives exactly the kind of boundary that the continuization programme wants.
The same model also extends the paper’s central distance objects without changing their meaning. For two continuous elections \(\mu\) and \(\nu\), the normalized swap distance becomes an optimal-transport problem over ranking types:
\(\min_{\sigma}\min_x\sum_{\pi,\rho}\operatorname{KT}(\sigma(\pi),\rho)x_{\pi,\rho}\),
where \(x\) couples the mass of \(\sigma(\pi)\) under \(\mu\) to the mass of \(\rho\) under \(\nu\). The positionwise, pairwise, and Bordawise representations are obtained by replacing voter counts with the corresponding population fractions. Thus the proposed mirrors cover the paper’s aggregate-representation results directly and provide a principled route to its six metrics, though I am not claiming that every diameter, correlation, or intrinsicness theorem has already been continuized.
My weakest point is that these anchors come from Section 4’s representation-recognition results rather than from the paper’s headline distance-computation problem, and the Class C prediction for Pairwise-Realizability\(_\infty\) still needs proof. Theorem 2’s integer hardness might dissolve completely under fractional masses. Even so, the case remains strong: the proposed questions are exact high-multiplicity versions of named problems proved in the paper, one yields a transparent polynomial-time relaxation, and the other isolates a credible candidate-ordering barrier rather than inventing an unrelated tractable problem.
The strongest negative case is narrower than the universal claim. It defeats the first mirror and weakens the second, but it cannot honestly eliminate every worthwhile continuization.
Theorem 1 is a poor anchor. For a continuous society, the normalized Borda vector is
\[ b_c=\sum_{\pi\in S_C}\mu_\pi\bigl(m-\operatorname{pos}_\pi(c)\bigr). \]
The feasible vectors are exactly the permutahedron generated by \((m-1,m-2,\ldots,0)\). Equivalently, one can test feasibility by majorization, construct a doubly stochastic candidate-position matrix, and decompose it into permutation matrices. The population distribution has disappeared behind a standard convex polytope. Thus the paper’s NP-completeness comes from exact integral realization with a fixed number of voters; its continuous counterpart is merely aggregate score geometry. That is a legitimate baseline, but not a compelling ChoCo problem: there is no intervention, optimization, robustness question, or residual population structure to study.
Theorem 2 gives a stronger negative point against the proponent’s specific argument. The reduction from RX3C relies on selecting exactly \(t\) whole votes. Its gadget has an immediate fractional solution: assign mass \(1/3\) to the “cover” insertion for every set \(S_i\), and mass \(2/3\) to the insertion before \(b_1\). Since every element occurs in exactly three sets, each element is covered with total mass \(1\), while \(d\) is behind \(b_1\) with total mass \(t\). Hence the reduction’s exact-cover constraint vanishes under continuization. The theorem therefore supplies no evidence that its own hardness survives, or that the proposed mirror has the predicted Class C character.
The better version of the mirror is nevertheless difficult to dismiss. Asking whether a rational pairwise matrix \(P\) is generated by some distribution over rankings is membership in the linear-ordering polytope:
\[ p_{cd}=\sum_{\pi:\,c\succ_\pi d}\mu_\pi . \]
This is a genuine high-multiplicity question, and rational solutions can be converted into finite elections by clearing denominators. It has a credible interpretation as validating pairwise population data against transitive preferences. The fact that the object is standard polyhedral combinatorics does not, by itself, establish that its computational treatment has already been done under ChoCo’s prior-art rule. I therefore cannot defeat this improved anchor without pretending that a real continuous question is invalid merely because its difficulty may come from the alternatives.
The distance extensions are weaker but still legitimate. Replacing voter counts by masses gives an optimal-transport distance over ranking types; for a fixed candidate matching, the transport problem is natural, while the candidate permutation preserves the paper’s substantive anonymity and neutrality. Positionwise and Bordawise variants largely collapse to computations on finite-dimensional marginals, so they are not exciting population-continuization targets. But the normalized swap-distance transport problem remains a defensible computational mirror.
Thus the honest negative verdict is that Theorem 1 is nearly vacuous after continuization, and Theorem 2’s published reduction is specifically destroyed by fractional mass. But the best pairwise-realizability formulation survives these objections. Consequently, the universal claim that no worthwhile continuous mirror exists is not supportable: one surviving mirror is enough, and this paper has one.
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.