# American Institute of Mathematical Sciences

September  2020, 15(3): 489-517. doi: 10.3934/nhm.2020028

## Bounded confidence dynamics and graph control: Enforcing consensus

 1 Georgia Institute of Technology, Program in Quantitative Biosciences, Georgia Institute of Technology School of Physics, Atlanta, GA 30332, USA 2 Arizona State University, School of Mathematical and Statistical Sciences, Tempe, AZ 85257-1804, USA

Received  December 2019 Revised  July 2020 Published  September 2020

Fund Project: The second author wishes to thank Benedetto Picolli for helpful discussions

A generic feature of bounded confidence type models is the formation of clusters of agents. We propose and study a variant of bounded confidence dynamics with the goal of inducing unconditional convergence to a consensus. The defining feature of these dynamics which we name the No one left behind dynamics is the introduction of a local control on the agents which preserves the connectivity of the interaction network. We rigorously demonstrate that these dynamics result in unconditional convergence to a consensus. The qualitative nature of our argument prevents us quantifying how fast a consensus emerges, however we present numerical evidence that sharp convergence rates would be challenging to obtain for such dynamics. Finally, we propose a relaxed version of the control. The dynamics that result maintain many of the qualitative features of the bounded confidence dynamics yet ultimately still converge to a consensus as the control still maintains connectivity of the interaction network.

Citation: GuanLin Li, Sebastien Motsch, Dylan Weber. Bounded confidence dynamics and graph control: Enforcing consensus. Networks & Heterogeneous Media, 2020, 15 (3) : 489-517. doi: 10.3934/nhm.2020028
##### References:

show all references

##### References:
The movement of an agent according to the bounded confidence dynamics (2.3)
Simulation of the opinion dynamics without and with control (resp. left and right figure), e.g. solving resp. (2.3) and Model 1 with $r_{*} = \frac12$. With the control (right), the dynamics converge to a consensus
Illustration of the critical regions (3.1) in $\mathbb{R}$ (interval behind ${\bf x}_i$) and $\mathbb{R}^2$ (semi-annulus region). The opinion ${\bf x}_i$ is attracted toward the local average $\overline{\bf x}_i$ and hence moves with velocity $\overline{\bf x}_i-{\bf x}_i$. In the "No-left behind dynamics" (1), ${\bf x}_i$ can only move only if there is no one in its critical region $\mathcal{B}_i$. Thus, ${\bf x}_i$ freezes whereas ${\bf x}_j$ is free to move in the left illustration
A configuration of agents (top) and the resulting interaction graph (edge set E, black) and behind graph (edge set $E^{\mathcal{B}})$, light blue). Note that the behind graph is a directed subgraph of the interaction graph
Counter-example in multi-dimension. Blue arrow is the velocity of each cluster. In this setting, every agent has someone in its critical region $\mathcal{B}_i$. Thus, the naive control in Model 1 would prevent anyone from moving
The velocity of agent $i$ is the projection of the desired velocity $\overline{\bf x}_i-{\bf x}_i$ onto the cone of admissible velocity $\mathcal{C}_{i}$
2D simulation of opinion dynamics without and with control (resp, top and bottom figure), e.g. solving resp. (1) and (3.5) with $r_* = \frac12$. With the control (bottom), the dynamics converge to a consensus
Preserving connectivity does not imply the convergence to a consensus. Here, when $r_* = 1$, the extreme points $x_1$ and $x_4$ will converge towards $x_2$ and $x_3$ respectively. However, $x_2$ and $x_3$ cannot move since $x_1$ and $x_4$ are always in their respective critical regions
The convex hull $\Omega(t_n)$ has to converge to a limit configuration $\Omega^\infty$. The dynamics converge to a consensus if $\Omega^\infty$ is reduced to a single point which we prove by contradiction. We distinguish three cases of limit configuration $\Omega^\infty$ depending on if the extreme point ${\bf x}_p^\infty$ has a so-called extreme neighbor $j$, i.e. $\|{\bf x}_p^\infty-{\bf x}_j^\infty\| = 1$
If the limit configuration $\{{\bf x}_k^\infty\}_k$ is not a consensus, the extreme point ${\bf x}_p(t_n)$ will eventually get inside the convex hull $\Omega^\infty$ which gives a contradiction
Situation in the case 2. The extreme point $x_p$ needs $x_{p_2}$ the neighbor of its neighbor $x_{p_1}$ to be pushed further to the right
The decay of the diameter $d(t)$ is first linear and then exponential after the diameter $d(t)$ becomes less than $1$
Left: diameter $d(t)$ over time for $100$ realizations (quantile representation). Right: stopping time $\tau$ (4.28) depending on the size of the critical region $r_*$
An example of how the behind graph can be relaxed while still ensuring that the interaction graph remains connected. The interaction graph is represented by undirected and directed edges, the behind graph is represented by only the blue directed edges. Agent 3 is in the behind region of both agent 2 and agent 4 and agents 2 and 4 are connected in the interaction graph therefore we may remove the edge from agent 4 to agent 3
The NOLB dynamics do not allow the red agent to disconnect from the blue agent (illustrated with a purple chain). The RNOLB dynamics allow this disconnection to occur but maintain connectivity of the whole configuration
The RNOLB dynamics can be seen as an interpolation between NOLB and bounded confidence
Diameter, $d(t)$ over time for 100 realizations of the RNOLB dynamics (quantile representation)
 [1] Hua Shi, Xiang Zhang, Yuyan Zhang. Complex planar Hamiltonian systems: Linearization and dynamics. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020406 [2] Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019 [3] Yancong Xu, Lijun Wei, Xiaoyu Jiang, Zirui Zhu. Complex dynamics of a SIRS epidemic model with the influence of hospital bed number. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021016 [4] Guillaume Cantin, M. A. Aziz-Alaoui. Dimension estimate of attractors for complex networks of reaction-diffusion systems applied to an ecological model. Communications on Pure & Applied Analysis, 2021, 20 (2) : 623-650. doi: 10.3934/cpaa.2020283 [5] Hongfei Yang, Xiaofeng Ding, Raymond Chan, Hui Hu, Yaxin Peng, Tieyong Zeng. A new initialization method based on normed statistical spaces in deep networks. Inverse Problems & Imaging, 2021, 15 (1) : 147-158. doi: 10.3934/ipi.2020045 [6] Evelyn Sander, Thomas Wanner. Equilibrium validation in models for pattern formation based on Sobolev embeddings. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 603-632. doi: 10.3934/dcdsb.2020260 [7] Zhimin Li, Tailei Zhang, Xiuqing Li. Threshold dynamics of stochastic models with time delays: A case study for Yunnan, China. Electronic Research Archive, 2021, 29 (1) : 1661-1679. doi: 10.3934/era.2020085 [8] Shigui Ruan. Nonlinear dynamics in tumor-immune system interaction models with delays. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 541-602. doi: 10.3934/dcdsb.2020282 [9] Eric Foxall. Boundary dynamics of the replicator equations for neutral models of cyclic dominance. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1061-1082. doi: 10.3934/dcdsb.2020153 [10] Divine Wanduku. Finite- and multi-dimensional state representations and some fundamental asymptotic properties of a family of nonlinear multi-population models for HIV/AIDS with ART treatment and distributed delays. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021005 [11] Xueli Bai, Fang Li. Global dynamics of competition models with nonsymmetric nonlocal dispersals when one diffusion rate is small. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3075-3092. doi: 10.3934/dcds.2020035 [12] Simone Fagioli, Emanuela Radici. Opinion formation systems via deterministic particles approximation. Kinetic & Related Models, 2021, 14 (1) : 45-76. doi: 10.3934/krm.2020048 [13] Simone Fiori. Error-based control systems on Riemannian state manifolds: Properties of the principal pushforward map associated to parallel transport. Mathematical Control & Related Fields, 2021, 11 (1) : 143-167. doi: 10.3934/mcrf.2020031 [14] Wenyuan Wang, Ran Xu. General drawdown based dividend control with fixed transaction costs for spectrally negative Lévy risk processes. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020179 [15] Wei-Chieh Chen, Bogdan Kazmierczak. Traveling waves in quadratic autocatalytic systems with complexing agent. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020364 [16] Onur Şimşek, O. Erhun Kundakcioglu. Cost of fairness in agent scheduling for contact centers. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021001 [17] Darko Dimitrov, Hosam Abdo. Tight independent set neighborhood union condition for fractional critical deleted graphs and ID deleted graphs. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 711-721. doi: 10.3934/dcdss.2019045 [18] Xiaoxian Tang, Jie Wang. Bistability of sequestration networks. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1337-1357. doi: 10.3934/dcdsb.2020165 [19] Soonki Hong, Seonhee Lim. Martin boundary of brownian motion on Gromov hyperbolic metric graphs. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021014 [20] Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $L^2-$norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

2019 Impact Factor: 1.053