Skip to main content

On the convergence of the Hegselmann-Krause system.

Author(s): Bhattacharyya, Arnab; Braverman, Mark; Chazelle, Bernard; Nguyen, Huy L

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1dw9f
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).
Publication Date: 9-Jan-2013
Electronic Publication Date: 2013
Citation: Bhattacharyya, Arnab, Braverman, Mark, Chazelle, Bernard, Nguyen, Huy L. (2013). On the convergence of the Hegselmann-Krause system.. ITCS, 61 - 66. doi:10.1145/2422436.2422446
DOI: doi:10.1145/2422436.2422446
Pages: 61 - 66
Type of Material: Journal Article
Journal/Proceeding Title: ITCS
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.