On the convergence of the Hegselmann-Krause system

Arnab Bhattacharyya, Mark Braverman, Bernard Chazelle, Huy L. Nguyen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

42 Scopus citations

Abstract

We study convergence of the following discrete-time non-linear dynamical system: n agents are located in ℝ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 nO(n) resulting from a more general theorem of Chazelle [4]. Also, we show a quadratic lower bound and improve the upper bound for one-dimensional systems to O(n 3).

Original languageEnglish (US)
Title of host publicationITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science
Pages61-65
Number of pages5
DOIs
StatePublished - Feb 11 2013
Event2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013 - Berkeley, CA, United States
Duration: Jan 9 2013Jan 12 2013

Publication series

NameITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science

Other

Other2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013
CountryUnited States
CityBerkeley, CA
Period1/9/131/12/13

All Science Journal Classification (ASJC) codes

  • Management of Technology and Innovation
  • Computer Science (miscellaneous)

Keywords

  • convergence
  • hegselmann-krause system
  • opinion dynamics

Fingerprint Dive into the research topics of 'On the convergence of the Hegselmann-Krause system'. Together they form a unique fingerprint.

Cite this