Answer: Polynomial-time solvable: \(\mathrm P\), with running time polynomial in \(m,\tau,L\).
Corollary 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe unique winner UCM problem can be solved in polynomial time. PROOF. Run the algorithm from Section 5 with |M| −1 ma- nipulators and return the answer. To show the correctness of this procedure, we need to show that c is a co-winner with |M| −1 manipulators iff c is a unique winner with |M| manipulators. (⇒): Suppose c can be made a co-winner with |M|−1 manipu- lators.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) candidates, a target \(c\), a rational coalition mass \(\alpha\), and a distribution \(\nu\) over \(\tau\) nonmanipulator rankings with total mass \(1-\alpha\), does there exist a rational assignment \(y_\pi \geq 0\) of coalition mass to rankings \(\pi\), with \(\sum_\pi y_\pi=\alpha\), such that \(c\) is the unique Schulze winner under the resulting pairwise margins and path strengths?
Let \(C\) be a nonempty set of \(m\) candidates, \(c\in C\), and \(\mathcal R(C)\) the set of strict total rankings of \(C\). The input includes a binary rational \(0<\alpha\leq1\) and nonmanipulator masses \(\nu_\pi\geq0\) totaling \(1-\alpha\).
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 types are rankings, and \(\tau\) is the support size, not \(m!\); let \(L\) be the total input bit length.
The coalition may assign rational masses \(y_\pi\geq0\) to any rankings \(\pi\in\mathcal R(C)\), subject to \(\sum_\pi y_\pi=\alpha\). Set \(q_\pi=\nu_\pi+y_\pi\), taking unlisted nonmanipulator masses as zero.
For distinct candidates define the margin \(w(a,b)=\sum_{\pi:a\succ_\pi b}q_\pi-\sum_{\pi:b\succ_\pi a}q_\pi\). Use the complete directed graph, retaining zero and negative margins.
Define \(S(a,b)=\max_{p:a\leadsto b}\min_{(u,v)\in p}w(u,v)\), where the maximum ranges over simple directed paths. The winning set is \(W=\{a\in C:\forall b\neq a,\ S(a,b)\geq S(b,a)\}\); success means \(W=\{c\}\), with no tie-breaking.
Is deciding whether such a rational coalition assignment exists in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
Discrete unique-winner unweighted coalitional manipulation is polynomial-time solvable for any positive number of manipulators ([Gaspers et al., 2013](https://arxiv.org/abs/1304.0844)).
Later work proves polynomial-time solvability for positive integer voter weights, in both winner models with unbounded candidates and manipulators ([Müller–Kosub, 2020](https://arxiv.org/pdf/1808.09226)).
No result explicitly treating this divisible rational-mass decision problem was located.
The decision problem is in \(\mathrm P\), with running time polynomial in \(m,\tau,L\).
The key fact is stronger than polynomial solvability of integer weighted manipulation: whenever manipulation succeeds, it also succeeds with all manipulators using the same ranking. This implies that allowing rational division of the coalition does not enlarge the set of successful instances.
We use the following established result.
Müller–Kosub theorem and unanimity property. For Schulze elections with positive integer voter weights, constructive coalitional manipulation in the unique-winner model is polynomial-time solvable. Moreover, if a coalition with prescribed positive integer weights can make a candidate the unique winner, then it can do so with every coalition member submitting the same ranking.
The decision statement is Theorem 2; the unanimity property follows from Algorithm 2 and is explicitly stated in footnote 5 of [Müller–Kosub, *A Note on the Complexity of Manipulating Weighted Schulze Voting*](https://arxiv.org/pdf/1808.09226).
Their election definition matches the present question: the graph is complete, edge weights are pairwise margins including zero and negative values, path strengths are maximum bottleneck strengths, and winners satisfy the weak comparisons defining \(W\). Thus their unique-winner model means exactly \(W=\{c\}\). [Source, Section 2](https://arxiv.org/pdf/1808.09226).
Their formulation of paths causes no discrepancy with the requirement of simple paths here. Removing a cycle from a directed walk preserves its endpoints and cannot decrease its minimum edge weight. Consequently, allowing walks does not increase the maximum bottleneck strength.
For a margin function \(w\), write \(S_w(a,b)\) for its strongest-path value and \(W_w\) for its winning set.
Lemma 1. For every positive scalar \(D\) and distinct candidates \(a,b\),
\(S_{Dw}(a,b)=D S_w(a,b)\).
Consequently, \(W_{Dw}=W_w\).
Proof. For each simple directed path \(p\),
\(\min_{(u,v)\in p}Dw(u,v)=D\min_{(u,v)\in p}w(u,v)\),
because \(D>0\). Taking the maximum over the finitely many simple paths gives the asserted equality. Multiplication by \(D>0\) preserves every comparison \(S_w(a,b)\geq S_w(b,a)\), so it preserves the winning set. \(\square\)
Lemma 2. A successful rational coalition assignment exists if and only if there is a ranking \(\rho\in\mathcal R(C)\) such that assigning the entire mass \(\alpha\) to \(\rho\) makes \(c\) the unique winner.
Proof. The reverse implication is immediate: setting \(y_\rho=\alpha\) and all other coalition masses to zero is an admissible rational assignment.
For the forward implication, suppose a successful rational assignment \(y\) exists. Its positive support is finite because \(\mathcal R(C)\) is finite. Let \(D\) be a positive common multiple of the denominators of all positive nonmanipulator masses and all positive coalition masses.
Construct an integer weighted election as follows:
Every listed weight is a positive integer. The coalition is nonempty because \(\alpha>0\), and its total weight is
\(\sum_{\pi:y_\pi>0}Dy_\pi=D\alpha\).
The resulting margin function is exactly \(Dw\), where \(w\) is the margin function under the assumed successful rational assignment. Lemma 1 therefore shows that \(c\) is the unique winner of this integer weighted election.
Apply the integer unanimity property. There is a ranking \(\rho\) such that all these manipulators can vote \(\rho\) while retaining \(c\) as unique winner. Since their weights sum to \(D\alpha\), this unanimous integer profile is precisely the positive scaling by \(D\) of the rational profile with nonmanipulator masses \(\nu\) and coalition mass \(\alpha\) concentrated on \(\rho\). Lemma 1 again preserves the winning set upon scaling down. \(\square\)
The denominator \(D\) in this proof can depend on the hypothetical successful assignment. The algorithm does not construct \(D\); it is used only to establish the equivalence.
First handle the elementary cases. If \(m=1\), the answer is yes. If \(\alpha=1\), there are no positive nonmanipulator masses; putting all coalition mass on any ranking with \(c\) first gives \(w(c,b)=1\) and \(w(b,c)=-1\) for every \(b\neq c\). Every path ending at \(c\) then has strength at most \(-1\), while \(S(c,b)\geq1\), so the answer is yes.
Now suppose \(m\geq2\) and \(0<\alpha<1\). Write the input fractions as
\(\alpha=a_0/b_0,\qquad \nu_i=a_i/b_i\quad(1\leq i\leq\tau)\),
with positive integer denominators. Set
\(D_0=\prod_{i=0}^{\tau}b_i\).
Create an integer weighted manipulation instance with:
These weights are positive integers.
For any ranking \(\rho\) of the single manipulator, the resulting integer margins are \(D_0\) times the margins obtained by assigning rational mass \(\alpha\) to \(\rho\). Lemma 1 shows that the two profiles have identical winning sets. Together with Lemma 2, this proves
\(\text{successful rational assignment exists}\ \Longleftrightarrow\ \text{the constructed integer instance admits successful manipulation}.\)
We therefore run the integer weighted unique-winner algorithm on this instance.
The product \(D_0\) has polynomial bit length: indeed,
\(\log_2 D_0=\sum_{i=0}^{\tau}\log_2 b_i\leq L\).
Since every input mass is at most one, every constructed weight is at most \(D_0\), hence has \(O(L)\) bits. Computing the product and the scaled integer weights uses polynomial-time integer arithmetic.
The constructed instance has exactly \(\tau\) nonmanipulators and one manipulator. Rankings are copied directly; neither voters nor the full ranking space are expanded. Its encoding length is therefore polynomial in \(m,\tau,L\).
The weighted algorithm uses polynomially many arithmetic operations, with finite bounds selected from margins plus total coalition weight. These quantities have \(O(L)\) bits on the constructed instance, so its arithmetic also has polynomial bit complexity. [Müller–Kosub, Algorithms 1–2 and Lemma 5](https://arxiv.org/pdf/1808.09226).
Thus the reduction and decision algorithm run in time polynomial in \(m,\tau,L\). On a yes-instance, a successful assignment can also be returned compactly: one ranking carrying mass \(\alpha\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly: the rational-mass decision problem is in \(\mathrm P\), with running time polynomial in \(m,\tau,L\). The essential unanimity property is supported by the cited source, and the reduction preserves the exact unique-winner condition. I found no mathematical gaps or false steps.
The prover states the external result with the necessary hypotheses: positive integer voter weights, prescribed coalition weights, unrestricted strict rankings, and constructive manipulation in the unique-winner model.
Theorem 2 establishes polynomial-time decision; Algorithm 2 constructs a common ranking for all manipulators, and footnote 5 explicitly confirms that any successful manipulation can be achieved unanimously. The cited result therefore supports both assertions used by the prover. [Müller–Kosub, Section 3](https://arxiv.org/pdf/1808.09226)
This is essential: polynomial-time solvability alone would not justify the subsequent reduction to one manipulator.
Section 2 of the source uses positive integer voter weights, strict total rankings, the complete directed graph with signed pairwise margins, maximum bottleneck path strengths, and the same weak comparisons defining the winning set. Its unique-winner condition is precisely that this set is a singleton. [Müller–Kosub, Section 2](https://arxiv.org/pdf/1808.09226)
The prover’s cycle-removal observation is correct for paths between distinct endpoints. Removing a repeated-vertex segment leaves a directed walk with the same endpoints and removes edges, so its minimum edge weight cannot decrease. Repetition can be eliminated until a simple path remains. This reasoning also applies to zero and negative margins.
For a positive scalar \(D\), multiplication commutes with both the minimum along each path and the maximum over paths. For distinct endpoints, the complete graph supplies at least one path, and there are finitely many simple paths. Thus the extrema are well-defined and
\(S_{Dw}(a,b)=D S_w(a,b)\).
Since positive multiplication preserves every weak comparison, it preserves the entire winning set, including ties. The lemma therefore preserves uniqueness exactly.
The reverse direction is immediate and respects rationality because \(\alpha\) is rational.
In the forward direction, there are finitely many rankings, so any rational assignment has finitely many positive coordinates. A positive common denominator exists for these coordinates and the listed nonmanipulator masses. Every resulting voter weight is a positive integer, and the coalition is nonempty because \(\alpha>0\).
Scaling the profile scales every margin by the same positive factor. The initial integer instance is consequently successful. The unanimity property applies to its prescribed manipulator weights and produces a common ranking. Their combined weight is exactly \(D\alpha\), so scaling back yields precisely the claimed unanimous rational assignment.
The possibly enormous support or denominator of the hypothetical assignment does not compromise the complexity argument: this construction establishes existence only and is not executed by the decision algorithm.
When \(m=1\), the winning condition is vacuous and the sole candidate is the unique winner.
When \(\alpha=1\), all nonmanipulator masses are zero. With \(c\) ranked first, every outgoing margin from \(c\) is \(1\), and every incoming margin is \(-1\). Every path into \(c\) contains an incoming final edge, while the direct path from \(c\) to each rival has strength \(1\). Hence \(c\) defeats every rival in the strongest-path comparison, and each rival fails its comparison against \(c\).
The product \(D_0\) includes the denominator of \(\alpha\) and every supported nonmanipulator mass. It therefore produces positive integer weights for all constructed voters.
For each possible ranking of the single manipulator, the integer profile is exactly a positive scaling of the corresponding unanimous rational profile. Lemma 1 preserves its winning set, and Lemma 2 supplies the equivalence with unrestricted rational manipulation.
In the remaining case \(0<\alpha<1\), the nonmanipulator mass is positive, so its support is nonempty. The constructed coalition also has positive weight. The integer theorem’s hypotheses are satisfied.
The denominator product satisfies \(\log_2 D_0\leq L\); its binary length is therefore at most \(L+1\). Each scaled weight is at most \(D_0\), since every input mass is at most one. Exact multiplication and division consequently involve polynomially many bits.
The reduction creates only \(\tau+1\) voters and copies the supported rankings. It does not expand integer weights into unit voters or enumerate all rankings.
Lemma 5 bounds the algorithm’s updates by polynomially many choices of shifted margins, rather than by weight magnitude. Algorithms 1–2 use bounded integer arithmetic and comparisons. [Müller–Kosub, Algorithms 1–2 and Lemma 5](https://arxiv.org/pdf/1808.09226)
On this constructed instance, those quantities have \(O(L)\) bits, establishing polynomial bit complexity as claimed.
No additional mathematical 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.