### 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 ^{3}).

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 | |

State | Published - Feb 11 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 | 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

## Fingerprint Dive into the research topics of 'On the convergence of the Hegselmann-Krause system'. Together they form a unique fingerprint.

## Cite this

*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