2.1 State space

Let $\mathcal{X}=\{1,\ldots ,m\}$ be a finite set of $m \gt 1$ alternatives.Footnote ¹ Let $\Omega (m)$ denote the finite set of all weak orders (total preorders, i.e., complete, transitive and reflexive relations) on $\mathcal{X}$ , and write $\Omega \;:\!=\;\Omega (m)$ . In the terminology of social choice theory, individual preferences are typically represented as complete and transitive orderings of alternatives (weak orders), a standard convention in the literature (Sen, Reference Sen1970). $\Omega$ ’s cardinality is the ordered Bell (or Fubini) number

(1) \begin{equation} |\Omega (m)| \,=\, F(m)\,=\,\sum _{k=1}^{m} k!\,S(m,k), \end{equation}

where $S(m,k)$ are Stirling numbers of the second kind (Stanley, Reference Stanley2012). In particular, $|\Omega (3)|=F(3)=13$ and $|\Omega (4)|=F(4)=75$ . We partially order $\Omega (m)$ by refinement: $\omega \leq \omega ^\prime$ if $\omega ^\prime$ is obtained from $\omega $ by merging consecutive indifference classes. This poset is not a lattice, since, e.g., two opposite strict orders have no common refinement in $\Omega (m)$ ; adjoining a least element turns it into the face lattice of the permutohedron. Figure 1 shows the Hasse (cover) graphs of the weak-order refinement posets for $m=3$ and $m=4$ ; in this manuscript we denote this Hasse (cover) graph by $H = (\Omega ,{E_H})$ , a connected graph whose edges correspond to elementary changes between adjacent weak orders (cover relations in the poset). We use $d_H$ to denote the shortest-path distance on $H$ (with unit edge lengths).

Figure 1.

Hasse diagrams (cover graphs) of the weak-order refinement posets $\Omega (3)$ and $\Omega (4)$ . Each weak order is written as an ordered partition, best class first; e.g. (0,1)2 means $0 \sim 1 \succ 2$ . Edges join weak orders that differ by merging two adjacent indifference classes. $|\Omega (3)| = F(3)=13$ and $|\Omega (4)| = F(4)=75$ , where $F(m)$ is the ordered Bell (Fubini) number.

2.2 Borda scores and local profile aggregation

A Borda score map $b\;:\;\Omega \to \mathbb{R}^m$ assigns each weak order a score vector. We use the averaged Borda convention for ties: if an indifference class occupies consecutive rank positions, each alternative receives the average of the corresponding strict Borda scores (Borda, Reference de Borda1784; Saari, Reference Saari1995; Terzopoulou and Endriss, Reference Terzopoulou and Endriss2021). Given a score vector $s\in \mathbb{R}^m$ , let $T(s)\in \Omega$ be the weak order obtained by sorting alternatives by decreasing score, with ties in $s$ mapped to indifference classes. Thus $T$ is constant on polyhedral cones and discontinuous across tie hyperplanes.

A profile is an assignment $\sigma =(\sigma _1,\ldots ,\sigma _n)\in \Omega ^{{V}}$ of a weak order to each node. Given a profile $\sigma$ and a weight matrix $W$ (to be defined in Section 2.3), node $i$ forms the aggregated Borda score

(2) \begin{equation} s_i(\sigma )=\sum _{j\in {V}} w_{ij}\, b(\sigma _j)\in \mathbb{R}^m, \end{equation}

and sets its (deterministic) Borda target to

(3) \begin{equation} \tau _i(\sigma )=T(s_i(\sigma ))\in \Omega . \end{equation}

2.3 Social graph and weights

Let $G=({V},{E})$ be a finite directed graph with node set ${V}=\{1,\ldots ,n\}$ . Each node $i\in {V}$ carries a preference state $\sigma _i\in \Omega$ , so the nodes of the social graph $G$ are in bijection with the nodes of the preference state space $\Omega ^{{V}}$ : the social network specifies who influences whom, while the preference space $\Omega$ specifies what each node holds. A nonnegative weight matrix $W=(w_{ij})$ is compatible with $G$ if $w_{ij}\gt 0$ only when $(i,j)\in {E}$ . Throughout we assume row-stochasticity:

(4) \begin{equation} \sum _{j\in {V}} w_{ij}=1,\qquad i\in {V}, \end{equation}

so each node forms a random-walk-type convex combination of its in-neighbors’ Borda scores. The undirected/unweighted case is recovered by taking $G$ undirected and setting $W=D^{-1}A$ , the random-walk matrix of $G$ .

In a directed graph, influence flows along incoming edges. For each node $i$ , its in-neighborhood is

\begin{equation*} N_i^- \;:\!=\; \{\, j\in V \;:\; w_{ij} \gt 0 \}, \end{equation*}

so the local aggregation equation (2) uses only the states of in-neighbors: $s_i(\sigma ) = \sum _{j\in N_i^-} w_{ij}\, b(\sigma _j)$ .

2.4 Persistent nodes

We study a discrete-time dynamical system in which each node $i\in V$ holds a preference state $\sigma _i(t)\in \Omega$ at time $t\in \{0,1,2,\ldots \}$ and updates it at each step according to an interaction rule depending on the states of its in-neighbors in $G$ .

Before specifying the update rules, we introduce a structural partition of the node set $V$ that is fixed throughout the dynamics: some nodes are persistent (their states are externally fixed for all time) and the remaining nodes are nonpersistent (they update according to the interaction rule).

Definition 2.1 (Persistent (boundary) nodes). Fix a set $P\subseteq V$ and an assignment $\bar \sigma _P=(\bar \sigma _p)_{p\in P}\in \Omega (m)^P$ . Nodes in $P$ are persistent (or boundary) if their states are kept constant and pinned for all times:

\begin{equation*} \sigma _p(t)=\bar \sigma _p, \,{ for\, all \,}p\in P{\, and\, all\, }t\ge 0. \end{equation*}

The remaining nodes $U\;:\!=\;V\setminus P$ are nonpersistent (or free) and evolve by the update rule.

The partition $V=P\sqcup U$ is a structural property of the model, fixed before any dynamics are specified. When $P=\varnothing$ all nodes are free; when $P\neq \varnothing$ the persistent nodes act as exogenous anchors representing, for example, stubborn actors, institutional positions, or media sources.

2.5 Update interaction rules

The most natural update rule is for each nonpersistent node to jump directly to its local Borda target. This defines the unbounded (or direct-jump) step and serves as the natural benchmark against which the bounded step is compared.

Definition 2.2 (Unbounded step/direct-jump map). For a nonpersistent node $i\in U$ , given its current state $\alpha \in \Omega$ and its local Borda target $\beta =\tau _i(\sigma )\in \Omega$ , define

\begin{equation*} \textsf {Jump}(\alpha ,\beta ) \;\;:\!=\;\; \beta . \end{equation*}

That is, the nonpersistent node moves directly to its local Borda target in a single step, regardless of the distance $d_H(\alpha ,\beta )$ .

In many social, political, and institutional settings, such unconstrained jumps are implausible: agents revise their preferences incrementally, reflecting informational, cognitive, or institutional constraints. This motivates restricting each update to a single elementary move in $H$ .

The bounded-step rule admits a natural interpretation that is both behavioral and technical. From a behavioral perspective, it models incremental preference revision: rather than instantaneously adopting a target ranking, agents adjust their preferences through elementary changes in the space of orderings, consistent with classical treatments of preference geometry (Kemeny and Snell, Reference Kemeny and Snell1962; Saari, Reference Saari1995) and models of bounded rationality (Simon, Reference Simon1957). From a technical perspective, boundedness restricts the admissible transitions in $H$ , ensuring that updates proceed through local moves. This locality aligns with standard models of iterative opinion dynamics on networks (DeGroot, Reference DeGroot1974; Friedkin and Johnsen, Reference Friedkin and Johnsen1990). The role of the bounded-step constraint relative to the unbounded benchmark is examined throughout the paper, beginning in Section 3.1.

2.6 Update variants

Each step rule ( $\textsf {Jump}$ or $\textsf {Step}$ ) combines with synchronous or asynchronous scheduling, yielding four variants. The two bounded variants are the primary objects of study; the two unbounded variants serve as a benchmark for comparison.

Definition 2.4 (Variant S: Synchronous bounded Borda dynamics). At each time $t$ , every nonpersistent node $i\in U$ updates simultaneously using $\textsf {Step}$ :

\begin{equation*} \sigma _i(t+1)=\textsf {Step}(\sigma _i(t),\,\tau _i(\sigma (t))), \qquad \sigma _p(t+1)=\sigma _p(t)\,{ for\, }p\in P. \end{equation*}

We denote the induced map on $\Omega ^U$ by $F_P$ .

Definition 2.5 (Variant A: Asynchronous bounded Borda dynamics). Fix an update schedule that selects a single nonpersistent node $I_t\in U$ at each time $t$ (e.g., uniformly at random). Only that node updates using $\textsf {Step}$ :

\begin{equation*} \sigma _{I_t}(t+1)=\textsf {Step}(\sigma _{I_t}(t),\,\tau _{I_t}(\sigma (t))), \qquad \sigma _{i}(t+1)=\sigma _i(t)\ \,{for\, }i\neq I_t. \end{equation*}

Definition 2.6 (Variant S $^\infty$ : Synchronous unbounded Borda dynamics). At each time $t$ , every nonpersistent node $i\in U$ updates simultaneously using $\textsf {Jump}$ :

\begin{equation*} \sigma _i(t+1)=\textsf {Jump}(\sigma _i(t),\,\tau _i(\sigma (t))) =\tau _i(\sigma (t)), \qquad \sigma _p(t+1)=\sigma _p(t)\,{ for\, }p\in P. \end{equation*}

We denote the induced map on $\Omega ^U$ by $F_P^{\infty }$ .

Definition 2.7 (Variant A $^\infty$ : Asynchronous unbounded Borda dynamics). Fix an update schedule that selects a single nonpersistent node $I_t\in U$ at each time $t$ . Only that node updates using $\textsf {Jump}$ :

\begin{equation*} \sigma _{I_t}(t+1)=\textsf {Jump}(\sigma _{I_t}(t),\,\tau _{I_t}(\sigma (t))) =\tau _{I_t}(\sigma (t)), \qquad \sigma _{i}(t+1)=\sigma _i(t)\ {\,for \,}i\neq I_t. \end{equation*}

3.1 Eventual periodicity and fixed points

For a fixed persistent boundary condition and deterministic tie-breaking in $\textsf {Step}$ , Variant S defines a deterministic map $ F_P\;:\;\Omega ^U\to \Omega ^U.$

Proof. (a) $F_P^{\infty }$ is a deterministic map on the finite set $\Omega ^U$ , so every orbit is eventually periodic.

(b) By definition, $F_P^{\infty }(\sigma )_i = \textsf {Jump}(\sigma _i,\tau _i(\sigma )) = \tau _i(\sigma )$ . Hence $F_P^{\infty }(\sigma )=\sigma$ if and only if $\tau _i(\sigma )=\sigma _i$ for all $i\in U$ , which is the same condition as for $F_P$ (since $\textsf {Step}(\alpha ,\alpha )=\alpha$ for all $\alpha \in \Omega$ ).

(c) Under the hypotheses of Theorem4.1, the targeting condition gives $\tau _i(\sigma (t))=\sigma _{i-1}(t)$ for all $i\in C$ . Under Variant S $^\infty$ :

\begin{equation*} \sigma _i(t+1) = \textsf {Jump}\bigl (\sigma _i(t),\,\tau _i(\sigma (t))\bigr ) = \tau _i(\sigma (t)) = \sigma _{i-1}(t). \end{equation*}

By induction, $\sigma _i(t)=\omega _{(i-t)\bmod k}$ for all $i\in C$ and all $t\ge 0$ . Since the $\omega _j$ are distinct, the profile $(\sigma _i(t))_{i\in C}$ first returns to its initial value when $t\equiv 0\pmod {k}$ , so the period is exactly $k$ .

We note that the proof of Theorem4.1 under Variant S uses the condition $\textsf {Step}(\omega _r,\omega _{r-1})=\omega _{r-1}$ , which holds because adjacent states on the $H$ -cycle are at distance $1$ in $H$ . Under Variant S $^\infty$ , the same conclusion holds without this condition: $\textsf {Jump}(\omega _r,\omega _{r-1})=\omega _{r-1}$ for any $\omega _r,\omega _{r-1}\in \Omega$ , whether or not they are adjacent in $H$ . Thus Variant S $^\infty$ requires fewer hypotheses than Variant S to produce the same periodic orbit.

(d) Part (a) of Theorem5.2 gives the stated Variant S $^\infty$ orbit and its Variant S $^\infty$ -specific margin from the tie hyperplane.

Proposition 3.3 (Local Borda equilibria as fixed points). Fix persistent boundary data $(P,\bar \sigma _P)$ and consider Variant S. If a profile $\sigma \in \Omega ^{V}$ satisfies

\begin{equation*} \tau _i(\sigma )=\sigma _i, { \,for\, all\, } i\in U, \end{equation*}

then $\sigma _U$ is a fixed point of the induced map $F_P\;:\;\Omega ^U\to \Omega ^U$ .

Lemma 3.1 (Frozen targets imply finite-time stabilization). Assume that for some $t_0$ the targets become time-independent, i.e., there exist $\bar \tau _i\in \Omega$ such that for all $t\ge t_0$ and all $i\in U$ ,

\begin{equation*} \tau _i(\sigma (t))=\bar \tau _i. \end{equation*}

Then for each $i\in U$ , the distance $d_H(\sigma _i(t),\bar \tau _i)$ is nonincreasing in $t$ and reaches $0$ in at most $d_H(\sigma _i(t_0),\bar \tau _i)$ steps. In particular, if all $\bar \tau _i$ coincide with a single $\bar \omega$ , then Variant S reaches consensus $\sigma _i\equiv \bar \omega$ within at most $\mathrm{diam}(H)$ steps after $t_0$ .

3.2 Consensus fixed points

3.3 Network dependence of convergence

4.1 Oscillations on directed cycles

The next theorem shows that if the social graph contains a directed cycle with essentially permutation-like influence, then periodic orbits exist whenever the move graph $H$ contains a cycle.

Theorem 4.1 (Self-oscillations via oscillations on a directed influence cycle). Assume $P=\varnothing$ . Suppose the social graph contains a directed cycle $C=(1\to 2\to \cdots \to \ell \to 1)$ such that for every $i\in C$ ,

\begin{equation*} w_{i,i-1}\gt 0 \quad \,{(with\, i-1 \,understood\, mod\, \ell )}, \qquad w_{ij}=0 \,{\, for \,} j\neq i-1, \end{equation*}

so each node copies the unique predecessor in the cycle at the score-aggregation stage. Assume moreover that for all profiles $\sigma$ , the target at $i\in C$ satisfies $ \tau _i(\sigma )=\sigma _{i-1}.$ Let $(\omega _0,\omega _1,\ldots ,\omega _{k-1},\omega _0)$ be a simple cycle in the move graph $H$ (adjacent successive states). Assume that $k\mid \ell$ . Initialize the nodes on $C$ by

\begin{equation*} \sigma _i(0)=\omega _{i \bmod k}\qquad (i\in C), \end{equation*}

and choose arbitrary initial states off $C$ . If $\textsf {Step}(\omega _r,\omega _{r-1})=\omega _{r-1}$ for all $r$ (i.e., one bounded step reaches the predecessor on the $H$ -cycle), then under Variant S the restriction $(\sigma _i(t))_{i\in C}$ is periodic with period $k$ . In particular, with no persistent nodes the nodes on $C$ perform $k$ -oscillations; the full trajectory is eventually periodic with period divisible by $k$ , and if $V = C$ the full dynamics has a $k$ -cycle.

Proof. We prove by induction on $t$ that

\begin{equation*} \sigma _i(t)=\omega _{(i-t)\bmod k} \qquad \text{for every }i\in C. \end{equation*}

For $t=0$ , this is the prescribed initialization. If the formula holds at time $t$ , then the targeting condition gives

\begin{equation*} \tau _i(\sigma (t))=\sigma _{i-1}(t) =\omega _{(i-1-t)\bmod k} =\omega _{(i-(t+1))\bmod k}. \end{equation*}

Since successive states on the $H$ -cycle are adjacent,

\begin{equation*} \sigma _i(t+1) =\textsf {Step}(\omega _{(i-t)\bmod k}, \omega _{(i-(t+1))\bmod k}) =\omega _{(i-(t+1))\bmod k}. \end{equation*}

Thus the formula holds for all $t\ge 0$ . Since the $\omega _r$ are distinct, the restriction $(\sigma _i(t))_{i\in C}$ has period $k$ .

Remark 4.1 (Targeting condition: score-and-weight derivation). The targeting condition $\tau _i(\sigma )=\sigma _{i-1}$ in Theorem 4.1 is a consequence of the weight structure, not an independent assumption. Under the hypothesis $w_{i,i-1}\gt 0$ and $w_{ij}=0$ for $j\neq i-1$ , row-stochasticity forces $w_{i,i-1}=1$ , so the aggregated score is

\begin{equation*} s_i(\sigma ) = \sum _{j\in V} w_{ij}\,b(\sigma _j) = 1\cdot b(\sigma _{i-1}) = b(\sigma _{i-1}). \end{equation*}

Since $T\circ b=\mathrm{id}$ on $\Omega$ (the projection $T$ recovers the ordering from its own Borda score vector), we get $\tau _i(\sigma )=T(s_i(\sigma ))=T(b(\sigma _{i-1}))=\sigma _{i-1}$ for every profile $\sigma$ . The targeting condition is therefore implied by the hypotheses of Theorem 4.1 .

More generally, if $w_{i,i-1}\lt 1$ (other neighbors have positive weight), the targeting condition holds if and only if the perturbed score $s_i(\sigma )=b(\sigma _{i-1})+\delta _i(\sigma )$ , where

\begin{equation*} \delta _i(\sigma ) \;:\!=\; \sum _{j\neq i-1} w_{ij}(b(\sigma _j)-b(\sigma _{i-1})), \end{equation*}

lies in the same polyhedral cone of $T$ as $b(\sigma _{i-1})$ . A sufficient condition is

\begin{equation*} \lVert \delta _i(\sigma )\rVert _\infty \;\lt \; d_\infty (b(\sigma _{i-1}),\,\partial \mathcal{C}(\sigma _{i-1})), \end{equation*}

where $\mathcal{C}(\sigma _{i-1})$ is the polyhedral cone of $T$ containing $b(\sigma _{i-1})$ and $d_\infty$ is the $\ell ^\infty$ distance to its boundary. Since $\lVert b(\sigma _j)-b(\sigma _{i-1})\rVert _\infty \le m-1$ for all $\sigma _j,\sigma _{i-1}\in \Omega$ , a uniform sufficient condition is

\begin{equation*} (1-w_{i,i-1})(m-1) \;\lt \; d_\infty (b(\sigma _{i-1}),\,\partial \mathcal{C}(\sigma _{i-1})). \end{equation*}

This inequality is satisfied whenever the predecessor’s weight $w_{i,i-1}$ is sufficiently close to $1$ relative to the margin of $\sigma _{i-1}$ from the nearest score-tie hyperplane.

Corollary 4.1 (Existence of nontrivial oscillations for $m=3$ ). For $m=3$ , the move graph $H$ in Figure 1 contains the 12-cycle formed by the boundary of the hexagon, in which the six strict rankings alternate with the six weak orders having exactly two indifference classes,

\begin{align*} & 012 \to (0,1)2 \to 102 \to 1(0,2) \to 120 \to (1,2)0 \to 210 \to 2(0,1)\\& \to 201 \to (0,2)1 \to 021 \to 0(1,2) \to 012,\end{align*}

as well as 4-cycles through the fully indifferent weak order, e.g. $012 \to (0,1)2 \to (0,1,2) \to 0(1,2) \to 012$ . Hence Theorem 4.1 yields nontrivial oscillations of the nodes on the cycle, of period 12 (resp. 4), whenever $P = \unicode{x00D8}$ and the social graph contains a directed influence cycle of length $\ell $ divisible by 12 (resp. 4) satisfying its weight/target hypotheses.

Figure 2 displays a self oscillation as in Theorem4.1.

Figure 2.

A self-oscillation as in Theorem 4.1 for $m=3$ under Variant S with $P = \unicode{x00D8}$ . Left: the social graph (arrows $j \to i$ indicate that $j$ influences $i$ ) and the initial profile. Nodes $1 \to 2 \to 3 \to 4 \to 1$ form a directed cycle $C(\ell =4)$ with ${w_{i,i - 1}}=1$ , initialised along the 4-cycle $012 \to (0,1)2 \to (0,1,2) \to 0(1,2)$ of $H(k=4)$ . Node 5 $(w_{51} = w_{53}=1/2)$ and node 6 $(w_{62} = w_{63}=1/2)$ lie off $C$ . Right: the nodes on $C$ oscillate with period 4, as predicted. Node 5 settles at 012, while node 6 is drawn into the same period-4 cycle. Curves are slightly offset vertically for visibility.

4.2 Even-period lifting

Bipartite social topology naturally induces a two-step description of synchronous dynamics and helps explain the prevalence of even-period cycles.

Lemma 4.1 (Two-step decoupling on bipartite graphs). Suppose $G$ is bipartite with ${V}=A\sqcup B$ and influence is across the cut only, i.e., $w_{ij}=0$ whenever $i,j\in A$ or $i,j\in B$ , where $A\sqcup B$ denotes a disjoint union (so $A\cap B=\varnothing$ and $A\cup B={V}$ ). Write $\sigma =(\sigma _A,\sigma _B)$ . Then the synchronous map $F\;:\;\Omega ^{{V}}\to \Omega ^{{V}}$ can be written as

\begin{equation*} F(\sigma _A,\sigma _B)=\bigl (F_A(\sigma _B),\,F_B(\sigma _A)\bigr ) \end{equation*}

for suitable maps $F_A\;:\;\Omega ^{B}\to \Omega ^{A}$ and $F_B\;:\;\Omega ^{A}\to \Omega ^{B}$ , and hence

\begin{equation*} F^{2}(\sigma _A,\sigma _B)=\bigl (G_A(\sigma _A),\,G_B(\sigma _B)\bigr ), \qquad G_A\;:\!=\;F_A\circ F_B,\ \ G_B\;:\!=\;F_B\circ F_A. \end{equation*}

5.1 Induced dynamics on free nodes

Fix a set of persistent nodes $P\subset {V}$ and boundary states $\bar \sigma _P$ . Variant S induces a deterministic map $F_P\;:\;\Omega ^U\to \Omega ^U$ on the free nodes $U$ . When $F_P$ has no fixed point, oscillations are unavoidable.

Thus, a key task is to identify topological/weight conditions (and contrarian boundary conditions) that preclude fixed points or that explicitly construct periodic orbits.

5.2 Antipodes on the preference state space

For averaged Borda scores, antipodes satisfy the score antisymmetry

(5) \begin{equation} b(\omega ^\dagger )=(m-1)\mathbf{1} - b(\omega ), \end{equation}

so after centering scores (subtracting $(m-1)\mathbf{1}/2$ ) antipodes negate.

Lemma 5.1 (Antipodes exist on $\Omega (m)$ and are $H$ -automorphisms). Represent $\omega \in \Omega (m)$ as an ordered partition $(C_1\succ C_2\succ \cdots \succ C_k)$ of $\mathcal{X}=\{1,\ldots ,m\}$ into indifference classes. Define the antipode map $\dagger \;:\;\Omega (m)\to \Omega (m)$ by reversal,

\begin{equation*} \omega ^\dagger \;:\!=\; (C_k\succ C_{k-1}\succ \cdots \succ C_1). \end{equation*}

Then $\dagger$ is an involution, i.e., $(\omega ^\dagger )^\dagger =\omega$ , and it preserves cover relations in the refinement poset, hence induces an automorphism of its cover graph $H$ . Moreover, averaged Borda scores satisfy

\begin{equation*} b(\omega ^\dagger )=(m-1)\mathbf{1}-b(\omega ). \end{equation*}

5.3 Alternating targets

The bounded-step rule implies that if a node’s target alternates between two distinct states, the node cannot converge to a fixed point. Under a mild uniqueness assumption on shortest paths, one gets a clean two-cycle.

Lemma 5.2 (Forced local oscillation by alternating targets). Fix a node $i$ and suppose there exist $\beta \neq \gamma$ in $\Omega$ such that for all sufficiently large $t$ ,

\begin{equation*} \tau _i(\sigma (t))=\beta \,{ for \,all\, even\, }t,\qquad \tau _i(\sigma (t))=\gamma \,{ for \,all\, odd\, }t. \end{equation*}

Assume the shortest path between $\beta$ and $\gamma$ in $H$ is unique and that $\textsf {Step}$ always moves to the unique neighbor on the corresponding geodesic. Then $\sigma _i(t)$ is eventually periodic with period $2$ (it alternates between two adjacent states on that geodesic).

Lemma5.2 reduces forced oscillation questions to identifying conditions that make targets alternate, which can be achieved by bipartite forcing and (in undirected settings) by spectral parity.

5.4 Spectral parity for bipartite walks

We record a basic spectral fact for random walks on bipartite graphs and explain how it can be leveraged to force alternating score signals under contrarian camps. This is where spectral theory enters most cleanly.

5.5 Reachability and even-period forcing

In a directed weighted influence graph, persistent nodes can generate forced oscillations only in the portion of the network they can reach. Write $P\subset V$ for persistent nodes and $U=V\setminus P$ for free nodes. Let $D_W$ be the simple directed influence support digraph on $V$ with an arc $j\to i$ whenever $w_{ij}\gt 0$ . For a set $S\subseteq V$ , let $\mathrm{Reach}(S)$ denote the set of vertices reachable from $S$ in $D_W$ .

We now isolate a clean topological/spectral mechanism that produces even-period oscillations under a contrarian partition of persistent nodes into two antipodal camps. Fix an antipodal pair $(\rho ,\rho ^\dagger )\in \Omega \times \Omega$ and partition the persistent nodes into two camps

\begin{equation*} P^+\sqcup P^- = P,\qquad \sigma _p(t)\equiv \rho \ \ (p\in P^+),\qquad \sigma _p(t)\equiv \rho ^\dagger \ \ (p\in P^-). \end{equation*}

Let $C\subseteq U$ be a closed communicating class for the free-to-free kernel $W_{UU}$ : for all $i\in C$ we have $\sum _{j\in U\setminus C} w_{ij}=0$ and the induced digraph $D_W[C]$ is strongly connected. Assume moreover that $W_{CC}$ is periodic with period $2$ (imprimitive): equivalently, $C$ admits a cyclic decomposition $C=A\sqcup B$ such that $w_{ij}\gt 0$ implies $(i,j)\in A\times B$ or $(i,j)\in B\times A$ , and (under irreducibility, by Perron–Frobenius theory) such a decomposition exists if and only if $ - \rho (W_{CC}) \in \sigma (W_{CC})$ , where $\rho (W_{CC})$ is the spectral radius (Levin et al., Reference Levin, Peres and Wilmer2009; Seneta, Reference Seneta2006). Because rows of C may put weight on persistent nodes, $W_{CC}$ is in general substochastic, so $\rho (W_{CC}) \lt 1$ is possible and $ - 1$ need not be an eigenvalue; for instance, in Theorem 5.2 below, $W_{CC}$ has eigenvalues $ \pm (1 - \varepsilon )$ . In this case, the two-step kernel $W_{CC}^2$ leaves $A$ and $B$ invariant and defines aperiodic chains on each cyclic class.

The following theorem gives an explicit two-node construction of a forced period– $2$ orbit.

Theorem 5.2. Let $m=2$ , let $\rho =(a_1\succ a_2)$ , $\rho ^\dagger =(a_2\succ a_1)$ , and let $\eta =(a_1\sim a_2)$ . Let $P^+=\{p\}$ and $P^-=\{q\}$ be persistent camps, with

\begin{equation*} \bar \sigma _p=\rho ,\qquad \bar \sigma _q=\rho ^\dagger . \end{equation*}

Let $C=\{i,j\}$ be two free nodes. For some $0\lt \varepsilon \lt \tfrac 12$ , suppose

\begin{equation*} w_{ij}=1-\varepsilon ,\qquad w_{ip}=\varepsilon , \qquad w_{ji}=1-\varepsilon ,\qquad w_{jq}=\varepsilon , \end{equation*}

and that all other weights in the rows of $i$ and $j$ are zero.

Then the following hold.

1. (a) Under Variant S $^\infty$ , the initial state

   \begin{equation*} (\sigma _i(0),\sigma _j(0))=(\rho ,\rho ^\dagger ) \end{equation*}
   belongs to a period– $2$ orbit alternating with $(\rho ^\dagger ,\rho )$ . Along this Variant S $^\infty$ orbit, each free node’s aggregate score has $\ell ^\infty$ -distance at least $(1-2\varepsilon )/2$ from the tie hyperplane.

2. (b) Under Variant S, the same initial state belongs to a period– $2$ orbit alternating with $(\eta ,\eta )$ . Along this Variant S orbit, each free node’s aggregate score has $\ell ^\infty$ -distance at least

   \begin{equation*} \frac {\min \{\varepsilon ,1-2\varepsilon \}}{2}\gt 0 \end{equation*}
   from the tie hyperplane.

Proof. The Borda score vectors are

\begin{equation*} b(\rho )=(1,0),\qquad b(\rho ^\dagger )=(0,1), \qquad b(\eta )=\Big(\frac 12,\frac 12\Big). \end{equation*}

At $(\sigma _i,\sigma _j)=(\rho ,\rho ^\dagger )$ , the aggregate scores are

\begin{equation*} s_i=(\varepsilon ,1-\varepsilon ), \qquad s_j=(1-\varepsilon ,\varepsilon ). \end{equation*}

Thus $\tau _i=\rho ^\dagger$ and $\tau _j=\rho$ . Under Variant S $^\infty$ , the next state is $(\rho ^\dagger ,\rho )$ . At that state, the aggregate scores are

\begin{equation*} s_i=(1,0), \qquad s_j=(0,1), \end{equation*}

so the next state is $(\rho ,\rho ^\dagger )$ . The score gaps at the two states of this orbit are $1-2\varepsilon$ and $1$ , respectively. Therefore the aggregate scores remain at $\ell ^\infty$ -distance at least $(1-2\varepsilon )/2$ from the tie hyperplane, proving part (a).

In the weak-order cover graph for $m=2$ , the unique shortest path from $\rho$ to $\rho ^\dagger$ is

\begin{equation*} \rho \longrightarrow \eta \longrightarrow \rho ^\dagger . \end{equation*}

Consequently, under Variant S, one bounded step from $(\rho ,\rho ^\dagger )$ yields $(\eta ,\eta )$ . At $(\eta ,\eta )$ , the aggregate scores are

\begin{equation*} s_i=\bigg(\frac {1+\varepsilon }{2},\frac {1-\varepsilon }{2}\bigg), \qquad s_j=\bigg(\frac {1-\varepsilon }{2},\frac {1+\varepsilon }{2}\bigg), \end{equation*}

so $\tau _i=\rho$ and $\tau _j=\rho ^\dagger$ . One bounded step therefore returns to $(\rho ,\rho ^\dagger )$ . The score gaps at the two states of this Variant S orbit are $1-2\varepsilon$ and $\varepsilon$ , respectively. Hence the aggregate scores remain at $\ell ^\infty$ -distance at least $\min \{\varepsilon ,1-2\varepsilon \}/2$ from the tie hyperplane, proving part (b).

The two-node forcing gadget of Theorem5.2 is illustrated in Figure 3.

Figure 3.

The two-node forcing gadget of Theorem 5.2 embedded in a larger social network $(m=2,\varepsilon =0.2)$ . Left: persistent nodes $p$ and $q$ (squares) hold $\rho = a1a2$ and $\rho \unicode{x2020} = a2a1$ . The gadget $i$ , $j$ has $w_{ij} = w_{ji}=1 - \varepsilon ,w_{ip} = w_{jq} = \varepsilon $ , and initial state ( $\rho ,\rho \unicode{x2020} $ ). The other free nodes have weights $w_{ki}=0.4,w_{kl}=0.3,w_{kp}=0.3;\ w_{lj}=0.4,w_{lk}=0.3,w_{lq}=0.3;\ w_{up} = w_{uq}=0.5;\ w_{vp}=0.6,w_{vk}=0.4$ . Each free node’s initial state is shown next to it, and an arrow $s \to t$ means that s influences $t$ . Dashed edges into $p$ and $q$ have no effect, because persistent nodes are pinned. Right: (a) under Variant ${S^\infty }$ the gadget alternates between ( $\rho ,\rho \unicode{x2020} $ ) and ( $\rho \unicode{x2020} ,\rho $ ); (b) under Variant $S$ it alternates between ( $\rho ,\rho \unicode{x2020} $ ) and ( $\eta ,\eta $ ), where $\eta = (a_1,a_2)$ . In both variants k and l are drawn into the period-2 oscillation, $u$ settles at $\eta $ , and $v$ settles at $\rho $ . Curves are slightly offset vertically for visibility.