Answer: Polynomial-time solvable: every promised instance admits a feasible evolution preserving \(a\) as the unique Borda winner.
Theorem 4.7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor each F in {Borda, Maximin, Copeland}, the problem F-ShortestPath is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support of paired rankings \(h=(r_0,r_1)\) with rational masses \(\eta_h\), where the initial and final marginal societies both have unique Borda winner \(a\), does there exist a piecewise-linear evolution of mass in which each history’s mass moves only along adjacent-swap paths of length \(\kappa(r_0,r_1)\), and \(a\) remains a Borda co-winner in the aggregate society at every point?
Given a candidate set \(C\) of size \(m\geq 1\) and \(a\in C\), a society is given by its support: a list of \(\tau\geq 1\) distinct types \(h=(r_0,r_1)\), each consisting of two strict complete rankings and a positive binary rational mass \(\eta_h\), with \(\sum_h\eta_h=1\). Here \(\tau\) is the support size, not the number of possible types; let \(L\) be the total input bit length.
Let \(\kappa(r,s)\) be the minimum number of adjacent swaps transforming \(r\) into \(s\). For each history \(h\), retain rankings \(r\) satisfying \(\kappa(r_0,r)+\kappa(r,r_1)=\kappa(r_0,r_1)\); permit a directed edge \(r\to s\) precisely when one adjacent swap produces \(s\) and \(\kappa(s,r_1)=\kappa(r,r_1)-1\).
An evolution consists of nonnegative continuous piecewise-linear masses \(x_{h,r}(t)\), for \(t\in[0,1]\), initially concentrated at \(r_0\) and finally at \(r_1\), with total mass \(\eta_h\) for every history. On each of finitely many time intervals, constant nonnegative transfer rates along permitted edges give each coordinate's derivative as inflow minus outflow. Mass may split and transfers may occur simultaneously; history labels remain fixed.
The aggregate mass at ranking \(r\) is \(\sum_h x_{h,r}(t)\); use mass-weighted Borda scores, allowing all candidates tied for the maximum to win. Both endpoint societies are promised to have unique winner \(a\). Call an evolution feasible if \(a\) is a Borda co-winner at every time.
Is deciding whether a feasible evolution exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For explicitly listed, individually paired voters, deciding whether a shortest adjacent-swap sequence preserves the common endpoint winner as a co-winner is NP-complete for Borda. [Source](https://www.ifaamas.org/Proceedings/aamas2013/docs/p383.pdf)
No result settling this exact divisible-mass problem was located in the literature search.
The problem is polynomial-time solvable: every instance satisfying the endpoint promise admits a feasible evolution. In fact, \(a\) can remain the unique Borda winner throughout.
The stated equations allow simultaneous through-flow at rankings containing zero mass, which gives a direct construction. To address the more restrictive interpretation of transfers as moving mass already present, I also prove feasibility using only one edge at a time.
For each history \(h\), choose a shortest adjacent-swap path
\(r_{h,0}=r_0,\ r_{h,1},\ldots,r_{h,D_h}=r_1,\qquad D_h=\kappa(r_0,r_1).\)
Such a path exists because adjacent swaps can transform any complete ranking into any other.
Every prefix and suffix of a shortest path is shortest: replacing either by a shorter path would shorten the whole path. Consequently, for every \(j\),
\(\kappa(r_0,r_{h,j})=j,\qquad \kappa(r_{h,j},r_1)=D_h-j.\)
Thus every path vertex satisfies the required geodesic equality, and every path edge decreases distance to \(r_1\) by one. All these vertices and edges are permitted. Shortest paths have no repeated vertices.
Define, for every history and ranking,
\(x_{h,r}(t)=\eta_h\bigl((1-t)\mathbf 1_{\{r=r_0\}}+t\mathbf 1_{\{r=r_1\}}\bigr).\)
For a history with \(D_h>0\), assign constant transfer rate \(\eta_h\) to every edge of its chosen path. Assign zero rate to all other edges.
The resulting derivatives are exactly those of the displayed coordinates:
When \(D_h=0\), keep the history stationary. These coordinates are nonnegative, conserve each history’s mass, and satisfy both endpoint conditions. One time interval suffices.
Let \(S_c^i\) denote candidate \(c\)’s Borda score at endpoint \(i\). Linearity of mass-weighted Borda scores gives
\(S_a(t)-S_c(t)=(1-t)(S_a^0-S_c^0)+t(S_a^1-S_c^1).\)
For every \(c\ne a\), both endpoint differences are positive by the promise, so their convex combination is positive. Hence \(a\) remains the unique winner.
This construction uses positive through-flow at internal vertices whose mass is zero. That satisfies the specified derivative equations. The next argument shows that this feature is unnecessary under the endpoint promise.
Assume \(m\geq 2\); when \(m=1\), the sole candidate wins throughout any permitted evolution.
Write \(b_c(r)\) for candidate \(c\)’s Borda score in ranking \(r\), using scores from \(m-1\) down to zero. For each competitor \(c\ne a\), define
\(g_c(r)=b_a(r)-b_c(r).\)
Then
\(-(m-1)\leq g_c(r)\leq m-1.\)
Define the minimum endpoint winning margin
\(\delta=\min_{c\ne a}\min\{S_a^0-S_c^0,\ S_a^1-S_c^1\}.\)
There are finitely many competitors, and every endpoint margin is positive. Therefore \(\delta>0\). Choose an integer \(N\) satisfying
\(N>2(m-1)/\delta.\)
Conceptually divide the mass of every history into \(N\) packets, each of mass \(\eta_h/N\). These packets are only bookkeeping; they do not change the history labels.
Perform \(N\) rounds. During each round, take one packet from each history and transport it all the way along that history’s chosen shortest path. Process histories sequentially, and move each packet across one edge at a time. A packet is transferred completely across one edge before its next transfer begins.
Thus every transfer draws on mass already present at its source.
Let \(K=\sum_h D_h\). If \(K=0\), all histories are stationary.
Otherwise, the construction has \(NK\) edge transfers. Give each transfer a time interval of length \(1/(NK)\). When moving a packet belonging to history \(h\), assign rate
\((\eta_h/N)/(1/(NK))=\eta_h K\)
to its current edge, and zero rate to every other edge.
During that interval, the packet’s mass decreases linearly at the source and increases linearly at the destination. Its remaining source mass stays nonnegative. Consequently, all coordinates are continuous, nonnegative, and piecewise linear, with constant nonnegative permitted transfer rates on finitely many intervals.
After every round, exactly one further packet of each history has reached its destination. After all \(N\) rounds, every history is concentrated at \(r_1\).
Fix a time during round \(k+1\), where \(k\) rounds have been completed and \(0\leq k<N\).
For each history \(h\), let \(p_{h,r}(t)\) describe the normalized distribution of its packet for the current round. This distribution is concentrated:
In particular, \(p_{h,r}(t)\geq0\) and \(\sum_r p_{h,r}(t)=1\). The history’s actual coordinates are
\(x_{h,r}(t)=\eta_h\left(\frac{N-k-1}{N}\mathbf 1_{\{r=r_0\}}+\frac{k}{N}\mathbf 1_{\{r=r_1\}}+\frac1N p_{h,r}(t)\right).\)
Compare this with the society at the beginning of the round,
\(y_{h,r}^{k}=\eta_h\left(\frac{N-k}{N}\mathbf 1_{\{r=r_0\}}+\frac{k}{N}\mathbf 1_{\{r=r_1\}}\right).\)
This reference society is the endpoint mixture with weights \(1-k/N\) and \(k/N\). Hence its winning margin against every competitor is at least \(\delta\).
For a fixed competitor \(c\), the change in its margin relative to this reference is
\(\displaystyle \frac1N\sum_h\eta_h\left(\sum_r p_{h,r}(t)g_c(r)-g_c(r_0)\right).\)
Both \(\sum_r p_{h,r}(t)g_c(r)\) and \(g_c(r_0)\) belong to the interval from \(-(m-1)\) to \(m-1\). Their difference is therefore at least \(-2(m-1)\). Using \(\sum_h\eta_h=1\), the actual winning margin satisfies
\(S_a(t)-S_c(t)\geq\delta-\frac{2(m-1)}N>0.\)
This holds for every competitor and every time. Therefore the sequential construction also preserves \(a\) as the unique winner throughout.
On the promised input domain, the decision algorithm simply returns YES. If input validity and the endpoint promise must also be checked, rankings and rational masses can be checked and endpoint scores computed using polynomial-time rational arithmetic in \(m,\tau,L\).
The sequential construction may require exponentially many intervals when the endpoint margin is small. This does not affect the decision result: the definition requires finitely many intervals, without a polynomial bound. Moreover, the exact equations admit the one-interval construction in Section 2.
The cited NP-completeness theorem concerns shortest paths through discrete voter profiles. Divisibility permits arbitrarily small packets, whose temporary score effects fit inside the positive endpoint margin; the discrete theorem therefore does not extend to this model. [Obraztsova et al., Theorem 4.7](https://www.ifaamas.org/Proceedings/aamas2013/docs/p383.pdf)
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. Every promised instance admits a feasible evolution, and the stronger claim that \(a\) remains the unique winner is also established. I found no major or minor mathematical issues.
Adjacent swaps connect the finite set of complete rankings, so a shortest path exists for every history. The prefix and suffix argument is valid: replacing either segment by a shorter path would contradict minimality of the full path.
Consequently, the two distance identities hold at every path vertex. Their sum gives the required geodesic equality, and the suffix identity verifies that each directed edge decreases distance to the destination by exactly one. The statement that a shortest path has no repeated vertices is correct; any repetition would permit deletion of a positive-length cycle.
For a history with distinct endpoints, the displayed coordinates put mass \(\eta_h(1-t)\) at its initial ranking and mass \(\eta_h t\) at its final ranking. All other coordinates vanish. These coordinates are nonnegative, continuous, linear, and conserve the history’s mass.
Assigning rate \(\eta_h\) to every edge of the chosen path gives derivative \(-\eta_h\) at the initial vertex, \(+\eta_h\) at the final vertex, and zero at every internal vertex. Unused vertices also have zero derivative. The absence of repeated path vertices ensures these cases do not overlap.
Positive inflow and outflow at a zero-mass internal vertex satisfy the evolution definition as written: it imposes nonnegative coordinates and nonnegative rates with the stated balance equations, without an additional source-availability constraint. The prover explicitly identifies this feature. Histories with identical endpoints are correctly treated as stationary; the coordinate formula then gives constant mass \(\eta_h\).
Aggregating the coordinates produces exactly the convex combination of the two endpoint societies. Borda scores are linear in ranking masses, so the displayed identity for each score difference is correct.
For every competitor, both endpoint differences are strictly positive. Their convex combination is strictly positive throughout the closed time interval, including its endpoints. Thus the construction preserves the unique winner, which is stronger than the required co-winner condition.
When there is only one candidate, there are no competitors and winner preservation is automatic. The direct construction still applies.
For at least two candidates, every ranking-level score difference belongs to the stated bounded interval. The minimum endpoint margin is positive because it is the minimum of finitely many strictly positive numbers. Therefore a finite integer satisfying the specified strict inequality exists.
Splitting each history into equal packets is valid bookkeeping for divisible mass and leaves history labels fixed. Moving each packet along its chosen path uses only permitted edges. At the beginning of each transfer, its full mass is present at the source; during the transfer, its remaining source mass decreases linearly to zero. Other packets contribute nonnegative mass, so every coordinate remains nonnegative.
If the total path length is positive, there are exactly the stated number of edge transfers. Their interval lengths sum to one, and the rate calculation is correct. All rates are finite and nonnegative. Transfer boundaries preserve continuity. If every path length is zero, the separately specified stationary evolution handles the case.
The coordinate decomposition correctly accounts for completed rounds, packets reserved for future rounds, and the current round’s packet. It also remains valid for stationary histories, where the initial and final rankings coincide.
The reference society is the stated endpoint mixture. Its margin against every competitor is at least the minimum endpoint margin.
Subtracting the reference coordinates from the actual coordinates gives exactly the displayed margin-change expression. The current packet’s expected score difference and its initial score difference both lie in the stated bounded interval, so their difference is bounded below by its negative width. Summing with the history masses introduces no support-size factor because those masses sum to one.
Hence the final lower bound is strictly positive by the choice of packet count. The argument covers all transfer times and round boundaries; the final endpoint is covered by the promise.
Since feasibility holds for every promised input, returning YES decides the promised problem in polynomial time. The potentially large sequential construction does not undermine that conclusion: the task asks for a decision, and the evolution definition requires only finitely many intervals. The optional validation claim is also sound; explicit rankings, rational masses, normalization, distinctness of types, and endpoint scores can be checked using polynomial-time exact arithmetic.
The cited discrete result is accurately characterized. Definition 4.6 requires a common unique endpoint winner and a shortest path along which that candidate remains a winner; Theorem 4.7 states NP-completeness for Borda. Its graph uses discrete, individually indexed votes. [Obraztsova et al., Definition 4.6 and Theorem 4.7](https://www.ifaamas.org/Proceedings/aamas2013/docs/p383.pdf)
The prover does not apply that theorem to the continuous model. Its independent constructions establish why the discrete hardness result does not obstruct this decision algorithm.
No additional lemma, clarification, or repair is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.