Answer: Polynomial-time solvable: the problem belongs to \(\mathrm P\), with running time polynomial in \(m,\tau,L\).
Theorem 10 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor the Borda rule, CCAUV is NP-complete; hence, under Borda it is NP-complete to decide whether Pr[Win(c ; T′)] > 0.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), registered ranking types \(t\) with masses \(\mu_t\), eligible ranking types \(t\) with available masses \(\nu_t\), and a target \(c\), decide whether there exist admitted masses \(x_t\in[0,\nu_t]\) such that, for every \(d\ne c\), \(\sum_{t\in\mathcal B}\mu_t\bigl(s_B(t,c)-s_B(t,d)\bigr)+\sum_{t\in\mathcal A}x_t\bigl(s_B(t,c)-s_B(t,d)\bigr)\ge 0\), where \(s_B(t,d)=m-\operatorname{pos}_t(d)\).
Given a candidate set \(C\) with \(m=|C|\ge 2\) and a target \(c\in C\), types are strict complete rankings of \(C\). Registered types \(\mathcal B\) have fixed positive masses \(\mu_t\); eligible types \(\mathcal A\) have positive available masses \(\nu_t\). These are finite measures, with no requirement that their masses sum to one; either support may be empty, and a ranking may occur in both.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau=|\mathcal A\cup\mathcal B|\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length. State running times in \(m,\tau,L\).
Use Borda with co-winner semantics: ties for the highest score count as winning. Registered mass cannot be removed. Eligible mass is divisible, and there is no admission budget beyond its availability.
The decision problem asks whether there exist real masses \(x_t\in[0,\nu_t]\) such that, for every \(d\in C\setminus\{c\}\), \(\sum_{t\in\mathcal B}\mu_t\bigl(s_B(t,c)-s_B(t,d)\bigr)+\sum_{t\in\mathcal A}x_t\bigl(s_B(t,c)-s_B(t,d)\bigr)\ge 0\), where \(s_B\) denotes the usual Borda score.
Is this continuous Borda voter-addition decision problem in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For explicitly listed indivisible voters, constructive control by adding an unlimited number of voters under Borda is \(\mathrm{NP}\)-complete; deciding positive winning probability under independent attendance is also \(\mathrm{NP}\)-complete. [Imber and Kimelfeld](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p647.pdf).
No result settling this exact divisible-mass problem was located in the literature search.
The continuous Borda voter-addition decision problem is in \(\mathrm P\), with running time polynomial in \(m,\tau,L\). It is exactly a rational linear-feasibility problem of polynomial encoding length.
Let \(n=|\mathcal A|\le\tau\), and let \(\operatorname{pos}_t(d)\) denote the position of candidate \(d\) in ranking \(t\), counting from \(1\). Under Borda,
\(s_B(t,d)=m-\operatorname{pos}_t(d)\).
For every listed type \(t\) and opponent \(d\ne c\), define
\(a_{dt}=s_B(t,c)-s_B(t,d)=\operatorname{pos}_t(d)-\operatorname{pos}_t(c)\).
These are integers satisfying \(|a_{dt}|\le m-1\). Define the fixed registered margin
\(b_d=\sum_{t\in\mathcal B}\mu_t a_{dt}\).
Consider the following linear feasibility problem, with one real variable \(x_t\) for each \(t\in\mathcal A\):
\(\sum_{t\in\mathcal A}a_{dt}x_t\ge-b_d\quad(d\in C\setminus\{c\}),\)
\(0\le x_t\le\nu_t\quad(t\in\mathcal A).\)
It has \(n\) variables and \(m-1+2n\) inequalities.
Equivalence. For any admissible admission vector \(x\), the final score difference between \(c\) and \(d\) is exactly
\(S_x(c)-S_x(d)=b_d+\sum_{t\in\mathcal A}a_{dt}x_t.\)
Thus an admissible admission vector makes \(c\) a co-winner if and only if it satisfies every displayed inequality. Both directions follow directly from this identity and the availability bounds.
If a ranking belongs to both supports, its fixed contribution appears in \(b_d\), while its additional contribution appears through \(x_t\). Consequently, overlap creates no difficulty.
We verify that constructing the linear program does not produce exponentially long coefficients.
Write each input mass as a positive integer numerator divided by a positive integer denominator. Let \(Q\) be the product of all denominators appearing in registered and eligible masses, taking \(Q=1\) when there are none. Since the sum of their binary encoding lengths is at most \(L\),
\(\log_2 Q\le L.\)
Define integers
\(U_t=Q\mu_t\quad(t\in\mathcal B),\qquad V_t=Q\nu_t\quad(t\in\mathcal A),\)
and change variables to \(y_t=Qx_t\). Because \(Q>0\), this is a bijection between real admission vectors and real scaled vectors satisfying the corresponding bounds. The equivalent system is
\(\sum_{t\in\mathcal A}a_{dt}y_t\ge-R_d,\qquad R_d=\sum_{t\in\mathcal B}U_ta_{dt},\)
\(0\le y_t\le V_t.\)
All coefficients and right-hand sides are now integers. The variables remain real; no integrality constraint is introduced.
Every input numerator has at most \(L\) bits, so \(U_t\) and \(V_t\) have \(O(L+1)\) bits. Moreover,
\(|R_d|\le|\mathcal B|(m-1)\max_{t\in\mathcal B}U_t,\)
with \(R_d=0\) when \(\mathcal B\) is empty. Hence each integer in the system has at most
\(B=O\!\left(L+\log(m+1)+\log(\tau+1)+1\right)\)
bits.
A dense encoding of the complete system therefore has length
\(S=O\!\left((m+\tau+1)(\tau+1)B\right).\)
The ranking positions can be computed by scanning the \(\tau\) listed rankings. Products, exact divisions, and sums used above involve polynomially many integers of polynomial bit length. Thus construction takes time polynomial in \(m,\tau,L\). No unlisted rankings need to be generated.
The polynomial-time linear-programming theorem states that feasibility of an explicitly given system of rational linear inequalities over the reals can be decided deterministically in time polynomial in its binary encoding length. See [Aspvall and Stone, *Khachiyan’s Linear Programming Algorithm*](https://pages.cs.wisc.edu/~cs787-1/AspvallStone.pdf).
Its hypotheses hold here:
Apply that exact feasibility algorithm and return its answer. The LP stage takes \(\operatorname{poly}(S)\) bit operations, so the complete running time is \(\operatorname{poly}(m,\tau,L)\).
Exact feasibility handles ties and feasible sets of lower dimension; no positive winning margin is assumed.
If \(\mathcal A\) is empty, simply test whether every registered margin \(b_d\) is nonnegative. If \(\mathcal B\) is empty, choosing every \(x_t=0\) gives all candidates score zero, so the answer is yes under co-winner semantics. These observations also cover completely empty support.
The hardness results in [Imber and Kimelfeld](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p647.pdf) concern selecting subsets of indivisible voters or deciding whether a winning attendance realization exists. Those choices are discrete. Here every eligible mass can range over an interval, and the constraints are linear, so rational linear feasibility settles the problem.
Therefore the stated continuous problem is polynomial-time solvable. Under polynomial-time many-one reductions, it could also be \(\mathrm{NP}\)-hard only if \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The decision problem is in \(\mathrm P\), with running time polynomial in \(m,\tau,L\). No mathematical gaps, false steps, or missing hypotheses were found.
The formula \(s_B(t,d)=m-\operatorname{pos}_t(d)\) is correct for positions numbered from \(1\). Subtraction gives
\[
a_{dt}=\operatorname{pos}_t(d)-\operatorname{pos}_t(c).
\]
The sign is correct: a positive coefficient means that type \(t\) favors \(c\) over \(d\). The bound \(|a_{dt}|\le m-1\) follows from both positions belonging to \(\{1,\ldots,m\}\).
The registered margin \(b_d\) includes every fixed registered contribution. The identity
\[
S_x(c)-S_x(d)=b_d+\sum_{t\in\mathcal A}a_{dt}x_t
\]
matches the task exactly. Requiring this quantity to be nonnegative for every opponent is precisely co-winner semantics. The bounds \(0\le x_t\le\nu_t\) express all admission restrictions. No budget, normalization, or integrality assumption is introduced.
Overlapping supports are handled correctly: the registered contribution remains fixed, and eligible mass supplies an additional variable contribution. The variable and inequality counts are correct.
The product \(Q\) includes every mass denominator, so \(Q\mu_t\) and \(Q\nu_t\) are integers. Its positivity makes \(y_t=Qx_t\) a bijective change of real variables. Multiplication by \(Q\) preserves inequality directions, and the displayed scaled system is correct.
The argument explicitly retains real variables. Clearing denominators therefore does not accidentally replace the continuous problem with an integer problem.
The estimate \(\log_2Q\le L\) is valid because the denominator encoding lengths are included in the total input length. Multiplying an input numerator by \(Q\) produces an integer of \(O(L+1)\) bits.
For nonempty registered support, the bound
\[
|R_d|\le|\mathcal B|(m-1)\max_{t\in\mathcal B}U_t
\]
correctly accounts for all summands, including possible cancellation. The empty case is stated separately, avoiding an undefined maximum. Consequently, the claimed bound
\[
B=O\!\left(L+\log(m+1)+\log(\tau+1)+1\right)
\]
is valid for coefficients and right-hand sides.
A dense system has \(m-1+2n\) rows and \(n\) variable columns, together with right-hand sides. With \(n\le\tau\), the claimed encoding bound
\[
S=O\!\left((m+\tau+1)(\tau+1)B\right)
\]
is valid.
Ranking scans, coefficient construction, denominator products, exact divisions, and margin sums involve polynomially many operations on integers of polynomial bit length. Thus preprocessing is polynomial in \(m,\tau,L\). The proof uses the listed support only; it never enumerates all possible rankings.
The invoked theorem is stated sufficiently precisely: feasibility of an explicitly encoded rational system of linear inequalities over real variables is decidable deterministically in time polynomial in binary encoding length. All its hypotheses are checked in the write-up.
The cited Aspvall–Stone paper concerns polynomial-time satisfiability of linear inequalities, consistent with this invocation. Its supplied PDF link failed to fetch during this audit, but the [publisher record](https://www.sciencedirect.com/science/article/pii/0196677480900024) confirms the cited result. This access failure is not a mathematical gap.
Exact feasibility covers non-strict inequalities and lower-dimensional feasible sets. The resulting \(\operatorname{poly}(S)\) bound therefore establishes the requested \(\operatorname{poly}(m,\tau,L)\) running time.
With empty eligible support, testing the registered margins is exactly the required decision. With empty registered support, admitting zero mass is permitted and gives every candidate score zero. Under the specified co-winner semantics, the answer is therefore yes. Completely empty support is covered as well.
The distinction between choosing subsets of indivisible voters and choosing real masses in intervals is accurate. The cited discrete results are confirmed by Theorem 4.1 of [Imber and Kimelfeld](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p647.pdf). They do not invalidate the continuous LP formulation.
The final statement about NP-hardness is also correct: a problem in \(\mathrm P\) can be NP-hard under polynomial-time many-one reductions only if \(\mathrm P=\mathrm{NP}\).
No mathematical repair or additional clarification 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.