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 social network to communicate with each other. 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 both these systems converge in polynomial number of non-trivial steps, regardless of the social network in the first variant and noise patterns in the second variant.