Finite-time consensus in a compromise process

Abstract

A compromise process describes the evolution of opinions through binary interactions. Opinions are real numbers, and at each step, two randomly selected agents reach a compromise by averaging their pre-interaction opinions. We prove that if the number $N$ of agents is a power of two, then consensus emerges after a finite number of compromise events with probability one; otherwise, consensus cannot be reached in a finite number of steps, provided the initial opinions are in a general position. The number of steps required to reach consensus is random for $N=2^k$ with $k\ge 2$. We prove that the smallest number of steps is $k\cdot 2^{k-1}$ when the initial opinions are in a general position. For $N=4$, we determine the distribution of the number of steps. In particular, we show that it has a purely exponential tail and compute all cumulants.

11 pages, 3 figures; v2: new section and references added