Termination of Binary Trust-Gossip Dynamics: A Constructive No-Limit-Cycles Theorem

Abstract

In the binary trust-gossip dynamics, $n$ agents each hold a directed binary opinion, trust or distrust, of every other agent, and a gossip step lets one agent copy another agent's opinion of a third whenever the copier trusts the source. We prove that under any fair schedule of such steps, every trajectory reaches an absorbing state in finitely many steps, one in which no gossip step changes any opinion; in particular, there are no limit cycles. The proof is constructive and rests on a single descent measure: the number of ordered pairs of distinct agents linked by a chain of trust. Trust-adding gossip leaves this count unchanged and trust-removing gossip can only lower it, so it never rises, and it is zero only at the all-distrust state. From any non-absorbing state we exhibit a finite run of steps that reaches an absorbing state or strictly lowers the count; since the count is a non-negative integer at most $n(n-1)$, the process halts at an absorbing state.

Disclosure

“dgements Formatted and illustrated using Overleaf. No competing interests to declare. This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors. Use of AI tools: Anthropic Claude Fable 5, Opus 4.8 and Sonnet 5 were used for assistance with drafting sections, conducting literature searches, and drawing figures. All mathematical content was verified independently by the author. References [1] N. Boichuk, Absorbing”

PDF page 17

Classification

Drafting limited passages

Multiplier

5

Verified

2026-08-24T00:34:05.733Z

Structural counts