Bounded confidence dynamics and graph control: Enforcing consensus

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)