### Interdisciplinary Seminar Series

Title: On the convergence of the Hegselmann-Krause system

Speaker: **Arnab Bhattacharyya**, DIMACS, Rutgers University

Date: Monday, October 22, 2012 11:00am - 12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We study convergence of the following discrete-time non-linear dynamical system: n agents
are located in R^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. Also, we show a quadratic lower bound and improve the upper bound
for one-dimensional systems to O(n^3).

Joint work with Mark Braverman, Bernard Chazelle and Huy L. Nguyen

DIMACS/CCICADA
Interdisciplinary Series, Complete Fall Calendar 2012