Finite-time consensus in a compromise process
Authors:
Preprint
Abstract
A compromise process describes the evolution of opinions through binary interactions. Opinions are real numbers, and in each step, two randomly selected agents reach a compromise, namely, they acquire the average of their pre-interaction opinions. We prove that if the number $N$ of agents is a power of two, the consensus emerges after a finite number of compromise events with probability one; otherwise, the consensus cannot be reached in a finite number of steps (if initial opinions are in a general position). The number of steps required to reach consensus is random for $N=2^k$ with $k\geq 2$. We prove that typically, the smallest number of steps to reach consensus is equal to $k\cdot 2^{k-1}$. For $N=4$, we determine the distribution of the number of steps, e.g., we show that it has a purely exponential tail and compute all cumulants.
Keywords
All Related Versions
This publication has 33 references indexed in Scilit:
- Explicit decay rate for the Gini index in the repeated averaging modelMathematical Methods in the Applied Sciences, 2022
- Graph Theory2017
- Dynamics of linguistic opinion formation in bounded confidence modelInformation Fusion, 2016
- Event-based broadcasting for multi-agent average consensusAutomatica, 2013
- A Pairwise Averaging Procedure with Application to Consensus Formation in the Deffuant ModelActa Applicandae Mathematicae, 2012
- Bifurcations and patterns in compromise processesPhysica D: Nonlinear Phenomena, 2003
- Granular Gas Dynamics2003
- Meet, discuss, and segregate!Complexity, 2002
- Modular Functions and Dirichlet Series in Number Theory1990
- Introduction to Analysis of the Infinite1988