d4-conf-atal-2015-0121 (d4-conf-atal-2015-0121)

Given candidates \(C\), a finite support \(T\) of rankings with rational masses \(\mu_t\) summing to \(1\), an initially unique Borda winner \(p\), and a rational threshold \(\kappa>0\), does there exist a destination ranking \(d\in T\) and transfers \(0\le x_t\le\mu_t\) for \(t\ne d\), with \(\sum_{t\ne d}x_t\ge\kappa\), such that the resulting masses \(\mu'_t=\mu_t-x_t\) for \(t\ne d\) and \(\mu'_d=\mu_d+\sum_{t\ne d}x_t\) leave \(p\) the unique Borda winner?

Given candidates \(C\), with \(m=|C|\geq 2\), a society is given by its support: a list \(T\) of \(\tau\) distinct strict rankings of \(C\), each with positive binary rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
Use Borda with scores weighted by mass. The input also contains an initially unique winner \(p\in C\) and a binary rational threshold \(\kappa>0\). Ties with another candidate disqualify \(p\) as a unique winner.
A permitted transfer chooses one destination \(d\in T\) and real amounts \(0\leq x_t\leq\mu_t\) for \(t\neq d\). Destination mass cannot leave; transferred mass adopts ranking \(d\).
The resulting masses are \(\mu'_t=\mu_t-x_t\) for \(t\neq d\) and \(\mu'_d=\mu_d+\sum_{t\neq d}x_t\). Decide whether such a transfer exists with \(\sum_{t\neq d}x_t\geq\kappa\) and \(p\) still the unique Borda winner.

Is this decision problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

The discrete version, where whole voters switch to one existing destination party while preserving the unique Borda winner, is \(\mathrm{NP}\)-hard. [Guo, Shrestha and Yang](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p1431.pdf)
No result settling exactly the mass-transfer version was identified in the literature search.

Result

The mass-transfer decision problem belongs to \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\).

For each existing destination, a rational linear program can determine whether enough mass can move while all of \(p\)'s score differences remain strictly positive. The strict inequalities are handled by maximizing a common winning margin.

1. Score differences after a transfer

For ranking \(t\) and candidate \(c\), let \(\operatorname{pos}_t(c)\) be the position of \(c\), starting at \(1\), and define its Borda score by
\[ \]
\(b_t(c)=m-\operatorname{pos}_t(c)\).

For every opponent \(q\in C\setminus\{p\}\), define
\[ \]
\(a_{tq}=b_t(p)-b_t(q)\), and \(\Delta_q=\sum_{t\in T}\mu_t a_{tq}\).

The premise that \(p\) is initially the unique winner means precisely that \(\Delta_q>0\) for every opponent \(q\).

Fix a destination \(d\in T\). Transferring mass \(x_t\) from ranking \(t\) to ranking \(d\) changes the score difference between \(p\) and \(q\) by \(x_t(a_{dq}-a_{tq})\). Indeed, the resulting difference is

\(\displaystyle M_{dq}(x) =\left(\mu_d+\sum_{t\ne d}x_t\right)a_{dq} +\sum_{t\ne d}(\mu_t-x_t)a_{tq} =\Delta_q+\sum_{t\ne d}(a_{dq}-a_{tq})x_t. \)

Consequently, \(p\) remains the unique Borda winner if and only if \(M_{dq}(x)>0\) for every \(q\ne p\).

2. A linear program for each destination

For destination \(d\), introduce the \(\tau-1\) transfer variables \(x_t\), together with one margin variable \(\varepsilon\). Consider the following linear program:

Maximize \(\varepsilon\), subject to

• \(0\le x_t\le\mu_t\) for every \(t\in T\setminus\{d\}\);
• \(\displaystyle\sum_{t\ne d}x_t\ge\kappa\);
• \(\displaystyle\Delta_q+\sum_{t\ne d}(a_{dq}-a_{tq})x_t\ge\varepsilon\) for every \(q\in C\setminus\{p\}\);
• \(0\le\varepsilon\le1\).

The bound \(\varepsilon\le1\) makes the feasible region bounded and does not affect whether a positive margin exists. All constraints are non-strict.

If this program is feasible, its feasible region is closed and bounded, hence compact. Therefore its objective attains a maximum; denote that maximum by \(\varepsilon_d^*\).

Lemma. A permitted successful transfer to \(d\) exists if and only if this program is feasible and \(\varepsilon_d^*>0\).

Proof. Suppose a successful transfer \(x\) exists. Its transferred mass meets the threshold and every opponent's margin is positive. Since there are finitely many opponents and \(m\ge2\), the number

\(\displaystyle \eta=\min_{q\ne p}M_{dq}(x)\)

exists and is positive. Set \(\varepsilon=\min\{1,\eta\}>0\). Then \((x,\varepsilon)\) satisfies every constraint, so \(\varepsilon_d^*\ge\varepsilon>0\).

Conversely, suppose the program is feasible and \(\varepsilon_d^*>0\). At an optimal solution, the transfer amounts obey their permitted bounds and meet the threshold. Every opponent satisfies \(M_{dq}(x)\ge\varepsilon_d^*>0\), so \(p\) is the unique winner. This proves the lemma.

In particular, an optimum of zero does not cause acceptance: it certifies only that nonnegative margins are attainable under the threshold constraint.

3. Polynomial encoding length and exact computation

We use the standard polynomial-time theorem for rational linear programming: feasibility can be decided, and a finite optimal value computed exactly, in time polynomial in the binary encoding length of the linear program. This is polynomial time in the bit model, as established by Khachiyan's linear-programming theorem. [Khachiyan, *A polynomial algorithm in linear programming*](https://www.mathnet.ru/eng/dan42319).

We check the required encoding bound explicitly.

Each \(a_{tq}\) is an integer satisfying \(|a_{tq}|\le m-1\), and thus \(|a_{dq}-a_{tq}|\le2(m-1)\). These coefficients require \(O(\log m)\) bits.

Write each input mass as \(\mu_t=u_t/v_t\), with positive integer denominator, and let \(Q=\prod_{t\in T}v_t\). The binary length of \(Q\) is \(O(L)\), because the sum of the input denominators' binary lengths is at most \(L\). Moreover,

\(\displaystyle \Delta_q =\frac{\sum_{t\in T}u_t(Q/v_t)a_{tq}}{Q}. \)

Because the masses sum to one, \(|\Delta_q|\le m-1\). Its displayed integer numerator therefore has absolute value at most \(Q(m-1)\). Hence every \(\Delta_q\) has a rational representation using \(O(L+\log m)\) bits, computable by polynomial-time integer arithmetic.

Each destination's program has exactly \(\tau\) variables and \(2\tau+m\) inequalities. Its entire encoding length is therefore polynomial in \(m,\tau,L\). All hypotheses of the rational linear-programming theorem are satisfied.

Exact optimization distinguishes \(\varepsilon_d^*=0\) from \(\varepsilon_d^*>0\); no assumed numerical tolerance is needed.

4. Decision algorithm and conclusion

The algorithm is:

• Compute the Borda differences \(a_{tq}\) and initial margins \(\Delta_q\).
• For each \(d\in T\), solve its linear program.
• Accept if some program is feasible with positive optimal margin; otherwise reject.

The lemma proves correctness for each destination. Enumerating all of \(T\) proves correctness for the full problem, since a permitted transfer must select one of these destinations.

There are \(\tau\) programs, each of polynomial encoding length. Thus the total running time is polynomial in \(m,\tau,L\). This also covers \(\tau=1\): the transfer sum is then zero, so the positive threshold makes the program infeasible.

The discrete hardness result does not conflict with this conclusion. Whole-voter transfers require integer transfer counts; the present problem permits arbitrary real amounts and therefore admits the linear programs above. The cited discrete Borda result is Theorem 6 of [Guo, Shrestha and Yang](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p1431.pdf).

⟨structured verdict parsed — rendered above⟩

Verification report

The prover resolves the task correctly. The linear programs model the permitted transfers exactly, their positive optimal margins characterize strict victory, and their binary encoding lengths are polynomial in \(m,\tau,L\). No mathematical gaps or false steps were found.

1. Score differences

The definition \(b_t(c)=m-\operatorname{pos}_t(c)\) is the standard Borda scoring convention. Thus \(a_{tq}=b_t(p)-b_t(q)\) correctly measures the contribution of ranking \(t\) to the score difference between \(p\) and \(q\).

The initial difference \(\Delta_q=\sum_t\mu_ta_{tq}\) is correct. Under the input premise, \(\Delta_q>0\) for every opponent.

For a fixed destination \(d\), the displayed expansion of \(M_{dq}(x)\) correctly accounts for both the mass removed from each source and the mass added to \(d\). Its simplified expression has the correct sign:
\[ M_{dq}(x)=\Delta_q+\sum_{t\ne d}(a_{dq}-a_{tq})x_t. \]
Consequently, requiring all these differences to be strictly positive is exactly the unique-winner condition.

2. Linear-program formulation

The source bounds encode precisely the allowed real transfer amounts. There is no outgoing variable for \(d\), as required. The transfer-sum constraint correctly retains the inclusive threshold \(\sum_{t\ne d}x_t\ge\kappa\).

The margin constraints and \(0\le\varepsilon\le1\) are also correct. The upper bound does not impose a minimum winning margin: any strictly positive collection of margins permits some positive \(\varepsilon\le1\).

Every variable is bounded, and all constraints are non-strict affine inequalities. Therefore a nonempty feasible region is compact, and the objective attains its maximum. This remains valid if the feasible region has empty interior.

3. Equivalence lemma

Both directions are justified.

• For a successful transfer, the minimum margin exists and is positive because there are finitely many opponents and \(m\ge2\). Choosing \(\varepsilon=\min\{1,\eta\}\) satisfies every constraint.
• For a feasible program with positive optimum, an attained optimal solution satisfies every permitted-transfer constraint and gives every opponent a strictly positive margin.

The distinction between zero and positive optimum is essential and is handled correctly. An optimum of zero cannot establish unique victory.

4. Encoding length and polynomial computation

The coefficient bounds \(|a_{tq}|\le m-1\) and \(|a_{dq}-a_{tq}|\le2(m-1)\) are correct.

The common-denominator argument is valid even if the input fractions are not reduced. The product \(Q\) has polynomial binary length; its factors divide it exactly. The displayed numerator for \(\Delta_q\) is an integer, and the normalization of the masses gives the asserted bound \(Q(m-1)\) on its absolute value. Computing these quantities requires only polynomial-time integer arithmetic.

The constraint count is correct:
\[ 2(\tau-1)+1+(m-1)+2=2\tau+m. \]
There are exactly \(\tau\) variables. Together with the coefficient bounds and the input encoding of \(\kappa\), this proves polynomial LP encoding length.

The prover states an appropriate standard rational linear-programming theorem: feasibility and finite exact optimization are polynomial-time operations in the binary input length. Its hypotheses hold here: all data are rational, the system is explicitly listed, and every feasible program has a finite attained optimum. The cited [Khachiyan paper](https://www.mathnet.ru/eng/dan42319) establishes polynomial-time linear programming. No numerical-tolerance assumption is needed.

5. Enumeration, edge cases, and discrete comparison

Enumerating \(T\) examines every permitted destination and requires only \(\tau\) LP calls.

The case \(\tau=1\) is correctly rejected because the transfer sum is zero and \(\kappa>0\). Thresholds exceeding the available source mass likewise make the corresponding program infeasible. The argument covers \(m=2\), where the minimum margin is over one opponent.

The discrete-hardness comparison is consistent with the continuous result. The cited [Theorem 6](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p1431.pdf) does state Borda hardness for ONE-DESTINATION-MAX; that external result is not needed for the continuous algorithm’s correctness.

Required repair: None. The empty display delimiters preceding two definitions are harmless formatting artifacts.

⟨structured verdict parsed — rendered above⟩