Opinion Dynamics with Limited Information
Abstract 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 all their friends is unrealistic. So, we...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2023
|
| Online Access: | https://hdl.handle.net/1721.1/152409 |
| _version_ | 1811082593921138688 |
|---|---|
| author | Fotakis, Dimitris Kandiros, Vardis Kontonis, Vasilis Skoulakis, Stratis |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Fotakis, Dimitris Kandiros, Vardis Kontonis, Vasilis Skoulakis, Stratis |
| author_sort | Fotakis, Dimitris |
| collection | MIT |
| description | Abstract
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 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]$$
s
i
∈
[
0
,
1
]
and maintains an expressed opinion
$$x_i(t) \in [0,1]$$
x
i
(
t
)
∈
[
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)$$
x
j
(
t
)
. The amount of influence j imposes on i is reflected by the probability
$$p_{ij}$$
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$$
(
x
i
(
t
)
-
s
i
)
2
and
$$(x_i(t) - x_j(t))^2$$
(
x
i
(
t
)
-
x
j
(
t
)
)
2
. An important class of dynamics in this setting are 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
$$\varOmega (1/\varepsilon )$$
Ω
(
1
/
ε
)
rounds to be within distance
$$\varepsilon $$
ε
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^*$$
x
∗
in
$$\tilde{O}(\log ^2(1/\varepsilon ))$$
O
~
(
log
2
(
1
/
ε
)
)
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^*$$
x
∗
of the FJ model within distance
$$\varepsilon $$
ε
in
$$\textrm{poly}(1/\varepsilon )$$
poly
(
1
/
ε
)
rounds. In view of our lower bound for no regret dynamics this rate of convergence is close to best possible. |
| first_indexed | 2024-09-23T12:05:53Z |
| format | Article |
| id | mit-1721.1/152409 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:05:53Z |
| publishDate | 2023 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1524092024-01-23T18:30:48Z Opinion Dynamics with Limited Information Fotakis, Dimitris Kandiros, Vardis Kontonis, Vasilis Skoulakis, Stratis Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Abstract 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 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]$$ s i ∈ [ 0 , 1 ] and maintains an expressed opinion $$x_i(t) \in [0,1]$$ x i ( t ) ∈ [ 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)$$ x j ( t ) . The amount of influence j imposes on i is reflected by the probability $$p_{ij}$$ 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$$ ( x i ( t ) - s i ) 2 and $$(x_i(t) - x_j(t))^2$$ ( x i ( t ) - x j ( t ) ) 2 . An important class of dynamics in this setting are 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 $$\varOmega (1/\varepsilon )$$ Ω ( 1 / ε ) rounds to be within distance $$\varepsilon $$ ε 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^*$$ x ∗ in $$\tilde{O}(\log ^2(1/\varepsilon ))$$ O ~ ( log 2 ( 1 / ε ) ) 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^*$$ x ∗ of the FJ model within distance $$\varepsilon $$ ε in $$\textrm{poly}(1/\varepsilon )$$ poly ( 1 / ε ) rounds. In view of our lower bound for no regret dynamics this rate of convergence is close to best possible. 2023-10-10T20:13:26Z 2023-10-10T20:13:26Z 2023-09-04 2023-09-10T03:10:18Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/152409 Fotakis, Dimitris, Kandiros, Vardis, Kontonis, Vasilis and Skoulakis, Stratis. 2023. "Opinion Dynamics with Limited Information." PUBLISHER_CC en https://doi.org/10.1007/s00453-023-01157-5 Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer US Springer US |
| spellingShingle | Fotakis, Dimitris Kandiros, Vardis Kontonis, Vasilis Skoulakis, Stratis Opinion Dynamics with Limited Information |
| title | Opinion Dynamics with Limited Information |
| title_full | Opinion Dynamics with Limited Information |
| title_fullStr | Opinion Dynamics with Limited Information |
| title_full_unstemmed | Opinion Dynamics with Limited Information |
| title_short | Opinion Dynamics with Limited Information |
| title_sort | opinion dynamics with limited information |
| url | https://hdl.handle.net/1721.1/152409 |
| work_keys_str_mv | AT fotakisdimitris opiniondynamicswithlimitedinformation AT kandirosvardis opiniondynamicswithlimitedinformation AT kontonisvasilis opiniondynamicswithlimitedinformation AT skoulakisstratis opiniondynamicswithlimitedinformation |