Opinion dynamics with Limited Information

We study opinion formation games based on the famous model proposed by Friedkin
and Johsen (FJ model). In today's huge social networks the assumption that in
each round agents update their opinions by taking into account the opinions of
\emph{all} their friends is unrealistic. So, we are interested in the convergence
properties of 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 consider an opinion formation
process where each agent $i$ meets with  one random friend $j$ at each round
$t$ and learns only her current opinion $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 \emph{no regret} dynamics,
i.e. dynamics that ensure vanishing regret against the experienced
disagreement cost to the agents.  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 $\Omega(1/\eps)$ rounds to be within distance $\eps$ from the stable
point of the FJ model.  On the other hand, we provide an opinion update rule that does
not ensure no regret and converges to $x^\ast$ in $\tilde{O}(\log^2(1/\eps))$
rounds.  Finally, in our variant of the FJ model, we show that the agents can adopt
a simple opinion update rule that ensures no regret to the experienced disagreement
cost and results in an opinion vector that converges to the stable point $x^\ast$
of the FJ model within distance $\eps$ in $\mrm{poly}(1/\eps)$ rounds. In view of our
lower bound for no regret dynamics this rate of convergence is close to best
possible.


Joint work with Dimitris Fotakis, Vardis Kandiros and Vasillis Kontonis, WINE 2018