2012/11/08 by Arnab Bhattacharyya, Mark Braverman, Bhattacharyya, Arnab +5 · 7 citations
Computer Science · Physics and Astronomy · #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) #cs.DS #cs.SI #nlin.AO
paper · pdf · doi:10.48550/arxiv.1211.1909
9 pages, 1 figure, to appear in ITCS '13
arxiv created 2012/11/08 · arxiv updated 2012/11/09
We study convergence of the following discrete-time non-linear dynamical system: n agents are located in Rd 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. Also, we show a quadratic lower bound and improve the upper bound for one-dimensional systems to O(n3).