Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 2 — class: hardness
Given a candidate set \(C\), a finite-support rational distribution \(\mu\) over strict rankings of \(C\), with no pairwise-majority ties, and a target \(c^\star\), form \(T_\mu\) by setting \(a\succ_\mu b\) exactly when more than half the mass ranks \(a\) above \(b\). Decide whether \(c^\star\in\mathrm{TEQ}(T_\mu)\).
Let \(C\) be a nonempty candidate set, \(m=|C|\), and \(c^\star\in C\). A society is given by its support: the list of the \(\tau\) distinct strict rankings of \(C\) with positive mass, each mass a binary rational; masses sum to \(1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Assume no pairwise-majority ties. Define \(T_\mu=(C,\succ_\mu)\) by \(a\succ_\mu b\) exactly when the mass ranking \(a\) above \(b\) exceeds \(1/2\).
For \(X\subseteq C\), put \(D_X(y)=\{x\in X:x\succ_\mu y\}\). Define \(\mathrm{TEQ}(\varnothing)=\varnothing\); recursively, let \(xR_Xy\) exactly when \(x\in\mathrm{TEQ}(D_X(y))\).
Writing \(R_X^*\) for reflexive transitive closure, define \(\mathrm{TEQ}(X)=\{x\in X:\forall y\in X,\ yR_X^*x\Rightarrow xR_X^*y\}\). Thus all source strongly connected components are selected, including isolated vertices, and \(\mathrm{TEQ}(T_\mu)=\mathrm{TEQ}(C)\).
Is deciding whether \(c^\star\in\mathrm{TEQ}(T_\mu)\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For explicitly given finite tournaments, TEQ membership is [NP-hard](https://arxiv.org/pdf/0711.2961). Computing TEQ from finite preference profiles is [NP-hard even with seven voters](https://pub.dss.in.tum.de/brandt-research/fewvoters-journal.pdf).
The search identified no result explicitly treating membership with the rational-mass input specified above.
The problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. This holds even when every mass is dyadic, meaning an integer divided by a power of two. Consequently, a polynomial-time algorithm in the total input length \(L\) would imply \(\mathrm{P}=\mathrm{NP}\).
Brandt, Fischer, and Harrenstein prove that, given an explicit finite tournament \(T\) and a designated candidate \(c^\star\), deciding whether \(c^\star\in\mathrm{TEQ}(T)\) is \(\mathrm{NP}\)-hard. Their Definition 2 uses precisely the recursive relation in the question. They define its top cycle as the maximal elements of the asymmetric part of its reflexive transitive closure. For any relation \(R\), this maximality condition is exactly
\(\forall y,\ yR^*x\Rightarrow xR^*y\).
Thus their definition agrees with the question, including selection of all source strongly connected components. [Definition 2 and Theorem 2](https://arxiv.org/pdf/0711.2961).
We therefore need a polynomial-time construction that represents any explicit tournament by a support of distinct rankings with positive binary rational masses.
Let \(T=(C,\succ)\) be an explicit tournament with \(m\geq 2\). Fix an ordering of the candidates.
For each edge \(a\succ b\), list the remaining candidates in that fixed order as \(r_1,\ldots,r_{m-2}\), and create two rankings:
\[ a>b>r_1>\cdots>r_{m-2}, \qquad r_{m-2}>\cdots>r_1>a>b. \]
Here \(>\) denotes the order within a ranking.
Define the comparison margin of a multiset of rankings for an ordered pair \((u,v)\) as the number ranking \(u\) above \(v\), minus the number ranking \(v\) above \(u\).
The two rankings above contribute margin \(2\) to \((a,b)\) and margin \(0\) to every other pair:
There are \(\binom m2\) edges, so the resulting multiset contains \(n_0=m(m-1)\) rankings. For every edge \(a\succ b\), its total comparison margin is exactly \(2\): its own gadget contributes \(2\), and every other gadget contributes \(0\).
Let \(N\) be the smallest power of two satisfying \(N\geq n_0\). Since \(n_0\) and \(N\) are even, \(N-n_0\) is even. Add \((N-n_0)/2\) pairs consisting of an arbitrary ranking and its reverse. Each such pair contributes zero to every comparison margin.
The padded multiset has exactly \(N\) rankings. Merge identical rankings: if ranking \(\rho\) occurs \(k_\rho\) times, assign it mass
\(\mu(\rho)=k_\rho/N\).
This gives a valid support representation:
For any edge \(a\succ b\), let \(A\) and \(B\) count padded rankings placing \(a\) above \(b\) and \(b\) above \(a\), respectively. Since \(A+B=N\) and \(A-B=2\), the mass placing \(a\) above \(b\) is
\(A/N=1/2+1/N>1/2\).
Merging duplicates does not change this mass. Therefore there are no majority ties, and the resulting majority tournament is exactly \(T_\mu=T\).
For \(m=1\), use the unique ranking with mass \(1\); the same tournament-preservation statement holds.
For \(m\geq 2\), minimality of \(N\) gives
\(N<2m(m-1)\).
Hence the number of distinct supported rankings satisfies
\(\tau\leq N<2m(m-1)\).
After labeling candidates by integers from \(1\) through \(m\), each ranking requires \(O(m\log(m+1))\) bits. Each mass requires \(O(\log(m+1))\) bits, because its numerator and denominator are at most \(N=O(m^2)\). Consequently, the produced instance has total bit length
\(L=O(\tau m\log(m+1))=O(m^3\log(m+1))\).
Constructing the rankings and sorting them to merge duplicates takes
\(O(m^3\log^2(m+1))\) bit operations using comparison sorting. Thus the reduction has polynomial running time and polynomial output length.
For completeness, an arbitrary input society can also be converted to its explicit majority tournament in polynomial time in \(m,\tau,L\). Write its masses as \(p_i/q_i\) and form the common denominator
\(Q=\prod_{i=1}^{\tau}q_i\).
Its bit length is \(O(L)\). For each pair, sum the scaled integer weights \(p_i(Q/q_i)\) of rankings placing the first candidate above the second, and compare twice that sum with \(Q\). Elementary binary arithmetic gives the conservative bound
\(O(m^2\tau L^2)\) bit operations.
This computation uses the listed support directly.
Map the explicit-tournament instance \((T,c^\star)\) to the constructed society with the same designated candidate.
We proved that \(T_\mu=T\). Therefore every dominator set \(D_X(y)\) agrees in the two instances. Induction on \(|X|\), starting with the empty set, then shows that their recursively defined TEQ sets agree for every subset \(X\): the smaller dominator-set solutions agree, hence the relations \(R_X\) agree, and so do their selected source components.
In particular,
\(c^\star\in\mathrm{TEQ}(T)\iff c^\star\in\mathrm{TEQ}(T_\mu)\).
This is a polynomial-time many-one reduction from the known \(\mathrm{NP}\)-hard membership problem. It proves the requested hardness for the rational-mass support representation. It does not assert membership in \(\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The reduction establishes \(\mathrm{NP}\)-hardness for the specified support representation, even with dyadic masses. No major or minor mathematical issues were found.
Theorem 2 states hardness of deciding membership for a designated alternative in an explicit tournament. Definition 2 uses the same recursive dominator-set relation. The paper defines the selected set as the maximal elements of the asymmetric part of the reflexive transitive closure, which agrees with the task’s condition \(\forall y,\ yR_X^*x\Rightarrow xR_X^*y\). This selects every source strongly connected component, including isolated vertices. No uniqueness assumption is needed. [Brandt, Fischer, and Harrenstein, Definition 2 and Theorem 2](https://arxiv.org/pdf/0711.2961).
Both rankings place \(a\) above \(b\), contributing margin \(2\). For a pair involving one of \(a,b\) and a remaining candidate, the two rankings give opposite comparisons. For two remaining candidates, their relative order is reversed. These cases exhaust all other pairs. Thus the gadget contributes zero margin elsewhere, and superposing the gadgets preserves margin \(2\) on every tournament edge.
For \(m\geq2\), \(n_0=m(m-1)\) is positive and even. The chosen power of two \(N\) is also even, so the padding count is a nonnegative integer. A ranking and its reverse cancel on every comparison. Merging duplicates therefore preserves every margin while producing distinct rankings with positive dyadic masses summing to \(1\).
The equations \(A+B=N\) and \(A-B=2\) give
\(A/N=1/2+1/N>1/2\).
This holds for every directed edge of the original tournament. Consequently, the constructed society satisfies the no-ties promise and has exactly the original majority tournament. For \(m=2\), the empty remaining-candidate list causes no problem: the two gadget rankings coincide and are correctly merged. The separate \(m=1\) construction is valid.
Minimality of \(N\) gives \(N<2m(m-1)\), hence \(\tau=O(m^2)\). Each ranking uses \(O(m\log(m+1))\) bits, and each mass uses \(O(\log(m+1))\) bits. The resulting bound \(L=O(m^3\log(m+1))\) follows. Comparison sorting uses \(O(m^2\log(m+1))\) comparisons, each costing at most \(O(m\log(m+1))\) bit operations, consistent with the stated construction bound \(O(m^3\log^2(m+1))\).
The product denominator \(Q\) has bit length bounded by the sum of the input denominator lengths, hence \(O(L)\). Scaling, summing, and comparing the weights can use elementary arithmetic within the conservative bound \(O(m^2\tau L^2)\). Pairwise ranking comparisons can also be obtained within this bound. This step computes the tournament, not TEQ, so it does not contradict the hardness conclusion.
Equality of the tournaments gives equality of every dominator set. The stated induction is well founded because \(y\notin D_X(y)\), so each recursive call concerns a strictly smaller set. The empty-set base case agrees, and equality of the recursive relations gives equality of TEQ on every subset. The designated candidate is preserved, yielding the required membership equivalence and polynomial-time many-one reduction.
Repair feedback: None required. The conclusion properly establishes hardness without asserting membership in \(\mathrm{NP}\), and it excludes a polynomial-time algorithm only conditional on \(\mathrm{P}\neq\mathrm{NP}\).
⟨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.