Drawing a map of elections (d4-journals-ai-2025-0007)

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.

Let \(C,D\) have equal size \(m\). The input consists of explicitly listed complete rankings with nonnegative, binary-encoded rational masses \(\mu_\pi,\nu_\rho\), each society having total mass \(1\). For \(c\in C\), set \(p^\mu_{c,i}=\sum_{\pi:\operatorname{pos}_\pi(c)=i}\mu_\pi\); define \(p^\nu_{d,i}\) analogously. Here position \(1\) is top-ranked, and \(\operatorname{EMD}(x,y)\) moves mass between positions \(i,j\) at cost \(|i-j|\) per unit.
Define \(\operatorname{OPT}(\mu,\nu)=\min_{\delta:C\to D\text{ bijective}}\sum_{c\in C}\operatorname{EMD}(p^\mu_c,p^\nu_{\delta(c)})\). An output includes an optimal bijection and optimal position-transport plans.

Is deciding whether \(\operatorname{OPT}(\mu,\nu)\le t\), for a rational threshold \(t\), in P or NP-hard?

For finite voter lists, positionwise distance is computable in polynomial time ([Szufa et al.](https://arxiv.org/abs/2504.03809)). Frequency matrices and the same positionwise distance have also been defined for vote distributions ([Boehmer et al.](https://papers.nips.cc/paper_files/paper/2022/file/cb1a0e1bd8b2f20f7500c7886e1fbc60-Paper-Conference.pdf)).

The problem is in \(\mathrm{P}\). An optimal bijection and optimal position-transport plans can also be computed in time polynomial in the binary input length.

The objective agrees with the raw positionwise distance between frequency matrices defined by [Boehmer et al.](https://papers.nips.cc/paper_files/paper/2022/file/cb1a0e1bd8b2f20f7500c7886e1fbc60-Paper-Conference.pdf). The proof below explicitly handles rational masses and their encoding lengths.

Exact computation of the marginals. Let \(L\) denote the total binary input length. Assume first that \(m\ge 1\). Let \(Q\) be the product of all denominators appearing in the masses of both societies, with positive denominators. Then every mass is an integer multiple of \(1/Q\), and \(\log_2 Q\) is at most the sum of the input denominator bit lengths, hence is \(O(L)\).

Define integer marginals
\(a_{c,i}=Qp^\mu_{c,i}\) and \(b_{d,i}=Qp^\nu_{d,i}\).
They can be computed by scanning the explicitly listed rankings and adding their scaled masses to the appropriate entries. Because each ranking contains every candidate exactly once and each society has total mass \(1\),
\(\sum_{i=1}^m a_{c,i}=\sum_{i=1}^m b_{d,i}=Q\)
for every \(c,d\). Every entry lies between \(0\) and \(Q\), so these computations have polynomial bit complexity.

Optimal transport on positions. Consider any two nonnegative integer vectors \(a,b\) of length \(m\), each summing to \(Q\). Write
\(A_k=\sum_{i=1}^k a_i\) and \(B_k=\sum_{i=1}^k b_i\), with \(A_0=B_0=0\).
We prove
\(\operatorname{EMD}(a/Q,b/Q)=Q^{-1}\sum_{k=1}^{m-1}|A_k-B_k|\),
and construct a plan attaining this value.

A scaled transport plan is a nonnegative matrix \(T\) with row sums \(a_i\) and column sums \(b_j\); its cost before division by \(Q\) is \(\sum_{i,j}|i-j|T_{ij}\).

For each cut between positions \(k\) and \(k+1\), define the mass crossing rightward and leftward by
\(R_k=\sum_{i\le k<j}T_{ij}\) and
\(S_k=\sum_{j\le k<i}T_{ij}\).
The marginal constraints imply \(R_k-S_k=A_k-B_k\): subtracting total demand on the first \(k\) positions from total supply there cancels all mass transported within those positions. Consequently,
\(R_k+S_k\ge |A_k-B_k|\).

A shipment from \(i\) to \(j\) crosses exactly \(|i-j|\) cuts. Summing its contribution over those cuts therefore gives
\(\sum_{i,j}|i-j|T_{ij}=\sum_{k=1}^{m-1}(R_k+S_k)\ge\sum_{k=1}^{m-1}|A_k-B_k|\).

To attain this bound, partition the interval \((0,Q]\) into intervals
\(I_i=(A_{i-1},A_i]\) and, separately, into intervals
\(J_j=(B_{j-1},B_j]\).
Define
\(T_{ij}=\operatorname{length}(I_i\cap J_j)=\max\{0,\min(A_i,B_j)-\max(A_{i-1},B_{j-1})\}\).

The two partitions show that the row sums are \(a_i\) and the column sums are \(b_j\), so this is a feasible integer plan. At cut \(k\), its rightward crossing mass is the length of \((0,A_k]\cap(B_k,Q]\), namely \(\max\{A_k-B_k,0\}\). Its leftward crossing mass is similarly \(\max\{B_k-A_k,0\}\). Thus \(R_k+S_k=|A_k-B_k|\) at every cut, establishing equality in the lower bound.

Dividing this plan by \(Q\) gives the required optimal transport plan for the probability vectors. The construction also covers zero entries and, with an empty cut sum, \(m=1\).

Optimal candidate matching. For every \(c\in C\) and \(d\in D\), compute the integer weight
\(W_{cd}=\sum_{k=1}^{m-1}\left|\sum_{i=1}^k a_{c,i}-\sum_{i=1}^k b_{d,i}\right|\).
The transport formula proves that
\(W_{cd}=Q\,\operatorname{EMD}(p^\mu_c,p^\nu_d)\).

Construct the complete bipartite graph with vertex classes \(C,D\) and edge weights \(W_{cd}\). A perfect matching selects exactly one partner for each candidate on both sides, so perfect matchings correspond bijectively to the allowed bijections. For the matching associated with \(\delta\), its weight is exactly
\(Q\sum_{c\in C}\operatorname{EMD}(p^\mu_c,p^\nu_{\delta(c)})\).

Apply the standard polynomial-time algorithm for minimum-weight bipartite perfect matching with binary-encoded integer weights, such as the Hungarian algorithm. Its hypotheses hold: the graph is finite and bipartite, both sides have size \(m\), every edge is present, and all weights are integers. In particular, a perfect matching exists.

If its minimum weight is \(K\), then
\(\operatorname{OPT}(\mu,\nu)=K/Q\).
The matching supplies an optimal bijection. For each selected pair, the interval-intersection construction supplies an optimal position-transport plan. These plans can be selected independently because the stated objective imposes only the individual marginal constraints for each matched pair.

Bit complexity and decision. Each prefix sum lies between \(0\) and \(Q\). Hence
\(0\le W_{cd}\le(m-1)Q\) and \(0\le K\le m(m-1)Q\).
All these integers have \(O(L+\log m)\) bits.

Computing all pair weights uses \(O(m^3)\) arithmetic operations after the marginals are available. The matching algorithm runs in polynomial time in the graph size and weight bit lengths. Constructing all selected transport matrices uses \(O(m^3)\) further arithmetic operations; each output entry has the form \(T_{ij}/Q\), with \(0\le T_{ij}\le Q\), and therefore has polynomial encoding length. Since rankings are explicitly listed, \(m\) is bounded by the input length.

Finally, write the threshold as \(t=u/v\), where \(v>0\). The exact decision is obtained by testing \(vK\le uQ\), an integer comparison of polynomial bit complexity. If \(m=0\) is allowed, the empty bijection has cost \(0\), and the decision is simply \(0\le t\).

Thus both the decision problem and the requested optimal-output problem are polynomial-time solvable. No expansion into a number of voters proportional to \(Q\) is needed.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The argument resolves the stated decision problem and the requested optimal-output problem in polynomial time in the binary input length. No major or minor mathematical issues were found.

• Scope and identification of the objective. The proof addresses explicitly listed rankings with rational masses, exactly as required. The cited identification with raw positionwise distance is correct: its definition minimizes the sum of Earth mover’s distances between candidate frequency columns over permutations. [Boehmer et al., Section 2](https://papers.nips.cc/paper_files/paper/2022/file/cb1a0e1bd8b2f20f7500c7886e1fbc60-Paper-Conference.pdf). The proof does not depend on this bibliographic identification.

• Common denominator and integer marginals. The product \(Q\) is a positive integer divisible by every mass denominator. Its binary length is bounded by the sum of the denominator encoding lengths, up to an additive constant. Thus its numerical magnitude may be exponential, but its representation has polynomial length.

Scaling the masses and accumulating them produces exact integer marginals. Nonnegativity and total society mass \(1\) justify both the marginal sums \(Q\) and the entry bounds between \(0\) and \(Q\). The construction requires polynomially many operations on polynomial-length integers.

• Transport lower bound. The proof correctly considers every nonnegative transport matrix with the prescribed margins; it does not restrict the lower bound to integer plans. For each cut, conservation gives \(R_k-S_k=A_k-B_k\). Nonnegativity then gives \(R_k+S_k\geq |A_k-B_k|\).

The identity expressing transport cost as the sum of crossing masses is exact: each shipment contributes once for each cut between its endpoints. Hence the stated lower bound holds for all feasible plans, including plans with arbitrary real entries.

• Attainment of the transport bound. The interval-intersection formula gives nonnegative integer entries because all interval endpoints are integers. The partition argument correctly establishes the row and column sums.

At each cut, the unions of the relevant supply and demand intervals give exactly the two intersections described in the proof. Their lengths are the positive and negative parts of \(A_k-B_k\). Consequently, the constructed plan attains the lower bound at every cut simultaneously.

Dividing its entries by \(Q\) gives a feasible optimal plan for the original probability vectors. Zero marginal entries cause only empty intervals and do not invalidate the argument. For \(m=1\), the empty cut sum correctly gives zero cost.

• Reduction to candidate matching. The weights \(W_{cd}\) are exactly \(Q\) times the corresponding transport optima. Perfect matchings in the constructed graph correspond bijectively to the allowed candidate bijections, with the asserted equality of objective values.

The invoked standard algorithmic result—polynomial-time minimum-weight bipartite perfect matching with binary-encoded integer weights—is stated sufficiently precisely. Its hypotheses are checked: the graph is finite, bipartite, balanced, complete, and has integer edge weights. Completeness guarantees feasibility.

The selected transport plans can be optimized independently because the problem imposes no constraints coupling transport plans belonging to different matched pairs. Thus the matching and the constructed plans jointly satisfy the requested output specification.

• Bit complexity and output size. The bounds \(W_{cd}\leq(m-1)Q\) and \(K\leq m(m-1)Q\) follow directly from the prefix sums lying between \(0\) and \(Q\). They justify polynomial encoding lengths.

The stated \(O(m^3)\) arithmetic-operation bounds for computing pair weights and constructing the selected transport matrices are valid. The latter produces \(m\) matrices with \(m^2\) entries each, so the explicit output also has polynomial size. Since a valid society of total mass \(1\) includes at least one explicitly listed complete ranking, the claimed bound on \(m\) by input length is justified for \(m\geq1\).

• Threshold comparison and boundary cases. Because \(v>0\) and \(Q>0\), the comparison \(vK\leq uQ\) is equivalent to the required rational comparison, including for negative thresholds. Its operands have polynomial bit length. The separate treatment of \(m=0\) correctly supplies the empty bijection, no transport matrices, and cost zero.

No additional clarification or repair is required.

⟨structured verdict parsed — rendered above⟩