Answer: The problem is in \(\mathrm{P}\): accept exactly when \(m\geq 7\). It is decidable in \(O(b)\) time, where \(b\) is the encoding length of \(m\).
Proposition 16 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateWhere φ is the conjunction of all con- straints introduced above, there exists a linear ordinal mar- gin matrix in which the SSV winner is not an SC winner iff SSV[n],1 ∧¬SC1 ∧φ is satisfiable.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\), does there exist a rational distribution \(\mu\) over strict rankings \(\pi \in S_m\), with \(\sum_\pi \mu_\pi = 1\) and pairwise distinct margins \(\Delta_\mu(a,b)\) for distinct ordered pairs \((a,b)\), such that the unique SSV winner is defeated under Split Cycle?
Let \(m\geq1\) and \(X=\{1,\ldots,m\}\). A society is represented by its support: the list of its \(\tau\) strict ranking types with positive binary rational masses, summing to \(1\); \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total encoding length. Define \(\Delta_\mu(a,b)=\mu\{\pi:a\succ_\pi b\}-\mu\{\pi:b\succ_\pi a\}\). Require distinct margins for all distinct ordered pairs with unequal coordinates.
For each nonempty \(Y\subseteq X\), define its SSV winner recursively: a singleton wins; otherwise choose the first coordinate of the ordered pair \((a,b)\), with \(a\neq b\), having greatest margin among those satisfying that \(a\) wins on \(Y\setminus\{b\}\). Include negative margins; deletion restricts rankings and preserves remaining pairwise margins.
The majority graph has an edge \(a\to b\) exactly when \(\Delta_\mu(a,b)>0\). Split Cycle declares this edge a defeat exactly when it is not the weakest edge of any directed cycle containing it. Its winners are the undefeated alternatives.
Given only \(m\), is deciding whether there exists such a rational society whose unique SSV winner is defeated under Split Cycle in P or NP-hard? Measure decision running time in the encoding length of \(m\); any running times involving explicitly represented societies must state their dependence on \(m,\tau,L\).
Known results: existence of a discrete counterexample is equivalent to satisfiability of an explicit Boolean encoding; no counterexample exists for \(m\leq6\), and one exists for every \(m\geq7\). Every ordinal margin ordering is realizable by a finite strict-ranking profile. [Verified source](https://arxiv.org/html/2512.00616v2).
Consequently, the rational-distribution existence problem has exactly the same threshold and is already in P; this is an inference from these verified results, so the requested target is not open.
The decision problem is in \(\mathrm{P}\). More precisely, a society satisfying the requirements exists if and only if \(\boldsymbol{m\geq 7}\).
The proof uses the verified threshold results supplied in the task. Below, we justify their applicability to rational societies and the running time in the encoding length of \(\boldsymbol{m}\).
Write \(\Delta(a,b)=\Delta_\mu(a,b)\). Since every ranking is strict, \(\Delta(b,a)=-\Delta(a,b)\). For \(\boldsymbol{m\geq 2}\), the distinctness requirement therefore excludes zero margins: otherwise the two distinct ordered pairs \(\boldsymbol{(a,b)}\) and \(\boldsymbol{(b,a)}\) would have equal margins.
Define \((a,b)\succ(c,d)\) exactly when \(\Delta(a,b)>\Delta(c,d)\). This is a strict total order on the off-diagonal ordered pairs, and it satisfies ordinal skew-symmetry because
\(\Delta(a,b)>\Delta(c,d)\) if and only if \(\Delta(d,c)>\Delta(b,a)\).
With diagonal margins set to zero, it is a linear ordinal margin matrix in the terminology of the cited paper.
Uniqueness of SSV. We prove by induction on \(\boldsymbol{|Y|}\) that every nonempty subset \(\boldsymbol{Y}\) has exactly one SSV winner. The singleton case follows from the definition. For a larger subset, the induction hypothesis supplies a unique winner \(\boldsymbol{w_b}\) of \(\boldsymbol{Y\setminus\{b\}}\) for every \(\boldsymbol{b\in Y}\). Thus the eligible pairs are precisely \(\{(w_b,b):b\in Y\}\). This set is nonempty, and its margins are distinct, so it has a unique maximum. Its first coordinate is the unique winner.
Consequently, two margin matrices with the same ordering of all off-diagonal margins have the same SSV winner on every subset. Indeed, induction gives identical winners after each deletion, hence identical eligible pairs and an identical maximizing pair. This argument includes negative margins.
They also have the same Split Cycle defeats. Positivity is determined by comparison with the reversed pair:
\(\Delta(a,b)>0\) if and only if \(\Delta(a,b)>\Delta(b,a)\).
Thus the majority graphs coincide. In each directed cycle, the weakest edge is determined by the margin ordering, so the defeats coincide as well.
A finite strict-ranking profile \(\boldsymbol{P}\) has some positive number \(\boldsymbol{N}\) of voters. List only its distinct ranking types \(\pi_1,\ldots,\pi_\tau\), and let \(\boldsymbol{n_i>0}\) be their multiplicities. Assign mass \(q_i=n_i/N\) to \(\boldsymbol{\pi_i}\). These are positive, binary-encoded rational numbers summing to one. For every distinct pair,
\(\Delta_\mu(a,b)=M_P(a,b)/N\),
where \(\boldsymbol{M_P(a,b)}\) is the integer voter-count margin.
Multiplication by the positive factor \(\boldsymbol{1/N}\) preserves distinctness, signs, and every margin comparison. By Section 1, this rational society has exactly the same SSV winner and Split Cycle defeats as the finite profile.
Conversely, suppose a rational society has support masses \(q_1,\ldots,q_\tau\). Choose a positive integer \(\boldsymbol{D}\) divisible by all their denominators. Construct a finite profile containing \(\boldsymbol{Dq_i}\) voters of ranking type \(\boldsymbol{\pi_i}\). Each multiplicity is a positive integer, and their sum is \(\boldsymbol{D}\). Its margins satisfy
\(M_P(a,b)=D\Delta_\mu(a,b)\).
The same preservation argument applies.
Hence the existence of a counterexample is equivalent in the two models. This equivalence imposes no bound on support size, and does not identify \(\boldsymbol{\tau}\) with the number of possible rankings.
The cited paper supplies the following results:
These are precisely the threshold and realization results needed here. [Holliday et al., *Stable Voting and the Splitting of Cycles*, Sections 2 and 4.5](https://arxiv.org/html/2512.00616v2)
For \(\boldsymbol{m\leq 6}\), a society satisfying the distinctness requirement induces a linear ordinal margin matrix. Theorem 17 therefore rules out the requested counterexample. This includes the singleton case, where there is no incoming majority edge.
For \(\boldsymbol{m\geq 7}\), choose the matrix supplied by Theorem 18. Lemma 2 realizes it by a finite profile. Its off-diagonal margins are distinct because the induced ordinal matrix is linear. Normalize its ranking multiplicities as in Section 2. The resulting rational society retains its unique SSV winner and the Split Cycle defeat of that winner.
This proves the asserted threshold in both directions.
Given the binary encoding of \(\boldsymbol{m\geq 1}\), accept exactly when \(\boldsymbol{m\geq 7}\).
If \(\boldsymbol{b}\) denotes the encoding length of \(\boldsymbol{m}\), this comparison takes \(\boldsymbol{O(b)}\) time, so the problem belongs to \(\mathrm{P}\). The algorithm neither constructs nor evaluates a society; it has no input parameters \(\boldsymbol{\tau}\) or \(\boldsymbol{L}\).
The SAT characterization does not imply NP-hardness of this threshold language. Under polynomial-time many-one reductions, NP-hardness here would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output proves the requested result. The rational-society existence problem has threshold \(m\geq 7\), and the proposed decision algorithm runs in polynomial time in the encoding length of \(m\). No major or minor mathematical issues were found.
The identity \(\Delta(b,a)=-\Delta(a,b)\) follows from the definition of the margin. For \(m\geq 2\), a zero off-diagonal margin would make the margins of the distinct ordered pairs \((a,b)\) and \((b,a)\) equal. Thus the exclusion of zero margins is justified.
Distinct off-diagonal margins induce a strict total order on off-diagonal ordered pairs. The stated ordinal skew-symmetry follows by negating both sides of a margin comparison. Extending the numerical margins by zero on the diagonal gives the ordinal margin matrix required by the cited results.
For \(m=1\), off-diagonal distinctness is vacuous. The output correctly handles this case separately when excluding counterexamples.
The induction establishing uniqueness is valid:
The further induction proving that the off-diagonal margin ordering determines every subset winner is also justified. Deletion preserves the comparisons between remaining alternatives, so identical smaller-set winners produce identical eligible pairs and the same maximizing pair.
Nothing in either argument excludes negative margins.
The equivalence
\[
\Delta(a,b)>0 \iff \Delta(a,b)>\Delta(b,a)
\]
is correct by skew-symmetry. Consequently, the margin ordering determines the majority graph.
It also determines the weakest edge in each directed cycle. Thus societies with the same margin ordering have identical Split Cycle defeats. Edges contained in no directed cycle cause no exception: their defeat status is also identical.
Both conversions are valid.
For a finite profile with \(N>0\) voters, each represented ranking type has positive multiplicity \(n_i\), and \(q_i=n_i/N\) is a positive rational mass with a finite binary encoding. The masses sum to one, and every margin is scaled by \(1/N\).
Conversely, for rational support masses, a positive common denominator \(D\) makes every \(Dq_i\) a positive integer. Their sum is \(D\), and the constructed profile scales all margins by \(D\).
Positive scaling preserves distinctness, signs, and comparisons, hence both voting rules. The argument correctly uses \(\tau\) as the number of represented ranking types.
These constructions establish existence equivalence. They make no polynomial-time construction claim, so potentially large multiplicities introduce no complexity gap.
The statements and numbering of Theorem 17, Theorem 18, and Lemma 2 match the [cited paper](https://arxiv.org/html/2512.00616v2). Their hypotheses match the matrices used in the output.
For \(m\leq 6\), the induced matrix satisfies the hypothesis ruling out a defeated SSV winner. For \(m\geq 7\), realization preserves the linear off-diagonal ordering, and normalization preserves both rules. The uniqueness requirement is supplied by the earlier induction.
These applications establish both directions of the claimed threshold. Reliance on the results is authorized explicitly by USER_TASK; reproving them is unnecessary.
Comparing the binary input \(m\) with the fixed integer \(7\) takes \(O(b)\) time, where \(b\) is its encoding length. This proves membership in \(\mathrm{P}\).
The algorithm does not receive or evaluate an explicitly represented society. Therefore no runtime dependence on \(m,\tau,L\) for society processing needs to be supplied.
The final qualification about NP-hardness is correct: polynomial-time many-one NP-hardness of this language would imply \(\mathrm{P}=\mathrm{NP}\). The output does not improperly claim unconditional non-hardness.
None required. The argument resolves the assigned existence decision problem with the stated input-size dependence.
⟨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.