Opinion Dynamics with Limited Information

Abstract

We study opinion formation games based on the Friedkin-Johnsen (FJ) model. We are interested in simple and natural variants of the FJ model that use limited information exchange in each round and converge to the same stable point. As in the FJ model, we assume that each agent i has an intrinsic opinion $s_i \in [0,1]$ and maintains an expressed opinion $x_i(t) \in [0,1]$ in each round t. To model limited information exchange, we assume that each agent i meets with one random friend j at each round t and learns only $x_j(t)$. The amount of influence j imposes on i is reflected by the probability $p_{ij}$ with which i meets j. Then, agent i suffers a disagreement cost that is a convex combination of $(x_i(t) - s_i)^2$ and $(x_i(t) - x_j(t))^2$.

An important class of dynamics in this setting are no regret dynamics. We show an exponential gap between the convergence rate of no regret dynamics and of more general dynamics that do not ensure no regret. We prove that no regret dynamics require roughly ${\varOmega }(1/\varepsilon )$ rounds to be within distance $\varepsilon$ from the stable point $x^*$ of the FJ model. On the other hand, we provide an opinion update rule that does not ensure no regret and converges to $x^*$ in ${\tilde{O}}(\log ^2(1/\varepsilon ))$ rounds. Finally, we show that the agents can adopt a simple opinion update rule that ensures no regret and converges to $x^*$ in $\mathrm {poly}(1/\varepsilon )$ rounds.

Part of this work was performed while Vasilis Kontonis was a graduate student at the National Technical University of Athens.

Stratis Skoulakis is supported by a scholarship from the Onassis Foundation.