On the convergence of the Hegselmann-Krause system

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

doi:10.1145/2422436.2422446

On the convergence of the Hegselmann-Krause system

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

62 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 n^O(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 ³).

Original language	English (US)
Title of host publication	ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science
Pages	61-65
Number of pages	5
DOIs	https://doi.org/10.1145/2422436.2422446
State	Published - 2013
Event	2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013 - Berkeley, CA, United States Duration: Jan 9 2013 → Jan 12 2013

Publication series

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

Other

Other	2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013
Country/Territory	United States
City	Berkeley, CA
Period	1/9/13 → 1/12/13

All Science Journal Classification (ASJC) codes

Management of Technology and Innovation
Computer Science (miscellaneous)

Keywords

convergence
hegselmann-krause system
opinion dynamics

Access to Document

10.1145/2422436.2422446

Cite this

Bhattacharyya, A., Braverman, M., Chazelle, B., & Nguyen, H. L. (2013). On the convergence of the Hegselmann-Krause system. In ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science (pp. 61-65). (ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science). https://doi.org/10.1145/2422436.2422446

@inproceedings{651aef9d8c604a99aef0f34a4e012bac,

title = "On the convergence of the Hegselmann-Krause system",

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).",

keywords = "convergence, hegselmann-krause system, opinion dynamics",

author = "Arnab Bhattacharyya and Mark Braverman and Bernard Chazelle and Nguyen, {Huy L.}",

year = "2013",

doi = "10.1145/2422436.2422446",

language = "English (US)",

isbn = "9781450318594",

series = "ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science",

pages = "61--65",

booktitle = "ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science",

note = "2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013 ; Conference date: 09-01-2013 Through 12-01-2013",

}

Bhattacharyya, A, Braverman, M , Chazelle, B & Nguyen, HL 2013, On the convergence of the Hegselmann-Krause system. in ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science. ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science, pp. 61-65, 2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013, Berkeley, CA, United States, 1/9/13. https://doi.org/10.1145/2422436.2422446

On the convergence of the Hegselmann-Krause system. / Bhattacharyya, Arnab; Braverman, Mark ; Chazelle, Bernard et al.
ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science. 2013. p. 61-65 (ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On the convergence of the Hegselmann-Krause system

AU - Bhattacharyya, Arnab

AU - Braverman, Mark

AU - Chazelle, Bernard

AU - Nguyen, Huy L.

PY - 2013

Y1 - 2013

N2 - 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).

AB - 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).

KW - convergence

KW - hegselmann-krause system

KW - opinion dynamics

UR - http://www.scopus.com/inward/record.url?scp=84873349264&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84873349264&partnerID=8YFLogxK

U2 - 10.1145/2422436.2422446

DO - 10.1145/2422436.2422446

M3 - Conference contribution

AN - SCOPUS:84873349264

SN - 9781450318594

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

SP - 61

EP - 65

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

T2 - 2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013

Y2 - 9 January 2013 through 12 January 2013

ER -

On the convergence of the Hegselmann-Krause system

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this