Answer: Polynomial-time solvable exactly in \(L^{O(1)}\); consequently fixed-parameter tractable for \(r+\alpha\).
Theorem 19 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet $\Psi(\ves) \in \P_{0,(\tau, n_1),\delta,\gamma,\alpha, \beta}$ be a winning condition. {\sc Minimum Move} can be solved in time $g(\gamma, \alpha) (\tau + \delta)^{\Oh(1)} \log(\ves)$ for any linear function $f(\vem) = \vecc^{\transpose} \vem$, where $g$ is some computable function.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a candidate set \(C\), its ranking types \(\mathcal T\), a rational distribution \(\mu\) supported on \(S\subseteq\mathcal T\), rational conversion costs \(\gamma(t,u)\), and a target condition \(\Psi\) given as a disjunction of systems of linear inequalities on type masses, find nonnegative transfers \(x_{t,u}\) minimizing \(\sum_{t\in S,u\in\mathcal T}\gamma(t,u)x_{t,u}\), subject to \(\sum_u x_{t,u}\leq\mu_t\) for each \(t\in S\) and \(\Psi(\mu')\). Here \(\mu'_u=\mu_u+\sum_{t\in S}x_{t,u}-\mathbf{1}_{u\in S}\sum_v x_{u,v}\); return an optimal transfer or report infeasibility.
Let \(C\) contain \(m\geq1\) candidates, and let \(\mathcal T\) be all strict rankings of \(C\). A society is given by its support: the list \(S\) of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau=|S|\) is the support size, not \(m!\). Require \(\sum_{t\in S}\mu_t=1\), and set \(\mu_u=0\) outside \(S\).
Conversion costs are an explicit table \(\gamma:\mathcal T^2\to\mathbb Q_{\geq0}\), with \(\gamma(t,t)=0\) and \(\gamma(t,v)\leq\gamma(t,u)+\gamma(u,v)\). Costs need not be symmetric.
The target condition is explicitly given as \(\Psi(y)=\bigvee_{i=1}^{d}(A_i y\leq b_i)\), with binary-encoded integer coefficients, \(d\geq1\), at most \(r\) rows per system, and \(\alpha=\max(1,\max_i\|A_i\|_\infty)\). Inequalities are non-strict; \(\Psi\) alone determines acceptance.
A transfer consists of real masses \(x_{t,u}\geq0\) for \(t\in S,u\in\mathcal T\), satisfying \(\sum_u x_{t,u}\leq\mu_t\). Its resulting society is \(\mu'_u=\mu_u+\sum_{t\in S}x_{t,u}-\mathbf1_{u\in S}\sum_{v\in\mathcal T}x_{u,v}\), with the last sum interpreted as zero outside \(S\).
Continuous Minimum Move asks for a transfer minimizing \(\sum_{t\in S,u\in\mathcal T}\gamma(t,u)x_{t,u}\) subject to \(\Psi(\mu')\), or a report of infeasibility. Let \(L\) be the total binary input length, including the cost table and all systems; state running times in \(m,\tau,d,r,\alpha,L\).
Is Continuous Minimum Move solvable in polynomial time, or is it NP-hard? If it is NP-hard, is it nevertheless fixed-parameter tractable with parameter \(r+\alpha\)?
Discrete Minimum Move admits an algorithm whose dependence on \(r,\alpha\) is unrestricted but whose dependence on the total type universe and number of disjuncts is polynomial ([source](https://arxiv.org/html/1801.09584)); discrete Borda shift bribery, a covered specialization, is NP-complete ([source](https://www.math.auckland.ac.nz/~slinko/Research/swap.pdf)).
For continuous moves, a polynomial-time result is known when winner regions have polynomially many systems and inequalities in \(m\), with running time polynomial also in the allowed destination count; this does not explicitly cover arbitrary input conditions \(\Psi\) ([source](https://arxiv.org/html/2608.25444v1)).
Continuous Minimum Move is solvable exactly in polynomial time in the total binary input length \(L\). Consequently, it is fixed-parameter tractable for parameter \(r+\alpha\), with no parameter-dependent factor required. NP-hardness would imply \(\mathrm P=\mathrm{NP}\).
This conclusion applies to the full stated problem, including arbitrary explicitly listed systems, binary rational masses and costs, and asymmetric costs.
Let \(N=|\mathcal T|=m!\). Introduce a variable \(z_{t,u}\) for every \(t\in S\) and \(u\in\mathcal T\). Interpret it as the mass originating at \(t\) that ends at \(u\), including mass that stays at its original type. Require
\[
\]
\(z_{t,u}\geq0,\qquad \sum_{u\in\mathcal T}z_{t,u}=\mu_t\quad(t\in S).\)
The resulting mass at \(u\) is then
\(y_u=\sum_{t\in S}z_{t,u}.\)
In particular, \(y_u\geq0\) and \(\sum_{u\in\mathcal T}y_u=\sum_{t\in S}\mu_t=1\).
We prove that this formulation preserves both resulting societies and costs.
From transfers to allocations. Given a legal transfer \(x\), define
\(z_{t,u}=x_{t,u}\quad(u\ne t),\qquad z_{t,t}=\mu_t-\sum_{v\ne t}x_{t,v}.\)
The capacity inequality \(\sum_vx_{t,v}\leq\mu_t\) implies \(z_{t,t}\geq0\), and each row of \(z\) sums to \(\mu_t\).
If \(u\in S\), diagonal transfers cancel in the original definition of \(\mu'_u\), giving
\(\mu'_u=\mu_u-\sum_{v\ne u}x_{u,v}+\sum_{\substack{t\in S\\t\ne u}}x_{t,u}=\sum_{t\in S}z_{t,u}.\)
If \(u\notin S\), then \(\mu_u=0\) and
\(\mu'_u=\sum_{t\in S}x_{t,u}=\sum_{t\in S}z_{t,u}.\)
Because \(\gamma(t,t)=0\), the costs agree:
\(\sum_{t\in S,u\in\mathcal T}\gamma(t,u)z_{t,u}=\sum_{t\in S,u\in\mathcal T}\gamma(t,u)x_{t,u}.\)
From allocations to transfers. Conversely, given such an allocation \(z\), set \(x_{t,u}=z_{t,u}\) for \(u\ne t\), and set \(x_{t,t}=0\). Then
\(\sum_ux_{t,u}=\mu_t-z_{t,t}\leq\mu_t.\)
The same calculations show that its resulting society is \(y\) and its cost equals the allocation cost. Thus the two formulations are exactly equivalent.
Let \(r_i\leq r\) be the number of rows of \(A_i\), and write its entries as \(a^{(i)}_{j,u}\). For each \(i\), solve the following linear program:
\( \displaystyle \min_z\ \sum_{t\in S}\sum_{u\in\mathcal T}\gamma(t,u)z_{t,u}, \)
subject to
\(z_{t,u}\geq0\quad(t\in S,\ u\in\mathcal T),\)
\(\sum_{u\in\mathcal T}z_{t,u}=\mu_t\quad(t\in S),\)
\(\sum_{t\in S}\sum_{u\in\mathcal T}a^{(i)}_{j,u}z_{t,u}\leq b^{(i)}_j\quad(j\in\{1,\ldots,r_i\}).\)
The last constraints are precisely \(A_i y\leq b_i\), after substituting \(y_u=\sum_tz_{t,u}\).
All coefficients are rational. Moreover, every variable satisfies \(0\leq z_{t,u}\leq\mu_t\leq1\). The feasible region is therefore a closed, bounded polyhedron. Whenever it is nonempty, the continuous linear objective attains a finite minimum.
We use the standard polynomial-time theorem for rational linear programming: an explicitly encoded rational LP can be tested for feasibility and, when its optimum is finite and attained, an exact rational optimal solution and value can be computed in time polynomial in its binary encoding length. The rationality and finite-attainment hypotheses have just been checked.
Solve all \(d\) linear programs. If every one is infeasible, report infeasibility. Otherwise, choose a feasible program with the smallest optimal value and convert its allocation into a transfer as above.
To justify this procedure, every accepted transfer satisfies at least one system \(A_i\mu'\leq b_i\), by the definition of \(\Psi\). Its corresponding allocation is feasible for that system’s LP with exactly the same cost. Hence its cost is at least the smallest optimum among the feasible programs.
Conversely, an optimal allocation from any feasible program yields a legal transfer whose resulting society satisfies that program’s system, and hence satisfies \(\Psi\), with the same cost.
These two implications prove both the infeasibility report and global optimality of the returned transfer.
Each program has \(n=\tau m!\) variables, \(\tau\) equality constraints, at most \(r\) target inequalities, and \(n\) nonnegativity constraints.
Its coefficients are copied from the input or are zero or one. Repeating coefficients across source types increases encoding length only polynomially. For example, a dense encoding of program \(i\) has length at most
\(O\bigl((\tau+r_i+1)(\tau m!+1)(L+1)\bigr).\)
Consequently, for a universal constant exponent, the running time is bounded by
\(d\bigl(m+\tau m!+r+L+\log_2(1+\alpha)\bigr)^{O(1)}.\)
Crucially, this is polynomial in the actual input length. The explicit cost table contains \(N^2\) rational entries, so \(N^2=O(L)\). Since \(\tau\leq N\), we obtain
\(\tau m!=\tau N\leq N^2=O(L).\)
Also, \(d\), the actual number of rows, \(m\), and \(\log_2(1+\alpha)\) are all \(O(L)\). If \(r\) is merely a loose upper bound, use the actual maximum row count in the construction. The total running time is therefore \(L^{O(1)}\), including exact comparison of optimal values and production of the transfer.
Thus the parameterized running time has the form \(f(r+\alpha)L^c\) with \(f\equiv1\) and a universal constant \(c\).
The triangle inequality and symmetry play no role in this proof. The allocation equivalence uses the zero diagonal; LP solvability uses the explicit rational data.
The cited discrete Borda shift-bribery hardness concerns indivisible votes. It does not establish hardness for real-valued transfers; the paper states that discrete result as Theorem 7. [Elkind, Faliszewski, and Slinko](https://www.math.auckland.ac.nz/~slinko/Research/swap.pdf).
The cited continuous paper’s Theorem 1 likewise uses linear programs when destination counts and winner-region descriptions permit them. Here, the explicitly supplied disjunction can be enumerated in time polynomial in \(L\), and the full cost table makes the destination universe polynomially bounded in \(L\). Thus no bound on the number of systems purely in terms of \(m\) is needed for this input model. [Continuous Computational Social Choice](https://arxiv.org/html/2608.25444v1).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes exact polynomial-time solvability for the stated explicit input model, and consequently fixed-parameter tractability for \(r+\alpha\). No mathematical gaps or false steps were found.
The variables are indexed correctly: only supported types supply mass, while every type may receive mass.
For a legal transfer, the proposed diagonal allocation satisfies
\[
z_{t,t}=\mu_t-\sum_{v\ne t}x_{t,v}\geq0,
\]
because nonnegativity and the transfer capacity constraint imply that the off-diagonal sum is at most \(\mu_t\). Adding the off-diagonal entries gives exactly the required row total \(\mu_t\).
The resulting-society calculation is correct in both cases. For a supported destination, the diagonal transfer cancels between incoming and outgoing mass. For an unsupported destination, the original mass and outgoing term are both zero. Thus every destination has resulting mass \(\sum_t z_{t,u}\).
Cost preservation is also correct: all off-diagonal entries remain unchanged, and both diagonal contributions have zero cost. The construction need not preserve diagonal transfer quantities, since those quantities affect neither the resulting society nor the objective.
Setting off-diagonal transfers equal to the allocation entries and diagonal transfers to zero produces nonnegative transfers. The allocation row equality gives
\[
\sum_u x_{t,u}=\mu_t-z_{t,t}\leq\mu_t.
\]
Consequently, all capacity constraints hold. The same supported/unsupported destination calculations establish the claimed resulting society, and the zero diagonal again establishes cost preservation.
These constructions prove equivalence of achievable societies and their achievable costs. They do not require a bijection between transfer arrays and allocation arrays.
Substituting \(y_u=\sum_tz_{t,u}\) into each row of \(A_i y\leq b_i\) gives exactly the displayed LP inequality. There is no missing condition on acceptance: satisfying that system is sufficient because acceptance is defined solely by the explicit disjunction.
All LP coefficients are rational and explicitly constructible. Nonnegativity and the row totals bound every variable by its source mass, which is at most one. The feasible region is closed and bounded in a finite-dimensional space. Therefore, whenever it is nonempty, the linear objective attains a finite minimum.
The rational LP theorem is stated with sufficient precision for its use here: polynomial time refers to binary encoding length and includes an exact rational optimizer and objective value. Its hypotheses are satisfied. In particular, the use of real transfer variables does not create a requirement for irrational output; rational LP optimization supplies a rational optimum.
Every accepted transfer satisfies at least one explicitly listed system. Its equivalent allocation is therefore feasible for at least one of the enumerated LPs, with identical cost. Its cost cannot be below the smallest feasible LP optimum.
Conversely, every feasible LP optimizer converts into an accepted transfer with the same objective value. These statements establish global optimality and justify reporting infeasibility precisely when every LP is infeasible.
Enumerating the disjuncts is valid even when systems overlap. No convexity assumption on their union is used.
The LP has \(\tau m!\) variables and the stated numbers of constraints. Its displayed dense encoding bound is a valid conservative upper bound: copied coefficients have bit length bounded by the input length, and replication across sources and constraints introduces only the indicated dimension factors.
The decisive input-model observation is correct. Writing \(N=m!\), the explicit cost table contains \(N^2\) rational entries, so
\[
N^2=O(L),\qquad \tau N\leq N^2=O(L).
\]
Thus the factorial type universe does not make the constructed LP exponentially large relative to this input.
The explicitly listed disjunct count and actual row counts are bounded by the input length. The treatment of a potentially loose bound \(r\) is correct: construction uses actual row counts. Coefficient bit lengths, including those of right-hand sides, are covered by \(L\).
Accordingly, the stated running-time expression is valid and reduces to \(L^{O(1)}\). Exact comparison of rational objective values and production of the rational transfer are covered by the same polynomial bound.
Polynomial time with a universal exponent establishes the claimed FPT bound with \(f\equiv1\). Asymmetric costs pose no problem. The triangle inequality is unnecessary for the written argument.
The proof also covers \(m=1\), systems with zero rows, zero costs, and systems whose intersection with the allocation constraints is empty. Non-strict inequalities are correctly used in the attainment argument. Normalization and positive supported masses ensure a nonempty support and valid row capacities.
The discrete citation is accurate: Theorem 7 states NP-completeness of Borda shift bribery. That discrete result does not establish hardness of the continuous problem audited here. [Swap Bribery](https://www.math.auckland.ac.nz/~slinko/Research/swap.pdf).
The continuous paper’s positive-results Theorem 1 uses LPs under its winner-region and destination-enumeration hypotheses. The prover’s description of that comparison is accurate; its own explicit-input proof does not depend on extending that theorem beyond those hypotheses. [Continuous Computational Social Choice: A Case Study in Bribery](https://arxiv.org/html/2608.25444v1).
Actionable feedback: No mathematical repair or additional clarification is required.
⟨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.