Answer: Polynomial-time solvable.
Theorem 3.4 — class: hardness
Given candidates \(C\), a bipartite action graph \(A\), a rational campaign mass \(\gamma>0\), a target \(c^\star\), a fixed tie-breaking priority, and a finite-support background society \(\mu\) of total mass \(1-\gamma\) over pairwise reports, does there exist a distribution \(\nu\) of total mass \(\gamma\) over strict orientations of every edge in \(A\) such that \(c^\star\) wins under pBorda? Campaign members share a utility ranking that places \(c^\star\) above the current winner; cycles in their reports are permitted.
Let \(C\) contain \(m\geq2\) candidates, let \(A\subseteq\binom{C}{2}\) be a simple bipartite action graph, and fix a strict tie-breaking priority and target \(c^\star\in C\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts listed types, not possible types. A type is an irreflexive, antisymmetric pairwise report; comparisons may be omitted and cycles are permitted.
The input background society \(\mu\) has total mass \(1-\gamma\), where \(\gamma\in\mathbb{Q}\) and \(0<\gamma\leq1\). Empty support is allowed when \(\gamma=1\). Let \(L\) be the total binary input length.
For any society \(\rho\), define \(M_{ij}(\rho)=\sum_{R:iRj}\rho(R)\) and the pBorda score \(s_i(\rho)=\sum_{j\in C\setminus\{i\}}M_{ij}(\rho)/(M_{ij}(\rho)+M_{ji}(\rho))\), with \(0/0=0\). The winner maximizes this score, using the fixed priority to break ties.
The current winner is the winner of \(\mu\); campaign members share a strict utility ranking placing \(c^\star\) above that winner. This ranking imposes no restrictions on their reports.
An admissible campaign society \(\nu\) has total mass \(\gamma\), arbitrary finite support with positive binary-rational masses, and each report orients every edge of \(A\) exactly once and compares no pair outside \(A\); cycles are allowed.
Decide whether an admissible \(\nu\) makes \(c^\star\) the winner of \(\mu+\nu\).
Is this continuous pBorda manipulation problem solvable in polynomial time in \(m,\tau,|A|,L\), or is it NP-hard?
Discrete pBorda manipulation by one voter required to orient every action edge is NP-complete even for bipartite action graphs. [Source](https://www.ifaamas.org/Proceedings/aamas2016/pdfs/p358.pdf)
No result settling this exact continuous problem was located in the literature search.
The problem is solvable in polynomial time. In fact, bipartiteness is unnecessary: the same algorithm works for every simple action graph under the stated report rules.
The proof has two ingredients: campaign societies realize exactly the rational points of a box of edge marginals, and all final scores are affine functions of those marginals.
Write \(q=|A|\). For each edge \(e\in A\), choose an ordered labeling \((u_e,v_e)\), and define
\(x_e=M_{u_ev_e}(\nu)\).
Because every campaign report orients every action edge exactly once and the campaign has total mass \(\gamma\),
\(0\leq x_e\leq\gamma,\qquad M_{v_eu_e}(\nu)=\gamma-x_e.\)
All coordinates are rational because campaign masses are rational.
Lemma. Every rational vector \(x\in[0,\gamma]^q\) is realized by an admissible campaign society with at most \(q+1\) positive-mass types.
Proof. Sort the distinct values in \(\{0,\gamma\}\cup\{x_e:e\in A\}\):
\(0=t_0<t_1<\cdots<t_k=\gamma.\)
There are at most \(q+2\) distinct values, so \(k\leq q+1\). For each interval \((t_{\ell-1},t_\ell)\), choose its midpoint \(z_\ell\), and define a report \(R_\ell\) by orienting edge \(e\) as follows:
Make no comparisons outside \(A\), and assign mass
\(\nu(R_\ell)=t_\ell-t_{\ell-1}.\)
Each mass is positive and rational, and their sum is \(\gamma\). Each report is irreflexive and antisymmetric and orients every action edge exactly once. Cycles cause no obstruction because they are permitted.
For a fixed edge \(e\), the intervals whose midpoints satisfy \(z_\ell<x_e\) partition \((0,x_e)\). Their masses therefore sum to \(x_e\), proving
\(M_{u_ev_e}(\nu)=x_e.\)
This also covers \(A=\varnothing\): use the empty report with mass \(\gamma\). Thus the construction realizes every claimed vector. \(\square\)
Consequently, there are no additional consistency constraints coupling different edge marginals.
Compute the background quantities
\(a_{ij}=M_{ij}(\mu)\)
from the listed support. For each action edge \(e\), put
\(d_e=a_{u_ev_e}+a_{v_eu_e}+\gamma.\)
Since \(\gamma>0\), we have \(d_e>0\). The campaign adds exactly \(\gamma\) to the total comparison mass on this edge, independently of its orientation distribution. Its contributions to the endpoint scores are therefore
\(\displaystyle \frac{a_{u_ev_e}+x_e}{d_e}\quad\text{and}\quad\frac{a_{v_eu_e}+\gamma-x_e}{d_e}.\)
For each candidate \(i\), define the fixed contribution from pairs outside \(A\):
\(\displaystyle b_i=\sum_{\substack{j\ne i\\\{i,j\}\notin A}}\frac{a_{ij}}{a_{ij}+a_{ji}},\)
using the stipulated value \(0\) when the denominator is zero. Campaign reports never compare these pairs, so their contributions remain fixed.
Thus the final score is exactly the affine function
\(\displaystyle S_i(x)=b_i+\sum_{\substack{e\in A\\u_e=i}}\frac{a_{u_ev_e}+x_e}{d_e}+\sum_{\substack{e\in A\\v_e=i}}\frac{a_{v_eu_e}+\gamma-x_e}{d_e}.\)
All its coefficients are rational.
Let \(H\) consist of the candidates other than \(c^\star\) that precede \(c^\star\) in the tie-breaking priority. Let \(K=C\setminus(H\cup\{c^\star\})\).
By the definition of the winner, \(c^\star\) wins exactly when
\(S_{c^\star}(x)>S_i(x)\quad(i\in H),\qquad S_{c^\star}(x)\geq S_i(x)\quad(i\in K).\)
Introduce a common strictness margin \(\delta\), and solve the rational linear program
\(\displaystyle \text{maximize }\delta\)
subject to
\(0\leq x_e\leq\gamma\quad(e\in A),\qquad 0\leq\delta\leq1,\)
\(S_i(x)+\delta\leq S_{c^\star}(x)\quad(i\in H),\)
\(S_i(x)\leq S_{c^\star}(x)\quad(i\in K).\)
The algorithm answers yes precisely when this program is feasible and its optimal value is positive.
Correctness, forward direction. Suppose an admissible campaign makes \(c^\star\) win. Its marginals give a rational vector \(x\) in the box. If \(H\ne\varnothing\), choose
\(\displaystyle \delta=\min\left(\{1\}\cup\{S_{c^\star}(x)-S_i(x):i\in H\}\right).\)
Every gap in this finite minimum is positive, so \(\delta>0\), and all program constraints hold. If \(H=\varnothing\), choose \(\delta=1\). In either case, the optimal value is positive.
Correctness, reverse direction. Suppose the program is feasible and has positive optimal value. A bounded rational linear program has a rational optimal solution; take such a solution \((x,\delta)\). Since \(\delta>0\), the constraints give all required strict inequalities for \(H\) and weak inequalities for \(K\). The lemma constructs an admissible rational campaign realizing \(x\). Its scores are the functions \(S_i(x)\), so \(c^\star\) wins.
This argument deals with exact ties and does not rely on numerical tolerances.
We use the standard rational linear programming theorem: feasibility and bounded optimization for explicitly given rational linear programs can be performed exactly in time polynomial in their binary encoding length, returning a rational optimum when one exists. Polynomial-time solvability originates with [Khachiyan’s linear programming algorithm](https://www.mathnet.ru/eng/dan42319).
Its hypotheses hold here:
For the last point, each \(a_{ij}\) is a sum of input masses. A common denominator can be chosen as the product of the input denominators; the product’s bit length is at most the sum of their bit lengths. Hence these sums have polynomial bit length. Adding \(\gamma\), taking the reciprocals of the positive \(d_e\), and summing at most \(m-1\) rational terms to form each score preserves polynomial bit length. The quantities can be computed by scanning the explicitly listed types, without enumerating possible types.
Exact rational linear programming therefore decides the problem in polynomial time. Moreover, when the answer is yes, it returns marginals of polynomial bit length. Sorting those marginals and applying the lemma produces at most \(q+1\) campaign types, with polynomial total encoding length.
For a campaign consisting of one report of mass \(\gamma\), each marginal must belong to \(\{0,\gamma\}\). Arbitrary rational mixtures instead permit every rational point of \([0,\gamma]^q\), as proved above. Thus the discrete problem imposes endpoint constraints that are absent from this continuous problem. The stated discrete hardness result does not obstruct the linear programming algorithm.
The utility-ranking premise adds no constraints to this formulation because the task explicitly allows unrestricted campaign reports.
⟨structured verdict parsed — rendered above⟩
The claimed polynomial-time resolution is sound in substance. The marginal characterization, affine score formulas, treatment of strict tie-breaking, and polynomial encoding argument all hold under the stated report rules. Bipartiteness is indeed unused.
I found one minor set-theoretic misstatement in the marginal construction. It does not invalidate the construction or require new mathematics.
For each action edge, every campaign report contributes to exactly one of its two orientations. Therefore the identities \(0\leq x_e\leq\gamma\) and \(M_{v_eu_e}(\nu)=\gamma-x_e\) are correct. Rationality follows from finite support with rational masses.
The converse construction is valid:
The endpoint cases \(x_e=0\) and \(x_e=\gamma\) work: the corresponding orientation receives respectively zero mass and all campaign mass. The separately stated construction for \(A=\varnothing\) is also valid.
Minor issue: The sentence “the intervals whose midpoints satisfy \(z_\ell<x_e\) partition \((0,x_e)\)” is literally false when there are thresholds strictly between \(0\) and \(x_e\). The open intervals omit those threshold points. For example, with two marginal values \(\gamma/2\) and \(\gamma\), the selected intervals for the latter omit \(\gamma/2\).
This does not affect the assigned masses or their sum.
Minimum clarification: Correct the partition wording and explicitly identify the selected consecutive intervals whose assigned masses sum to \(x_e\).
The conclusion that all rational box points are realizable is otherwise established.
The background quantities \(a_{ij}\) correctly record all relevant information from the listed types.
On an action edge, the total final comparison mass is \(d_e=a_{u_ev_e}+a_{v_eu_e}+\gamma\). This is independent of \(x_e\) and strictly positive because \(\gamma>0\). Thus both endpoint contribution formulas are correct.
Outside \(A\), the campaign adds no comparisons. The fixed contributions \(b_i\), including their specified zero-denominator convention, are therefore correct.
The displayed expression for \(S_i(x)\) accounts for every pair involving candidate \(i\) exactly once. All variable terms have fixed rational denominators, so the scores are affine rational functions.
No gap occurs here.
The sets \(H\) and \(K\) correctly distinguish competitors that defeat the target on a score tie from those that lose such a tie. Consequently, the required strict and weak inequalities exactly characterize the target winning.
The common margin construction is valid. When \(H\neq\varnothing\), finitely many positive score gaps have a positive minimum; capping that minimum at \(1\) preserves positivity and satisfies the margin bounds. When \(H=\varnothing\), choosing \(\delta=1\) is valid because no score constraint contains \(\delta\).
For the reverse implication, the program has a nonempty bounded rational feasible polyhedron whenever it is feasible. Its objective attains a rational optimum. A positive optimal margin gives precisely the required strict inequalities, and the marginal lemma converts the rational solution into an admissible campaign.
The argument correctly distinguishes infeasibility from a feasible optimum of zero. It also handles lower-dimensional feasible sets and exact ties without numerical assumptions.
No gap occurs here.
The stated rational linear programming theorem is the appropriate standard theorem: explicitly encoded rational programs admit polynomial-time feasibility testing and exact optimization, with a rational optimal solution when a finite optimum exists. The cited [Khachiyan reference](https://www.mathnet.ru/eng/dan42319) identifies the foundational polynomial-time linear programming result.
The application satisfies its hypotheses:
The bit-length argument is valid. Products of input denominators have bit length bounded by the sum of their bit lengths. Forming background sums, adding \(\gamma\), taking reciprocals of positive rational denominators, and summing polynomially many score terms produce polynomial-length rational coefficients.
The computation uses listed support rather than enumerating possible reports, as the task requires. A rational optimal solution has polynomial encoding length, and the threshold construction consequently yields a campaign with polynomial total encoding length.
No substantive complexity gap occurs here.
The proof addresses the continuous problem specified in the task. Its distinction between a single report’s endpoint marginals and arbitrary mixtures’ box marginals is justified by the established characterization.
Empty background support when \(\gamma=1\), an empty action graph, zero comparison mass outside \(A\), and arbitrary priority positions of the target are all covered by the formulas and constraints.
The utility premise imposes no report restrictions, so omitting it from the optimization constraints is justified. No step relies on bipartiteness.
Correct the open-interval partition sentence in Section 1. No additional lemma, algorithmic ingredient, or mathematical argument 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.