How friends and non-determinism affect opinion dynamics

The Hegselmann-Krause system (HK system for short) is one of the most popular models for the dynamics of opinion formation in multiagent systems. Agents are modeled as points in opinion space, and at every time step, each agent moves to the mass center of all the agents within unit distance. The rate of convergence of HK systems has been the subject of several recent works. In this work, we investigate two natural variations of the HK system and their effect on the dynamics. In the first variation, we only allow pairs of agents who are friends in an underlying undirected social network to communicate with each other; moreover, the social network may itself be dynamic. In the second variation, agents may not move exactly to the mass center but somewhere close to it. The dynamics of both variants are qualitatively very different from that of the classical HK system. Nevertheless, we prove that, for any fixed ε > 0, both these systems make only a polynomial number of steps in which two agents separated by distance at least ε interact with each other, regardless of the social network in the first variant and with only a bound on the noise in the second.