On the Convergence of the Hegselmann-Krause System

2012/11/08 by Bhattacharyya, Arnab, Braverman, Mark, Chazelle, Bernard +1 · 6 citations
#Adaptation and Self-Organizing Systems (nlin.AO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Social and Information Networks (cs.SI)

paper · doi:10.48550/arxiv.1211.1909

Abstract

We study convergence of the following discrete-time non-linear dynamical system: n agents are located in R^d and at every time step, each moves synchronously to the average location of all agents within a unit distance of it. This popularly studied system was introduced by Krause to model the dynamics of opinion formation and is often referred to as the Hegselmann-Krause model. We prove the first polynomial time bound for the convergence of this system in arbitrary dimensions. This improves on the bound of n^O(n) resulting from a more general theorem of Chazelle. Also, we show a quadratic lower bound and improve the upper bound for one-dimensional systems to O(n³).

Cited by

• Equivalent bounded confidence processes
• Opinion Dynamics: A Comprehensive Overview
• Exponential convergence of multiagent systems with lack of connection
• Localmax dynamics for attention in transformers and its asymptotic behavior
• Universality and Invariance in Hegselmann-Krause Opinion Dynamics: Proof of Three Conjectures
• The 2R-Conjecture for the Hegselmann--Krause Model: A Proof in Expectation and New Directions

Related

• A quadratic lower bound for the convergence rate in the one-dimensional Hegselmann-Krause bounded confidence dynamics
• On Convergence Rate of Scalar Hegselmann-Krause Dynamics
• On the Convergence Properties of Social Hegselmann-Krause Dynamics
• Inertial Hegselmann-Krause Systems
• How friends and non-determinism affect opinion dynamics