Answer: Polynomial-time solvable; whenever unanimity is reachable, its earliest round satisfies \(0\leq t\leq\tau-1\), and this bound is sharp.
Proposition 4 — class: other
Given a finite alternative set \(W\), supported types \(K\) with positive rational masses \(\mu_k\) summing to \(1\), an initial total-preorder preference \(\pi_k\) for each type, and a reliability order over types inducing a most-reliable successor \(f(k)\), decide whether some finite round makes all positive-mass types share the same preference, and return the earliest such round if it exists. At each round, type \(k\) adopts the current preference of type \(f(k)\).
Let \(W\) be a finite alternative set with \(m=|W|\geq 1\). A society is given by its support: a list \(K\) of \(\tau\geq 2\) types with positive binary rational masses \(\mu_k\), where \(\sum_{k\in K}\mu_k=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type \(k\) has an initial total preorder \(\pi_k\) on \(W\), given as ordered indifference classes, and its own fixed total reliability order \(\preceq_k\) on all of \(K\), including itself. Let \(f(k)\) be the unique greatest type in this order; self-selection is allowed.
Set \(\pi_k^{(0)}=\pi_k\). At each integer round \(t\geq 0\), all types update simultaneously by \(\pi_k^{(t+1)}=\pi_{f(k)}^{(t)}\); masses and reliability orders remain fixed. Unanimity means equality of the entire preference relations for every supported type. Distinct types may initially have identical preferences.
The computational problem is to decide whether unanimity occurs and, if so, return the least such \(t\), including \(t=0\), encoded in binary. Let \(L\) be the total binary input length.
Can unanimity reachability and its earliest round be computed in time polynomial in \(m,\tau,L\), or is deciding unanimity reachability NP-hard?
For finite agent lists with pairwise distinct initial preferences, unanimity under simultaneous copying is characterized by synchronous reachability of a common agent in the most-reliable-successor relation; this characterization supplies a modal decision procedure, without a stated complexity bound. [Ghosh–Velázquez-Quesada](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p1491.pdf)
No result settling the exact rational-mass problem above was located in the literature search.
Both unanimity reachability and the earliest round are computable in time polynomial in \(m,\tau,L\). More precisely, if unanimity ever occurs, its earliest round satisfies \(0\leq t\leq\tau-1\).
The proof allows identical initial preferences, arbitrary positive rational masses, and self-selection. For \(m=1\), all initial preferences coincide and the answer is immediately \(t=0\); the argument below covers general \(m\).
Write \(f^0\) for the identity on \(K\), and \(f^{t+1}=f\circ f^t\). We first establish that, for every \(k\in K\) and \(t\geq0\),
\(\displaystyle \pi_k^{(t)}=\pi_{f^t(k)}.\)
At \(t=0\), this is the definition of the initial state. If it holds at round \(t\), the simultaneous update gives
\(\displaystyle \pi_k^{(t+1)}=\pi_{f(k)}^{(t)}=\pi_{f^t(f(k))}=\pi_{f^{t+1}(k)}.\)
Thus the claim follows by induction.
Define the set of initial preference sources at round \(t\) by
\(\displaystyle S_t=f^t(K)=\{f^t(k):k\in K\}.\)
Consequently, unanimity at round \(t\) is equivalent to
\(\displaystyle \pi_u=\pi_v\quad\text{for every }u,v\in S_t.\)
Indeed, every current preference comes from a member of \(S_t\), and every member of \(S_t\) supplies some type’s current preference. This equivalence concerns equality of preference relations, so it remains valid when distinct types have identical initial preferences.
We have \(S_0=K\) and \(S_{t+1}=f(S_t)\). These sets are nonempty because \(K\) is nonempty and \(f\) is defined everywhere.
They are also nested:
\(\displaystyle S_{t+1}\subseteq S_t\quad\text{for every }t\geq0.\)
For the base case, \(f(K)\subseteq K\). If \(S_t\subseteq S_{t-1}\), taking images under \(f\) gives \(S_{t+1}\subseteq S_t\).
Furthermore, an equality \(S_{t+1}=S_t\) forces permanent stabilization: applying \(f\) gives \(S_{t+2}=S_{t+1}\), and induction gives all subsequent equalities.
Starting with \(\tau\) elements, a nested sequence of nonempty sets can undergo at most \(\tau-1\) strict decreases. Therefore,
\(\displaystyle S_{\tau-1}=S_\tau=S_{\tau+1}=\cdots.\)
To justify the endpoint explicitly: if equality occurs before round \(\tau-1\), stabilization has already occurred; otherwise the first \(\tau-1\) decreases are strict, leaving a singleton, whose next nonempty subset must equal itself.
Since unanimity depends only on whether the initial preferences on \(S_t\) coincide, its truth value is constant after round \(\tau-1\). Hence unanimity is reachable if and only if it occurs in one of rounds \(0,\ldots,\tau-1\).
Also, once unanimity occurs, it persists: subsequent source sets are subsets of the unanimous source set.
Fix an indexing of \(W\). Encode each initial preorder by its rank vector: an alternative receives the index of its indifference class in the given order. Each vector has \(m\) entries.
Two such vectors coincide exactly when their preference relations coincide. One direction follows because class ranks determine every comparison. Conversely, the relation determines its indifference classes and their order, hence determines the rank vector.
The algorithm is:
At the start of iteration \(t\), the maintained set is \(S_t\), by induction on the update \(S\leftarrow f(S)\). Section 1 therefore proves that each comparison correctly tests unanimity at that round. Testing rounds in increasing order returns the least round. Section 2 proves that rejection after the final test rules out every later round.
There are \(\tau\) iterations. Each examines at most \(\tau\) vectors of length \(m\) and computes at most \(\tau\) successors. Thus, after parsing, the algorithm uses \(O(\tau^2m+\tau^2)\) elementary operations. Ranks and type indices require only \(O(\log(m+\tau+1))\) bits, so these operations have polynomial bit cost. Parsing the explicitly supplied preferences, reliability orders, and rational masses also takes polynomial time in \(L\).
The masses do not enter either the update rule or the equality test. Their magnitudes and denominators therefore introduce no additional dynamics or numerical computation. The returned round requires only \(O(\log\tau)\) bits.
Let \(C\subseteq K\) be the set of vertices lying on directed cycles of the graph with edges \(k\to f(k)\). Then
\(\displaystyle S_{\tau-1}=C.\)
For the first inclusion, a cyclic vertex has a predecessor on its cycle under every iterate \(f^t\); hence \(C\subseteq S_t\) for every \(t\).
For the reverse inclusion, put \(S=S_{\tau-1}\). Stabilization gives \(f(S)=S\), so the restriction of \(f\) to the finite set \(S\) is surjective and therefore bijective. Every vertex of a finite permutation lies on a cycle. Thus \(S\subseteq C\).
It follows that unanimity is reachable exactly when all cyclic vertices, across all cycles, have the same initial preference relation.
When initial preferences are pairwise distinct, this condition says that \(C\) is a singleton, necessarily a self-loop. This recovers the common-source condition in [Ghosh–Velázquez-Quesada, Proposition 3](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p1491.pdf). With repeated preferences, several cycles may exist and still permit unanimity.
For any \(\tau\geq2\) and \(m\geq2\), choose distinct total preorders \(p,q\). Let \(K=\{1,\ldots,\tau\}\), with
\(\displaystyle f(i)=i+1\text{ for }i<\tau,\qquad f(\tau)=\tau.\)
Give types \(1,\ldots,\tau-1\) initial preference \(q\), and type \(\tau\) initial preference \(p\). These successors can be realized by total reliability orders placing the designated successor greatest; choose any admissible positive masses.
For every \(t<\tau-1\), type \(1\) has preference \(q\), while type \(\tau\) has preference \(p\). Unanimity therefore fails. At round \(\tau-1\), every type copies the initial preference of type \(\tau\), so unanimity occurs.
Thus the bound \(\tau-1\) cannot be improved in general. The decision problem belongs to \(\mathsf{P}\); NP-hardness under polynomial-time reductions would consequently imply \(\mathsf{P}=\mathsf{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. Both unanimity reachability and the earliest round are computable in polynomial time, and the bound \(t\leq\tau-1\) is justified and sharp. No major or minor mathematical issues were found.
The identity
\[
\pi_k^{(t)}=\pi_{f^t(k)}
\]
is proved correctly by induction. The induction step uses simultaneous updating and the identity \(f^t\circ f=f^{t+1}\), which holds for iterates of the same function.
The equivalence between unanimity at round \(t\) and equality of all initial preferences indexed by \(S_t=f^t(K)\) is exact. Each current preference has a source in \(S_t\), and each source in \(S_t\) is attained by some supported type. Injectivity of the assignment of initial preferences is unnecessary.
The proof that \(S_{t+1}\subseteq S_t\) is correct: the base inclusion is \(f(K)\subseteq K\), and taking images preserves inclusion.
The permanent-stabilization claim is also correct. Since \(S_{t+1}=f(S_t)\), equality at consecutive rounds implies equality at the next pair, and induction applies.
Nonemptiness follows because \(f\) is a total function on a nonempty finite set. Consequently, there can be at most \(\tau-1\) strict decreases. The write-up explicitly handles the endpoint: if all first \(\tau-1\) decreases are strict, the remaining set is a singleton and cannot decrease further while remaining nonempty.
Thus \(S_{\tau-1}\) is indeed the permanent source set. Although individual types’ preferences can continue changing, the unanimity predicate depends only on the initial preferences represented in this set. The asserted constancy of that predicate after round \(\tau-1\) follows.
Persistence of unanimity follows correctly from nestedness.
Rank vectors give a canonical representation of the supplied ordered indifference classes, using the same indexing of alternatives and class positions for every type.
Equality of vectors implies equality of all comparisons. Conversely, equality of preference relations determines the same indifference classes in the same order, hence the same vector. This correctly tests equality of entire total preorders, including ties.
The maintained-set invariant \(S=S_t\) is valid initially and preserved by the update \(S\leftarrow f(S)\).
Each iteration therefore tests exactly the required unanimity condition. Testing rounds in increasing order returns the earliest round, including round \(0\). Rejecting after round \(\tau-1\) is justified by permanent stabilization.
All maintained source sets are nonempty, so the comparison never requires a convention for an empty collection.
The operation bound \(O(\tau^2m+\tau^2)\) after parsing is justified. There are \(\tau\) iterations, each comparing at most \(\tau\) vectors of length \(m\) and processing at most \(\tau\) successors. Duplicate removal can be implemented within the stated bound using the fixed type indexing.
Ranks and type indices have polynomial bit length. Reading and indexing the explicitly supplied data takes polynomial time in \(L\). The round counter and returned answer require \(O(\log\tau)\) bits.
Ignoring the masses is legitimate: neither the update rule nor the specified unanimity condition depends on their values. Positivity ensures that every listed type is supported. The algorithm is being evaluated on the valid inputs specified by the task; additional numerical validation is not required for correctness.
Both inclusions in \(S_{\tau-1}=C\) are valid:
The resulting criterion—equality of initial preferences on all cyclic vertices—therefore follows.
Under pairwise distinct initial preferences, that criterion forces exactly one cyclic vertex, necessarily a self-loop. The comparison with [Ghosh–Velázquez-Quesada, Proposition 3](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p1491.pdf) is accurate: that proposition concerns pairwise distinct initial preferences and synchronous arrival at a common preference source under the same copying dynamics. The present proof establishes its result independently of the citation.
The chain construction is valid. For every \(t<\tau-1\), the source of type \(1\) is a type carrying \(q\), while the terminal type retains \(p\). At round \(\tau-1\), every source is the terminal type.
The designated successors are realizable by total reliability orders, and admissible positive rational masses exist. Distinct preorders \(p,q\) exist whenever \(m\geq2\).
For \(m=1\), every total preorder is identical, giving earliest round \(0\), as stated. Self-selection and initially unanimous societies are also covered.
The final complexity statement is appropriately qualified: membership in \(\mathsf{P}\) implies that NP-hardness under polynomial-time reductions would entail \(\mathsf{P}=\mathsf{NP}\).
No repair or additional clarification is needed.
⟨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.