Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 4.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateweakCondorcet-CCRPC- h TE TP i are in P, but weakCondorcet-CCREPC-TP is NP-complete. Briefly, what is behind the change in complexity here is that we can make one of the subelections represent a vertex cover and we use equipartition to limit the size of that vertex cover. The reason the same approach does not work also for Condorcet elections is that we crucially need that we can have multiple winners.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(C\), \(p\in C\), and a binary-rational distribution \(\mu\) over the supported complete rankings of \(C\), decide whether \(C\) has a split \(C_1\sqcup C_2\) with \(\bigl||C_1|-|C_2|\bigr|\le 1\) such that each side advances its sole weak Condorcet winner, if one exists, according to \(q_\mu(a,b)=\sum_{t:\,a\succ_t b}\mu_t\), and \(p\) is the sole weak Condorcet winner among the candidates who advance.
Given a candidate set \(C\) with \(m=|C|\geq 1\) and \(p\in C\), a society is given by its support: the list of the \(\tau\) distinct strict complete rankings of \(C\) with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length, and state running times in \(m,\tau,L\).
For distinct candidates define \(q_\mu(a,b)=\sum_{t:\,a\succ_t b}\mu_t\). On a candidate subset \(S\), the weak Condorcet winners are \(W_\mu(S)=\{a\in S:\ q_\mu(a,b)\geq 1/2\text{ for every }b\in S\setminus\{a\}\}\); in particular, \(W_\mu(\varnothing)=\varnothing\) and a singleton's candidate wins.
Choose a partition \(C=C_1\sqcup C_2\) satisfying \(\bigl||C_1|-|C_2|\bigr|\leq 1\). Each side advances its winner exactly when \(|W_\mu(C_i)|=1\), and otherwise advances nobody (ties eliminate). If \(A\) is the set of advancing candidates, the partition succeeds exactly when \(W_\mu(A)=\{p\}\). Every stage uses the entire unchanged society, with rankings restricted to the candidates participating in that stage.
Is deciding whether a successful partition exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For explicit finite electorates, weak Condorcet runoff candidate partition without the size constraint is in \(\mathrm{P}\) under both ties eliminate and ties promote; with equipartition, the ties-promote version is NP-complete. The ties-eliminate equipartition version was explicitly left unclassified in the [verified result](https://arxiv.org/pdf/1410.2652v1). No classification of the rational-mass formulation above was located.
The decision problem is \(\mathrm{NP}\)-complete. Hardness holds even when all masses are dyadic rationals, the support size satisfies \(\tau=O(m)\), and \(m\) is even.
The case \(m=1\) is trivially successful. The proof below concerns unbounded candidate sets.
Write \(a\to b\) when \(q_\mu(a,b)>1/2\). Because every ranking is strict and complete,
\[ q_\mu(a,b)+q_\mu(b,a)=1. \]
Consequently, a candidate belongs to \(W_\mu(S)\) exactly when no candidate in \(S\) has an arc into it. Restricting rankings to a candidate subset preserves all comparisons between the remaining candidates.
A partition is a polynomial-size certificate. Its balance, preliminary winner sets, advancing candidates, and final winner set can all be checked from the pairwise comparison table.
For an explicit arithmetic bound, write each mass as \(\mu_t=a_t/b_t\), and let \(D=\prod_{t=1}^{\tau}b_t\). The bit length of \(D\) is \(O(L)\). Compute the integer weights \(w_t=a_t(D/b_t)\), and, for every ordered candidate pair, sum the weights of rankings placing the first candidate above the second. Comparing twice this sum with \(D\) determines the pairwise outcome exactly.
Using schoolbook integer arithmetic, this computation and certificate verification take
\[ O\!\left(\tau L^2+m^2\tau L\right) \]
bit operations. Thus the problem belongs to \(\mathrm{NP}\).
We reduce from Exact Cover by 3-Sets, abbreviated X3C, using its standard \(\mathrm{NP}\)-completeness theorem.
An instance consists of a universe \(U\), with \(|U|=3k\), and a family \(S_1,\ldots,S_n\) of three-element subsets of \(U\). The question is whether exactly \(k\) of these sets cover every element exactly once.
We may assume \(k\geq1\) and \(n\geq k\). Instances with \(k=0\) are trivially yes, and instances with \(n<k\) are trivially no. These can be mapped to fixed yes and no elections, respectively: a singleton election is yes, while two candidates with a unanimous ranking placing the other candidate above \(p\) give a no instance.
We first ensure that
\[ k\leq n\leq2k. \]
Given an instance with \(n\geq k\), let \(d=\max\{0,n-2k\}\). Add \(d\) mutually disjoint triples of fresh elements to the universe, and add exactly those \(d\) triples to the family. Each fresh element occurs only in its added triple, so every exact cover must select all the added triples. Therefore this padding preserves the answer.
The new parameters are \(k'=k+d\) and \(n'=n+d\). They satisfy \(k'\leq n'\leq2k'\). Indeed, if \(n>2k\), then \(n'=2(n-k)=2k'\); otherwise nothing changes. The padding is polynomial. Henceforth, rename the padded parameters \(k,n\).
Set
\[ \ell=3k+1,\qquad g=(2k-n+1)\ell. \]
Since \(n\leq2k\), we have \(g\geq\ell\geq4\).
Construct the following disjoint candidate sets:
Specify precisely these strict majority arcs:
\[ z_{i,j}\to z_{i,j+1\bmod\ell}. \]
Every other pairwise contest is tied. Section 5 constructs strict complete rankings and positive dyadic masses realizing these outcomes.
In particular, \(p\) ties every nonguard candidate, no candidate defeats a guard, and the sole candidate that defeats a cycle candidate is its predecessor in its own cycle.
The total number of candidates is
\[ m=1+3k+n\ell+g =\ell+n\ell+(2k-n+1)\ell =2(k+1)\ell. \]
Thus every permitted partition has both sides of size
\[ K=(k+1)\ell=1+k\ell+3k. \]
Suppose a partition succeeds, and let \(P\) be its side containing \(p\). Let \(Q=C\setminus P\).
Since \(W_\mu(A)=\{p\}\), the candidate \(p\) must belong to the advancing set \(A\). Under ties eliminate, this requires
\[ W_\mu(P)=\{p\}. \]
No guard can belong to \(P\), because every guard strictly defeats \(p\). Therefore \(G\subseteq Q\).
We now determine the possible contents of \(P\).
Each cycle block is either entirely in \(P\) or entirely outside \(P\). To prove this, suppose \(z_{i,j}\in P\). If its predecessor were absent from \(P\), then \(z_{i,j}\) would have no incoming arc in \(P\), because that predecessor is its only strict defeater. It would then belong to \(W_\mu(P)\), contradicting \(W_\mu(P)=\{p\}\). Its predecessor must therefore also belong to \(P\). Repeating this argument around the cycle puts all of \(Z_i\) in \(P\).
Let \(h\) be the number of complete cycle blocks in \(P\), and let \(x\) be the number of element candidates in \(P\). There are no guards in \(P\), so balance gives
\[ 1+h\ell+x=K=1+k\ell+3k. \]
Hence
\[ (h-k)\ell=3k-x. \]
The right-hand side is an integer between \(0\) and \(3k=\ell-1\). The left-hand side is a multiple of \(\ell\). Their equality therefore forces
\[ h=k,\qquad x=3k. \]
Thus \(P\) contains exactly \(k\) cycle blocks and every element candidate.
Every element candidate \(e_u\) must have an incoming arc in \(P\), since it cannot be another weak Condorcet winner alongside \(p\). Its only possible incoming arcs are from candidates \(z_{i,0}\) with \(u\in S_i\). Consequently, the \(k\) sets corresponding to the selected cycle blocks cover all of \(U\).
These \(k\) sets have total cardinality \(3k=|U|\). Since they cover \(U\), each element must occur in exactly one selected set: otherwise the total number of element occurrences would exceed \(3k\). They therefore form an exact cover.
Conversely, let \(I\subseteq\{1,\ldots,n\}\) index an exact cover, with \(|I|=k\). Choose
\[ P=\{p\}\cup\{e_u:u\in U\}\cup\bigcup_{i\in I}Z_i, \qquad Q=C\setminus P. \]
Then \(|P|=1+3k+k\ell=K\), and \(|Q|=K\), so the partition is balanced.
Within \(P\):
It follows that \(W_\mu(P)=\{p\}\), so \(p\) advances.
All guards belong to \(Q\). No candidate defeats any guard, so every guard is a weak Condorcet winner in \(Q\). Since \(g\geq4\), we have \(|W_\mu(Q)|\geq2\), and ties eliminate advances nobody from \(Q\).
Thus \(A=\{p\}\), whose unique weak Condorcet winner is \(p\). The partition succeeds.
This proves the equivalence between the X3C instance and the constructed election, provided the specified outcomes are realizable.
We give the realization explicitly.
For each specified arc \(a\to b\), choose a fixed ordering \(R\) of the other candidates and introduce the two rankings
\[ a\succ b\succ R, \qquad R^{\mathrm{rev}}\succ a\succ b. \]
Both rankings place \(a\) above \(b\), giving this pair a vote-count margin of \(2\). Every other pair receives margin \(0\) from these two rankings:
Let \(r\) be the number of specified arcs. Here
\[ r=n\ell+3n+g=O(m). \]
The construction above uses \(2r\) rankings. Choose \(M\) to be the smallest power of two at least \(2r\). Thus \(2r\leq M<4r\). Add reversal pairs of arbitrary complete rankings until the electorate contains exactly \(M\) rankings. This is possible because \(M-2r\) is even, and every reversal pair contributes zero margin to every contest.
The resulting society satisfies
\[ q_\mu(a,b)= \begin{cases} \frac12+\frac1M,&a\to b,\\ \frac12-\frac1M,&b\to a,\\ \frac12,&\text{neither arc is specified}. \end{cases} \]
There are no opposite specified arcs, so these outcomes realize exactly the construction in Section 3.
Give each of the \(M\) voters mass \(1/M\), then coalesce identical rankings. A distinct ranking occurring \(c_t\) times receives mass \(\mu_t=c_t/M\). These masses are positive dyadic rationals and sum to \(1\), as required. Coalescing preserves every pairwise probability.
Since \(M=O(m)\), the resulting support size and encoding length satisfy
\[ \tau=O(m),\qquad L=O(m^2\log m). \]
Generating the rankings and coalescing duplicates by lexicographic sorting takes \(O(m^2(\log m)^2)\) bit operations. After padding, \(k\) is at most the sum of the original parameters, and \(m=2(k+1)(3k+1)\). Thus the entire reduction has polynomial size and running time in the original X3C input length.
The reduction proves \(\mathrm{NP}\)-hardness, and Section 1 proves membership in \(\mathrm{NP}\). Therefore the stated rational-mass problem is \(\mathrm{NP}\)-complete.
The construction also uses only \(O(m)\) explicit voters before coalescing. It therefore establishes the same classification for explicit finite electorates under the stated rules—the ties-eliminate case left open immediately before Theorem 4.4 in the [cited paper](https://arxiv.org/pdf/1410.2652).
⟨structured verdict parsed — rendered above⟩
The proof establishes \(\mathrm{NP}\)-completeness for the problem in USER_TASK. The reduction and rational-mass realization are sound. There is one minor inconsistency in the claimed strengthening to even candidate counts: the preprocessing uses a singleton as its fixed yes instance.
Verified. Strict complete rankings imply
\(q_\mu(a,b)+q_\mu(b,a)=1\). Therefore \(a\) is a weak Condorcet winner on a subset precisely when it has no incoming strict-majority arc within that subset. Tied comparisons correctly create no arcs.
Restricting rankings preserves pairwise probabilities because every stage uses the same masses and retains the relative order of participating candidates.
A partition supplies a polynomial-size certificate. Computing the two preliminary winner sets, applying ties eliminate, and checking the final winner set verifies exactly the stated success condition.
The arithmetic bound is valid:
Thus membership in \(\mathrm{NP}\) is established in the requested parameters.
Verified. The source problem is stated precisely: an explicitly given universe of size \(3k\), three-element subsets, and the existence of an exact cover containing \(k\) sets. This matches the standard NP-complete X3C problem, also stated in the [referenced mathematical literature](https://page.math.tu-berlin.de/~felsner/Paper/diss.pdf).
The padding preserves both directions of the answer. Each fresh element occurs in exactly one added triple, so every exact cover must select every added triple. Removing those triples from a padded exact cover leaves an exact cover of the original universe.
The parameter calculation is correct. When \(n>2k\),
\(d=n-2k\), \(k'=n-k\), and \(n'=2(n-k)=2k'\). Otherwise the parameters remain unchanged. In either case \(k'\leq n'\leq2k'\).
The fixed singleton yes instance and unanimous two-candidate no instance are correct for the unrestricted target. The singleton uses the explicitly permitted empty preliminary side.
Minor issue — even-candidate strengthening. The fixed singleton yes instance has odd candidate count. Consequently, the complete reduction as written does not always output an even-candidate election, although every election produced by the main construction does.
Minimum clarification requested: Make the preprocessing consistent with the even-candidate strengthening, or explicitly justify restricting the hardness source to the nontrivial instances used by the main construction. This does not affect the classification of USER_TASK.
Verified. The bounds \(g\geq\ell\geq4\) follow from \(n\leq2k\) and \(k\geq1\).
The candidate count simplifies correctly:
\(m=1+3k+n\ell+g=2(k+1)\ell\).
Thus every balanced partition of a constructed instance has two sides of size
\(K=(k+1)\ell=1+k\ell+3k\).
The specified arcs have the required structural properties:
Since \(\ell\geq4\), the cycle specification introduces no opposite arcs. The other arc types also introduce no opposite arcs.
Verified step by step.
\((h-k)\ell=3k-x\).
Since \(0\leq x\leq3k\), the right-hand side lies between \(0\) and \(\ell-1\). The only multiple of \(\ell\) in that interval is zero. Thus \(h=k\) and \(x=3k\).
There is no missing assumption about whether \(Q\) advances a candidate: this direction only needs the necessary preliminary uniqueness of \(p\).
Verified. The proposed \(P\) has exactly \(K\) candidates, so its complement also has size \(K\).
Within \(P\), \(p\) has no incoming arc; every cycle candidate has its predecessor present; and every element candidate is defeated by a representative from the exact cover. Therefore \(W_\mu(P)=\{p\}\).
Every guard remains undefeated in \(Q\). Since \(g\geq4\), \(Q\) has multiple weak Condorcet winners and advances nobody under ties eliminate. The final candidate set is therefore \(\{p\}\), which satisfies the exact success condition.
Both directions of the reduction are established.
Verified. For each arc \(a\to b\), the two displayed rankings contribute margin \(2\) to that pair and zero to every other pair:
Margins add across these ranking pairs. Reversal pairs used for padding contribute zero margin throughout.
The arc count \(r=n\ell+3n+g\) is correct and is \(O(m)\). In particular, \(n\ell+g\) counts cycle and guard arcs, and \(3n\) counts incidence arcs.
Here \(r>0\), so choosing the smallest power of two \(M\geq2r\) gives \(2r\leq M<4r\). Both \(M\) and \(2r\) are even, making the reversal-pair padding possible.
A vote-count margin of \(2\) among \(M\) voters gives probability \(1/2+1/M\), exactly as claimed. Unspecified pairs remain tied. Coalescing identical rankings preserves these probabilities and produces positive dyadic masses summing to one.
The bounds \(\tau=O(m)\), \(L=O(m^2\log m)\), and \(O(m^2(\log m)^2)\) bit operations for generation and comparison-based sorting are valid under ordinary binary candidate encoding. Padding and the candidate construction are polynomial in the explicit X3C input length.
The argument proves both NP-hardness and membership in \(\mathrm{NP}\) for the rational-mass problem. It also establishes the explicit-electorate classification because the realization already supplies only \(O(m)\) voters.
The historical comparison is accurate: the cited paper uses the unique-winner model and ties eliminate as specified here, and explicitly leaves this equipartition case open immediately before Theorem 4.4. [Cited paper](https://arxiv.org/pdf/1410.2652v1).
No substantive mathematical gap or false central step was found. The sole requested clarification concerns the preprocessing for the even-candidate strengthening.
⟨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.