Answer: Polynomial-time solvable in \(O(\tau L^2+\tau mL)\) time.
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm~\ref{algorithm:RAAA} satisfies the Conservative Reality-aware Condorcet criterion. Furthermore, the modifications described in Remark~\ref{remark:agendas} correspond to algorithms which satisfy the further Reality-aware Condorcet criteria discussed in Section~\ref{section:condorcet}.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite alternative set \(S\), a current Reality \(R\in S\), an agenda order, and a society represented by \(\tau\) strict rankings \(t\) with positive rational masses \(\mu_t\) summing to \(1\), with no ties in the majority comparisons used, compute the winner returned by Algorithm 1: form \(S_R=\{s\in S\setminus\{R\}:\sum_{t:s\succ_t R}\mu_t>1/2\}\), run the agenda on \(S_R\) starting with \(R\), and return the final alternative if it wins every required comparison, or \(R\) otherwise.
Let \(S\) be a finite alternative set with \(m=|S|\geq 1\), a distinguished current Reality \(R\in S\), and a supplied linear agenda order on \(S\).
A society is given by its support: the list of the \(\tau\) strict rankings of \(S\) 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; state running times in \(m,\tau,L\).
For distinct alternatives, write \(a\triangleright b\) when \(\sum_{t:a\succ_t b}\mu_t>1/2\). Promise that every majority comparison used below is untied.
Form \(S_R=\{s\in S\setminus\{R\}:s\triangleright R\}\). If this set is empty, return \(R\). Otherwise initialize an incumbent to \(R\), visit each member of \(S_R\) in the restricted agenda order, and replace the incumbent by the majority winner of its comparison with the visited alternative.
Let \(c\) be the final incumbent. Compare \(c\) with every other member of \(S_R\) that it has not already faced during the agenda; return \(c\) if it wins every extra comparison, and return the original \(R\) otherwise. The rankings and original Reality remain fixed throughout.
Is computing the returned alternative solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite electorates, this procedure satisfies the conservative Reality-aware Condorcet criterion: it elects the Condorcet winner of \(S_R\) whenever one exists, and elects \(R\) otherwise.
Computing the returned alternative is polynomial-time solvable. With exact arithmetic, a running-time bound is \(O(\tau L^2+\tau mL)\). The stated conservative Reality-aware Condorcet criterion also holds for the supplied rational masses.
Write each mass as \(\mu_t=p_t/q_t\), where \(p_t,q_t\) are positive integers encoded in binary. Define \(Q=\prod_{t=1}^{\tau}q_t\) and \(W_t=p_t(Q/q_t)\). Then \(\mu_t=W_t/Q\), and normalization gives \(\sum_{t=1}^{\tau}W_t=Q\).
The bit length of \(Q\) is \(O(L)\), because the sum of the denominators’ bit lengths is bounded by the input length. Each \(W_t\) also has \(O(L)\) bits: positivity and normalization imply \(W_t\leq Q\). Computing \(Q\) and all \(W_t\) takes \(O(\tau L^2)\) bit operations using schoolbook integer arithmetic.
For each ranking, construct a position table \(\operatorname{pos}_t(a)\). Thus \(a\succ_t b\) exactly when \(\operatorname{pos}_t(a)<\operatorname{pos}_t(b)\). These tables take \(O(\tau m\log(m+1))\) bit operations to construct.
For distinct \(a,b\), compute \(A(a,b)=\sum_{t:\operatorname{pos}_t(a)<\operatorname{pos}_t(b)}W_t\). Then \(a\triangleright b\) exactly when \(2A(a,b)>Q\). All partial sums are at most \(Q\), so a comparison takes \(O(\tau L)\) bit operations with indexed position tables. The untied-comparison promise makes each required comparison decisive.
Let \(k=|S_R|\).
Consequently, there are at most \(3(m-1)\) majority comparisons. Record the agenda’s compared pairs; after finding its final incumbent \(c\), scan this record to identify the alternatives already faced by \(c\). The record and scan require \(O(m)\) entries and operations.
Combining preprocessing and comparison costs gives \(O(\tau L^2+\tau mL)\), since \(\log(m+1)=O(L)\) for the explicit input representation. This is polynomial in \(m,\tau,L\).
A Condorcet winner of \(S_R\) is an alternative \(w\in S_R\) satisfying \(w\triangleright s\) for every \(s\in S_R\setminus\{w\}\).
If \(S_R\) is empty, the procedure returns \(R\) as specified. Assume henceforth that \(S_R\) is nonempty.
Each eligible alternative is visited exactly once. If an incumbent loses, it is replaced and cannot become incumbent again: its visit has already occurred.
Therefore, the final incumbent \(c\) cannot have lost an agenda comparison. Moreover, \(c\in S_R\), because the first visited alternative defeats \(R\), and every subsequent incumbent belongs to \(S_R\).
If the final verification accepts \(c\), then \(c\) defeats every other member of \(S_R\): it defeated those it faced during the agenda, and the verification checks all remaining members. Thus every returned alternative other than \(R\) is a Condorcet winner of \(S_R\).
Suppose \(w\) is a Condorcet winner of \(S_R\). Immediately before \(w\)'s visit, the incumbent is either \(R\) or an earlier visited member of \(S_R\).
Because \(w\in S_R\), it defeats \(R\). Because it is a Condorcet winner of \(S_R\), it defeats every other possible incumbent. Hence \(w\) becomes incumbent when visited. It defeats every subsequently visited alternative, so it remains the final incumbent. It also wins every extra comparison and is returned.
These two statements prove that the procedure returns the Condorcet winner of \(S_R\) whenever one exists, and returns \(R\) otherwise. Uniqueness follows because two distinct Condorcet winners would each have to defeat the other, which strict majority comparisons cannot permit.
Thus the problem belongs to \(\mathrm{P}\); NP-hardness under polynomial-time reductions would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output resolves the computational question: the procedure is polynomial-time computable in the supplied representation. Its arithmetic and comparison bounds are valid, and its Condorcet argument is sound. There is one minor imprecision concerning the initial incumbent \(R\).
The common-denominator construction is valid even when the supplied fractions are not reduced. Every \(q_t\) divides \(Q\), so \(W_t=p_t(Q/q_t)\) is an integer, and normalization gives
\[
\sum_{t=1}^{\tau}W_t=Q.
\]
The claimed bit bounds hold:
The position tables correctly represent the supplied strict rankings. Their stated construction cost assumes indexed alternative identifiers, consistent with the indexed tables explicitly used in the output.
For each pair, the identity
\[
a\triangleright b\quad\Longleftrightarrow\quad 2A(a,b)>Q
\]
is correct. Positivity ensures all partial sums are at most \(Q\); doubling adds at most one bit. The stated \(O(\tau L)\) cost per majority comparison is therefore valid with the indexed position tables. Exact arithmetic avoids any rounding issue.
All three counts are correct:
For \(k>0\), their sum is at most \(3(m-1)\). For \(k=0\), only eligibility testing occurs, which also satisfies that bound. In particular, when \(m=1\), there are no majority comparisons and the procedure returns \(R\).
Recording compared pairs and scanning them after determining \(c\) suffices to identify its prior opponents. The record has \(O(m)\) entries. The bit costs of identifiers and bookkeeping are absorbed by the stated total bound.
Thus \(O(\tau L^2+\tau mL)\) is a valid polynomial upper bound for the explicit input representation.
The output correctly establishes that the final incumbent belongs to \(S_R\): the first eligible alternative defeats \(R\), and every subsequent replacement comes from \(S_R\).
For eligible alternatives, the non-reentry argument is valid. Each is visited once, and an eligible incumbent that loses cannot subsequently return. Consequently, the final incumbent has won every agenda comparison involving it.
The extra comparisons cover precisely its remaining opponents in \(S_R\). Acceptance therefore implies that the returned alternative defeats every other member of \(S_R\).
Conversely, the argument concerning a Condorcet winner \(w\) checks every possible incumbent at its visit: \(R\) or an earlier eligible alternative. The supplied definitions ensure \(w\) defeats either. Its later agenda comparisons and extra comparisons also succeed. This includes the singleton case, where the within-set Condorcet condition is vacuous.
The uniqueness assertion is correct: opposite strict majority victories cannot both occur. No external theorem is invoked without justification.
Minor — scope of the non-reentry explanation. The sentence “If an incumbent loses, it is replaced and cannot become incumbent again: its visit has already occurred” includes \(R\), although \(R\) has no agenda visit and loses the first comparison whenever \(S_R\) is nonempty.
The surrounding argument already handles \(R\), so this does not undermine the conclusion. The minimum clarification is to restrict the “its visit has already occurred” explanation to incumbents in \(S_R\), and state separately that \(R\) is never visited.
The final statement about NP-hardness is appropriately 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.