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/2/11

Y1 - 2013/2/11

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 -