Answer: Polynomial-time solvable; the problem belongs to \(\mathsf{P}\).
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate{\sc domination} and {\sc dominating manipulation} with partial orders are {\sf NP}-hard for Borda, even when the number of unknown pairs in each vote is no more than $4$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a fixed tie-breaking order, a finite set of partial-order types \(T\) with at most four unknown pairs each, rational masses \(\mu_t\), a distinguished manipulator with true ranking \(V_M\), and ballots \(V,U\), does \(U\) dominate \(V\) over every admissible mass allocation among the linear extensions of each type, with strict improvement for at least one allocation?
Given a candidate set \(C\) with \(m\geq 2\), a fixed strict tie-breaking order, and strict rankings \(V_M,V,U\), consider Borda voting with divisible non-manipulator mass and one manipulator of weight \(1\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) partial-order types with positive masses \(\mu_t\), each a binary rational. Each type has at most four incomparable unordered candidate pairs. Masses are not normalized; \(\tau\) is the support size, not the number of possible types.
For each type \(t\), let \(\mathcal E_t\) be its linear extensions. An admissible allocation consists of real masses \(x_{t,\ell}\geq 0\) satisfying \(\sum_{\ell\in\mathcal E_t}x_{t,\ell}=\mu_t\) for every \(t\).
Let \(b_\ell(c)\) denote the standard Borda score of \(c\) in ranking \(\ell\). For ballot \(B\in\{V,U\}\), let \(w_B(x)\) be the candidate maximizing \(\sum_{t\in T}\sum_{\ell\in\mathcal E_t}x_{t,\ell}b_\ell(c)+b_B(c)\), with ties resolved by the given order.
Ballot \(U\) dominates \(V\) if \(w_U(x)\succeq_{V_M}w_V(x)\) for every admissible \(x\), and \(w_U(x)\succ_{V_M}w_V(x)\) for at least one admissible \(x\); both outcomes use the same allocation. Here weak preference means equality or higher rank in \(V_M\). Let \(L\) be the total binary input length.
Is deciding whether \(U\) dominates \(V\) solvable in time polynomial in \(m,\tau,L\), or is it \(\mathsf{NP}\)-hard?
For finite lists of unit-weight voters, Borda domination and existence of a dominating manipulation are \(\mathsf{NP}\)-hard even with at most four unknown pairs per partial order ([Conitzer, Walsh, and Xia](https://www.cs.cmu.edu/~conitzer/dominatingAAAI11.pdf)).
No result settling this exact divisible-mass domination problem was located in the literature search.
Deciding whether the given ballot \(U\) dominates the given ballot \(V\) is solvable in time polynomial in \(m,\tau,L\).
The algorithm enumerates the possible ordered pairs of winners and tests each pair using a rational linear program. The same allocation variables determine both winners, and strict tie-breaking inequalities are handled exactly.
Let \(k_t\leq 4\) be the number of incomparable unordered candidate pairs in type \(t\).
Every linear extension specifies an orientation of each of these \(k_t\) pairs. This orientation determines the extension uniquely: the relative order of every other candidate pair is already prescribed by the partial order. Consequently,
\(\lvert\mathcal E_t\rvert\leq 2^{k_t}\leq 16.\)
Moreover, all extensions can be constructed in polynomial time. First compute the transitive closure of the partial order if necessary. Then enumerate the at most \(16\) orientations of its incomparable pairs. Each orientation, together with the prescribed comparisons, gives a directed graph containing exactly one directed edge between every two distinct candidates.
Discard orientations that produce a directed cycle. For each remaining orientation, a topological ordering exists and is unique, because every candidate pair has a prescribed direction. It is a linear extension of the original partial order. Conversely, every linear extension occurs in this enumeration.
Thus, writing
\(N=\sum_{t\in T}\lvert\mathcal E_t\rvert,\)
we have \(N\leq 16\tau\), and all relevant Borda score vectors can be computed in polynomial time. Only the supplied support \(T\) is enumerated.
Let \(\pi(c)\) denote the position of candidate \(c\) in the tie-breaking order; smaller positions have higher priority.
For an allocation \(x\), define the non-manipulator score
\(S_c(x)=\sum_{t\in T}\sum_{\ell\in\mathcal E_t}x_{t,\ell}b_\ell(c).\)
For ballot \(B\in\{V,U\}\) and distinct candidates \(c,d\), define the score difference
\(D_B(c,d;x)=S_c(x)-S_d(x)+b_B(c)-b_B(d).\)
This is an affine function of \(x\). Candidate \(c\) wins under ballot \(B\) if and only if, for every \(d\neq c\),
Indeed, \(c\) must strictly outscore every candidate that would defeat it in a tie, while it may tie candidates of lower priority. These conditions are therefore both necessary and sufficient.
Fix an ordered pair \((a,b)\in C^2\). We will decide whether there exists an admissible allocation \(x\) such that
\(w_V(x)=a\quad\text{and}\quad w_U(x)=b.\)
Introduce the allocation variables \(x_{t,\ell}\) and one additional variable \(\varepsilon\). Maximize \(\varepsilon\), subject to the following constraints.
Allocation constraints:
\(x_{t,\ell}\geq 0\quad\text{for every }t,\ell,\)
\(\sum_{\ell\in\mathcal E_t}x_{t,\ell}=\mu_t\quad\text{for every }t,\)
\(0\leq\varepsilon\leq 1.\)
Winner constraints for \(V\): for every \(d\neq a\), impose
Winner constraints for \(U\): for every \(d\neq b\), impose
Call this linear program \(P_{a,b}\). Crucially, both sets of winner constraints use the same vector \(x\).
The winner pair \((a,b)\) is attainable if and only if \(P_{a,b}\) is feasible and its optimal value is strictly positive.
Suppose first that an admissible allocation \(x\) realizes the pair.
By Section 2, all score differences represented by strict winner conditions are positive. There are finitely many such conditions. If at least one exists, let \(\delta>0\) be the minimum of their score differences and choose
\(\varepsilon=\min\{1,\delta\}>0.\)
If no strict condition exists, choose \(\varepsilon=1\). In either case, \((x,\varepsilon)\) satisfies every constraint of \(P_{a,b}\). Its optimal value is therefore positive.
Conversely, suppose \(P_{a,b}\) has a feasible solution with \(\varepsilon>0\). Every condition that requires strict superiority then has score difference at least \(\varepsilon>0\); every other winner condition has nonnegative score difference. Section 2 gives \(w_V(x)=a\) and \(w_U(x)=b\).
Finally, whenever the LP is feasible, its optimum is attained. Its feasible region is closed and bounded: the allocation constraints imply \(0\leq x_{t,\ell}\leq\mu_t\), and \(0\leq\varepsilon\leq 1\). Thus a positive optimal value supplies the positive-slack feasible solution needed above. This proves the lemma.
We use the standard rational linear programming theorem: a linear program with explicitly encoded rational coefficients can be checked for feasibility and, when feasible with a finite optimum, solved exactly in time polynomial in its binary encoding length. In particular, its rational optimal value can be compared exactly with zero. See [Trevisan’s linear programming notes, Sections 2.4–2.5](https://lucatrevisan.github.io/cs261/lecture05.pdf).
Here its hypotheses hold:
\(D_B(c,d;x)=\sum_{t,\ell}x_{t,\ell}\bigl(b_\ell(c)-b_\ell(d)\bigr)+b_B(c)-b_B(d).\)
All these Borda differences are integers of absolute value at most \(m-1\), so their binary lengths are \(O(\log(m+1))\).
Hence each LP has encoding length polynomial in \(m,\tau,L\), and the lemma provides a polynomial-time test for each winner pair.
This is an exact positivity test. No fixed positive score margin is assumed; feasible strict margins may be arbitrarily small across different inputs.
Let \(\rho(c)\) be the position of \(c\) in the manipulator’s strict ranking \(V_M\), with smaller positions preferred. Compute
\(\mathcal R=\{(a,b)\in C^2:\exists\text{ admissible }x,\ w_V(x)=a,\ w_U(x)=b\}\)
using the preceding LP test for all \(m^2\) ordered pairs.
Then \(U\) dominates \(V\) if and only if both of the following conditions hold:
To prove necessity, each pair in \(\mathcal R\) has an admissible witness allocation. Universal weak improvement therefore excludes every pair with \(\rho(b)>\rho(a)\), and an allocation witnessing strict improvement supplies a pair with \(\rho(b)<\rho(a)\).
For sufficiency, take any admissible allocation. Its two winners form a pair in \(\mathcal R\), so condition 1 gives weak improvement. The pair supplied by condition 2 has an admissible witness allocation, which gives strict improvement.
There are only \(m^2\) LP calls, each taking polynomial time. The subsequent rank comparisons also take polynomial time. This proves the claimed complexity bound.
The cited [Conitzer–Walsh–Xia theorem](https://www.cs.cmu.edu/~conitzer/dominatingAAAI11.pdf) concerns indivisible voters. A unit voter must place all its weight on one extension. With aggregated integer multiplicities, extension counts must remain integers.
The present model permits arbitrary nonnegative real allocations. Its allocation constraints and fixed-winner conditions are therefore linear constraints over real variables, to which the polynomial-time LP theorem applies. The discrete hardness theorem does not impose those integrality restrictions on the problem asked here.
⟨structured verdict parsed — rendered above⟩
The prover’s polynomial-time claim is correct. The argument resolves the exact divisible-mass domination problem in USER_TASK. No major or minor mathematical issues were found.
The bound \(\lvert\mathcal E_t\rvert\leq 2^{k_t}\leq 16\) is valid. Two distinct strict rankings differ on some candidate pair; if both extend the same partial order, that pair must be incomparable. Thus their orientations of the incomparable pairs differ.
After transitive closure, orienting every incomparable pair gives exactly one directed comparison for each distinct candidate pair. An acyclic orientation has a unique topological ordering because every pair’s relative order is specified. It extends the original partial order. Conversely, every linear extension supplies an enumerated acyclic orientation.
Computing closure, checking at most \(16\) orientations per type, and computing their Borda vectors all take polynomial time. The bound \(N\leq16\tau\) correctly uses the supplied support size.
Assessment: Correct and complete.
The inequalities correctly encode the fixed strict tie-breaking order:
These comparisons against every other candidate are necessary and sufficient. The score differences include the manipulator’s ballot contribution with the correct sign.
Assessment: Correct and complete.
Both winner constraints use the same allocation vector, as USER_TASK requires. The nonnegativity and per-type mass equalities describe exactly the admissible allocations.
The shared slack variable correctly handles strict inequalities. At any allocation realizing the pair, the finitely many required strict score differences have a positive minimum. Choosing the smaller of that minimum and \(1\) gives a feasible positive slack. Conversely, positive slack ensures every required strict comparison.
The case with no strict comparisons is explicitly handled: choosing \(\varepsilon=1\) is valid.
The optimum-attainment argument also holds. Each allocation coordinate lies between \(0\) and its finite type mass, and \(\varepsilon\) lies between \(0\) and \(1\). The feasible region is closed and bounded, so a feasible LP attains its optimum. Consequently, positive optimal value is equivalent to an attainable winner pair.
Assessment: Correct and complete, including boundary ties and the absence of strict constraints.
The stated rational LP theorem applies: feasibility and finite-optimum optimization for explicitly encoded rational linear programs are solvable in time polynomial in binary encoding length. The cited [Trevisan notes, Sections 2.4–2.5](https://lucatrevisan.github.io/cs261/lecture05.pdf), support polynomial-time solution and polynomial-size rational optimal solutions.
The encoding checks are correct:
Thus exact comparison of the rational optimum with zero is justified. The argument does not assume a uniform positive margin or confuse numerical approximation with exact feasibility.
Assessment: Correct application of the theorem; all relevant hypotheses are verified.
The attainable relation \(\mathcal R\) captures exactly the winner pairs produced by admissible allocations.
The first rank condition excludes every allocation causing a worse outcome under \(U\). The second supplies an allocation causing a strictly better outcome. The necessity and sufficiency arguments therefore match both quantifiers in the definition of domination.
Enumerating all \(m^2\) ordered pairs preserves polynomial running time. Pairs with equal winners are included correctly: they satisfy weak improvement but cannot witness strict improvement.
Assessment: Correct and complete.
The distinction from indivisible voters is valid. Integer extension counts in the discrete model cannot be substituted for unrestricted real allocation variables. The cited [Conitzer–Walsh–Xia paper, Theorem 4](https://www.cs.cmu.edu/~conitzer/dominatingAAAI11.pdf), states the discrete Borda hardness result with at most four unknown pairs per vote; it does not contradict this algorithm.
The proof addresses deciding domination between the two supplied ballots. It does not claim to solve the separate problem of finding a dominating ballot.
Positive, unnormalized masses cause no difficulty: the allocation bounds depend on the supplied masses, while complexity depends on their binary encoding lengths. No normalization assumption is introduced.
Assessment: Correct contextual distinction and task scope.
No repair or additional clarification is needed. The extension bound, exact treatment of tie-breaking, shared allocation, and rational LP complexity together establish the claimed polynomial-time algorithm.
⟨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.