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

References in corpus (13)

• Statistical physics of social dynamics
• Social Balance on Networks: The Dynamics of Friendship and Enmity
• Bifurcations and Patterns in Compromise Processes
• Multiscaling in Infinite Dimensional Collision Processes
• Multi-body Interactions and Non-Linear Consensus Dynamics on Networked Systems
• Influence of correlations on the velocity statistics of scalar granular gases
• Consensus on simplicial complexes, or: The nonlinear simplicial Laplacian
• Third and fourth degree collisional moments for inelastic Maxwell models
• Velocity Distribution of Driven Inelastic One-component Maxwell gas
• Cutoff for the Averaging process on the hypercube and complete bipartite graphs
• Concentration and local smoothness of the averaging process
• Tiny fluctuations of the averaging process around its degenerate steady state
• On the convergence of nonlinear averaging dynamics with three-body interactions on hypergraphs