Answer: \(\mathrm{TC}\): polynomial-time solvable, including an attaining rational distribution. For each fixed \(k\geq4\), computing the value for \(k\)-kings is NP-hard. The degree identity holds with probability tending to one, simultaneously for all candidates and all admissible \(k\), as well as for \(\mathrm{TC}\).
Theorem 18 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet S ∈{TC, k-kings}, where 4 ≤k ≤ n −1. Assume that a tournament T is generated according to the uniform random model. Then, with high probability, the following holds for all x ∈V (T) simultaneously: MoVS(x, T) = min outdeg(x), min y∈V (T ):y̸=x indeg(y) .
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), ranking types \(T\), a rational society distribution \(\mu\) with no pairwise majority ties, a target \(x\), and \(S\in\{\mathrm{TC},k\text{-kings}\}\), compute the signed minimum number of pairwise majority orientations that must be reversed to change \(x\)’s status in \(S(T_\mu)\), together with a rational distribution \(\nu\) attaining it; under a uniform-random induced tournament, determine whether the degree formula of Theorem 18 holds with high probability.
Let \(C\) contain \(m\geq5\) candidates. Types are strict linear rankings of \(C\). A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible rankings. Masses sum to \(1\); let \(L\) be the total input bit length.
For a distribution \(\rho\), define \(T_\rho\) by \(a\to b\) exactly when \(\rho(\{r:a\succ_r b\})>1/2\). Require no pairwise majority ties. Input also includes \(x\in C\) and \(S\in\{\mathrm{TC},k\text{-kings}\}\), with integer \(4\leq k\leq m-1\) in the latter case.
Here \(\mathrm{TC}\) consists of candidates reaching every other candidate by a directed path; \(k\)-kings reach every other candidate within \(k\) edges.
An admissible replacement \(\nu\) is any rational distribution over strict rankings of \(C\), allowing new types, with no majority ties. Its cost \(d(\mu,\nu)\) is the number of unordered candidate pairs oriented differently in \(T_\mu\) and \(T_\nu\); there is no additional cost for changing masses.
Let \(M_S(x,\mu)\) be the minimum such cost over replacements changing membership of \(x\) in \(S\), positive for an initial winner and negative otherwise. The computational problem returns this signed value and an attaining \(\nu\), represented by its rational support.
Is this computational problem solvable in polynomial time in \(m,\tau,L\) and \(k\), or is computing its value NP-hard, separately for \(\mathrm{TC}\) and each fixed \(k\geq4\)?
If every orientation of \(T_\mu\) is an independent fair coin, does \(M_S(x,\mu)=\min\{\operatorname{outdeg}_{T_\mu}(x),\min_{y\neq x}\operatorname{indeg}_{T_\mu}(y)\}\) hold simultaneously for all \(x\), with probability tending to \(1\) as \(m\to\infty\)?
Known tournament results: the displayed degree formula holds with high probability under independent fair orientations ([source](https://arxiv.org/html/2012.02657v3)).
Exact destructive reversal cost is polynomial-time computable for top-cycle winners and NP-hard for each fixed \(k\geq4\) for \(k\)-king winners ([source](https://ojs.aaai.org/index.php/AAAI/article/download/5554/5410)); these statements concern tournament input rather than rational-society input with a distribution witness.
The problem is polynomial-time solvable for \(\mathrm{TC}\), including an attaining rational distribution. For every fixed \(k\geq4\), computing its value for \(k\)-kings is NP-hard, even when \(x\) is initially a winner.
The proposed degree identity holds with probability tending to one, simultaneously for every candidate. In fact, it holds simultaneously for \(\mathrm{TC}\) and every \(k\) with \(4\leq k\leq m-1\).
We first prove the representation fact needed to transfer tournament results to societies.
Lemma. Given any tournament \(U\) on \(m\) candidates, one can construct, in polynomial time, a rational distribution \(\rho_U\) such that \(T_{\rho_U}=U\). Its support size is at most \(m(m-1)+2\), its masses are dyadic rationals, and its total encoding length is polynomial in \(m\).
Proof. Let \(N=\binom m2\). For each edge \(a\to b\) of \(U\), list the remaining candidates in an arbitrary order \(w_1,\ldots,w_{m-2}\), and introduce the two rankings
\[ a\succ b\succ w_1\succ\cdots\succ w_{m-2}, \qquad w_{m-2}\succ\cdots\succ w_1\succ a\succ b. \]
Both rank \(a\) above \(b\). For every other unordered pair, their preferences cancel: candidates among the \(w_i\) appear in opposite orders, and each \(w_i\) appears below both \(a,b\) in one ranking and above both in the other.
Let \(Q\) be the least power of two satisfying \(Q\geq2N\). Give each of these \(2N\) ranking occurrences mass \(1/Q\). If \(Q>2N\), choose an arbitrary ranking \(r\) and its reverse, and give each mass \((Q-2N)/(2Q)\). Their pairwise contributions cancel, and the total mass becomes one.
For a distribution \(\rho\), define its pairwise margin by \(\Delta_\rho(a,b)=\rho(a\succ b)-\rho(b\succ a)\). For every edge \(a\to b\) of \(U\), the construction gives \(\Delta_{\rho_U}(a,b)=2/Q>0\). Indeed, its own gadget contributes \(2/Q\), and every other gadget and the padding contribute zero. Thus \(T_{\rho_U}=U\), without ties.
Merge identical rankings and omit zero masses. Since \(Q\) is even, the padding masses also have denominator \(Q\). Every resulting numerator is at most \(Q\), and \(Q<4N\), so each mass uses \(O(\log m)\) bits. There are at most \(2N+2\) rankings, each representable using \(O(m\log m)\) bits after numbering the candidates. The total encoding length is therefore \(O(m^3\log m)\). All construction and merging operations take polynomial time. \(\square\)
Write \(T=T_\mu\). For tournaments \(T,U\) on \(C\), let \(h(T,U)\) count the unordered pairs whose orientations differ.
Define the unsigned tournament optimum by
\[ D_S(x,T)= \min\bigl\{ h(T,U): [x\in S(U)]\neq[x\in S(T)] \bigr\}. \]
This minimum exists: there are finitely many tournaments, and membership can be changed by making \(x\) a Condorcet loser if it is initially a winner, or a Condorcet winner otherwise.
Every admissible replacement \(\nu\) induces a tournament \(U=T_\nu\), and its cost is exactly \(h(T,U)\). Consequently, the minimum society cost is at least \(D_S(x,T)\).
Conversely, realize an optimal tournament \(U\) by the distribution \(\rho_U\) from Section 1. It is admissible and has cost \(h(T,U)=D_S(x,T)\). Hence
\[ M_S(x,\mu)= \begin{cases} D_S(x,T_\mu),&x\in S(T_\mu),\\ -D_S(x,T_\mu),&x\notin S(T_\mu). \end{cases} \]
In particular, every optimum has an attaining distribution of polynomial encoding length.
The input tournament can itself be computed in polynomial time. Read each ranking into a table of candidate positions and sum the masses supporting each ordered pair. For binary-encoded rational masses, a common denominator can be formed by multiplying the input denominators; its bit length is at most their total bit length, hence at most \(L\). Exact comparisons with \(1/2\) therefore require only polynomially many bit operations. The no-tie hypothesis ensures exactly one orientation per pair.
Membership in either solution is also polynomial-time decidable: compute directed distances from \(x\), and check reachability or the distance bound \(k\).
The following argument applies to both solutions in the question.
Suppose \(x\notin S(T)\). Set
\[ A=\{a:x\to a\}, \qquad B=\{b:b\to x\}. \]
The set \(B\) is nonempty, since otherwise \(x\) would reach every other candidate in one edge.
Choose \(y\in B\) with maximum outdegree in the subtournament induced by \(B\). We claim that \(y\) reaches every member of \(B\) within two edges.
For \(z\in B\setminus\{y\}\), this is immediate if \(y\to z\). Otherwise \(z\to y\). If there were no path \(y\to w\to z\) within \(B\), then \(z\) would beat every outneighbor of \(y\) in \(B\), as well as \(y\). Thus its outdegree in \(B\) would exceed that of \(y\), contradicting the choice of \(y\).
Now reverse only \(y\to x\). In the resulting tournament, \(x\) still reaches every member of \(A\) directly, and it reaches every member of \(B\) through \(y\) within three edges. Thus \(x\) becomes a \(3\)-king, and therefore belongs to \(\mathrm{TC}\) and to every \(k\)-king solution considered here.
Zero reversals cannot change membership, so the optimum is exactly one. Consequently, \(M_S(x,\mu)=-1\) for every initial non-winner. This construction also supplies an attaining replacement through Section 1.
It remains to handle \(x\in\mathrm{TC}(T)\).
For \(A\subseteq C\), define its outgoing edge boundary by
\[ \delta_T^+(A)= \{(a,b)\in E(T):a\in A,\ b\notin A\}. \]
We prove the exact formula
\[ D_{\mathrm{TC}}(x,T)= \min_{\substack{x\in A\\A\subsetneq C}} |\delta_T^+(A)|. \]
Upper bound. Take any such \(A\) and reverse every edge in \(\delta_T^+(A)\). Every edge between \(A\) and its complement now points into \(A\): originally outgoing edges were reversed, and originally incoming edges were retained. Hence no vertex of \(A\), including \(x\), can reach its complement. These reversals remove \(x\) from the top cycle.
Lower bound. Let \(U\) be any tournament obtained by reversals that remove \(x\) from the top cycle. Let \(A\) be the vertices reachable from \(x\) in \(U\), including \(x\). Since \(x\) is no longer a top-cycle member, \(A\subsetneq C\).
There is no edge in \(U\) from \(A\) to its complement: such an edge would make its endpoint reachable. Therefore every original edge in \(\delta_T^+(A)\) must have been reversed. The reversal cost is at least \(|\delta_T^+(A)|\), proving the lower bound.
To compute this minimum, regard \(T\) as a directed network with capacity one on every arc. For each \(y\neq x\), compute a minimum directed \(x\)-\(y\) cut. The standard max-flow/min-cut theorem applies to this finite network with nonnegative integral capacities and gives a minimum cut in polynomial time.
Every proper set containing \(x\) excludes some \(y\), so the minimum over these \(m-1\) cuts is exactly the displayed optimum. Retain an optimal cut set \(A\), reverse \(\delta_T^+(A)\), and realize the resulting tournament using Section 1.
Together with the non-winner construction, this returns both the signed value and an attaining rational distribution in polynomial time in \(m,\tau,L\).
We use the supplied tournament hardness result in its precise applicable form:
For every fixed \(k\geq4\), computing the minimum destructive reversal cost of an initially winning \(k\)-king in an unweighted tournament is NP-hard.
This is Theorem 6 of [Brill, Schmidt-Kraepelin, and Suksompong, *Refining Tournament Solutions via Margin of Victory*](https://ojs.aaai.org/index.php/AAAI/article/download/5554/5410).
Fix \(k\geq4\), and take an instance consisting of a tournament \(T\) and an initial \(k\)-king \(x\). Construct \(\mu=\rho_T\) using Section 1. This transformation is polynomial-time, produces a society of polynomial support size and encoding length, and guarantees \(T_\mu=T\) without ties.
Section 2 shows that the society’s signed value is exactly the original destructive reversal optimum; its sign is positive because \(x\) is initially a winner. Thus a polynomial-time algorithm for the society value would compute the NP-hard tournament value in polynomial time.
This proves NP-hardness even for polynomial-support dyadic societies and initially winning candidates. Requiring an attaining distribution cannot make the value computation easier.
For clarity, the endpoint \(k=m-1\) equals \(\mathrm{TC}\), since any reachable vertex has a simple path of length at most \(m-1\). That endpoint is polynomial-time solvable. The hardness statement concerns each fixed \(k\geq4\) as \(m\) grows; the problem allowing \(k\) as input is also NP-hard because it includes the fixed case \(k=4\).
Let \(T\) have independent fair orientations, and define
\[ g_T(x)= \min\left\{ \operatorname{outdeg}_T(x), \min_{y\neq x}\operatorname{indeg}_T(y) \right\}. \]
Theorem 18 of [Brill, Schmidt-Kraepelin, and Suksompong, *Margin of Victory in Tournaments: Structural and Experimental Results*](https://arxiv.org/html/2012.02657v3) states that, for \(\mathrm{TC}\) and for \(k\)-kings with \(4\leq k\leq m-1\), the signed tournament margin equals \(g_T(x)\) simultaneously for all \(x\), with probability tending to one. Section 2 transfers this assertion exactly to societies.
We can also strengthen the quantifiers to cover all admissible \(k\) simultaneously.
First, with probability tending to one, every candidate is a \(2\)-king. For a fixed ordered pair \(x,y\), failure to reach \(y\) within two edges requires \(y\to x\) and, for each other candidate \(z\), the failure of \(x\to z\to y\). Independence gives probability \(\frac12(3/4)^{m-2}\). A union bound therefore bounds the probability that some candidate is not a \(2\)-king by
\[ \frac{m(m-1)}2\left(\frac34\right)^{m-2}, \]
which tends to zero.
Apply the cited theorem separately to \(4\)-kings and \(\mathrm{TC}\). By a union bound, their identities and the preceding all-winner event hold jointly with probability tending to one.
On that event, every candidate is initially a winner for every solution under consideration. Moreover,
\[ 4\text{-kings}(U)\subseteq k\text{-kings}(U)\subseteq \mathrm{TC}(U) \]
for every tournament \(U\). Thus removing \(x\) from \(\mathrm{TC}\) also removes it from \(k\)-kings, and removing it from \(k\)-kings also removes it from \(4\)-kings. Taking minimum reversal costs yields
\[ D_{4\text{-kings}}(x,T) \leq D_{k\text{-kings}}(x,T) \leq D_{\mathrm{TC}}(x,T). \]
Both endpoint costs equal \(g_T(x)\), so every intermediate cost does too. The society–tournament equivalence completes the claimed simultaneous identity.
⟨structured verdict parsed — rendered above⟩
The prover resolves all parts of the task. The realization construction, exact transfer of costs, top-cycle algorithm, hardness reduction, and probabilistic argument are correct. No major or minor mathematical issues were found.
The two rankings associated with an edge \(a\to b\) both prefer \(a\) to \(b\). Their preferences cancel on every other pair:
Thus each gadget contributes margin \(2/Q\) to its designated edge and zero to all other pairs.
The mass calculation is correct. The gadgets have total mass \(2N/Q\), and the two padding rankings add total mass \((Q-2N)/Q\). Their contributions cancel because they are reverses.
The denominator claim also holds: \(Q\) and \(2N\) are even, so \((Q-2N)/(2Q)\) has an integer numerator when expressed with denominator \(Q\). Merging identical rankings preserves all margins and the total mass. Every retained mass is positive and dyadic.
The stated bounds \(2N+2=m(m-1)+2\) and \(Q<4N\) are valid. Consequently, the support and rational encoding have polynomial size, and the construction can be performed in polynomial time.
Assessment: Correct, including normalization, strict majorities, and output encoding.
Both directions of the optimum comparison are justified:
The minimum exists because there are finitely many tournaments and membership can always be changed. For the permitted candidate counts, a Condorcet loser cannot reach any other candidate, while a Condorcet winner reaches every other candidate directly. These observations apply to both solutions.
The sign convention matches the task exactly. The claim about a polynomial-size attaining distribution concerns existence; Section 4 subsequently supplies an algorithm to find one for the top cycle.
Exact extraction of the input tournament is polynomial-time. Multiplying the input denominators gives a common denominator whose bit length is bounded by the sum of their bit lengths. Numerator arithmetic and comparisons therefore remain polynomial in \(L\). Reachability and bounded-distance membership are also polynomial-time decidable.
Assessment: Correct. Allowing new types and imposing no mass-change cost are essential hypotheses, and both are explicitly provided by the task.
The maximum-outdegree argument in the subtournament on \(B\) is valid. If \(z\to y\) and no intermediate vertex gives a two-edge path from \(y\) to \(z\), then \(z\) beats every outneighbor of \(y\), as well as \(y\). Its outdegree would therefore be strictly larger.
Reversing \(y\to x\) preserves all edges within \(B\) and all direct edges from \(x\) to \(A\). Afterward, \(x\) reaches \(y\) directly and every other member of \(B\) within three edges. This also handles a singleton \(B\).
Zero changes cannot alter membership because membership depends only on the tournament. Hence the minimum cost is exactly one, and its signed value is \(-1\).
Assessment: Correct for both the top cycle and every permitted \(k\).
The cut formula has valid upper and lower bounds.
For the upper bound, reversing precisely the outgoing boundary of a proper set containing \(x\) makes every crossing edge point into that set. No path from \(x\) can leave it.
For the lower bound, the vertices reachable from \(x\) in the modified tournament form a proper set with no outgoing edge. Every original outgoing boundary edge must therefore have changed orientation. Other reversed edges can only increase the cost.
The optimization over directed \(x\)-\(y\) cuts is exact: every proper set containing \(x\) excludes some \(y\), and every such cut is a proper set containing \(x\). The network is finite with nonnegative integral capacities, so the stated max-flow/min-cut application and polynomial-time computation are valid.
Retaining a minimum cut, reversing its boundary, and applying Section 1 produces an optimal rational witness.
Assessment: Correct polynomial-time algorithm for the complete requested output.
The cited [Theorem 6](https://ojs.aaai.org/index.php/AAAI/article/download/5554/5410) establishes NP-hardness of computing the unweighted margin of a \(k\)-king for every constant \(k\geq4\). This matches the initially winning instances used in the reduction.
The realization map has polynomial output length and preserves the tournament exactly. Section 2 therefore preserves the optimum exactly, with positive sign. The reduction establishes hardness of the value alone, as required.
The endpoint distinction is correct: \(k=m-1\) gives the top cycle, whereas fixed-\(k\) hardness concerns growing \(m\). These statements do not conflict. Allowing \(k\) as input includes the hard fixed case.
Assessment: Correct.
The statement attributed to [Theorem 18](https://arxiv.org/html/2012.02657v3) matches the source: under independent fair orientations, the degree formula holds simultaneously for all candidates with probability tending to one, for either specified solution.
The additional simultaneous-in-\(k\) argument is also valid:
The signed-value issue is handled by the all-winner event. Section 2 then transfers the identity to societies without imposing any additional distributional assumption on their masses.
Assessment: Correct, including the stronger simultaneous claim.
None. The answer establishes polynomial-time solvability for the top cycle and hardness for each fixed \(k\geq4\). The complexity status below records the hard branch; this is not a dependence on input representation.
⟨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.