A model of voting dynamics under bounded confidence with nonstandard norming

1.   Introduction

Various models of opinion dynamics have been studied since 1950s ([6,7]). At present, opinion studies are a well-developed field of research (see, for example, the monographs [14,20] and the recent survey [17]). The main goal of opinion dynamics is to describe and analyze evolution of public opinion in social systems.

Mostly, models studied in opinion dynamics are linear, which allows one to apply more or less standard methods of linear dynamical systems. One of the first nonlinear models was suggested in [11,12], where the notion of "bounded confidence" has been introduced. This notion formalizes the fact that, in the course of formation of public opinion, a member of the society is mostly influenced by individuals sharing a similar opinion.

The first opinion model based on the notion of bounded confidence, introduced by Hegselmann and Krause, was later called the Hegselmann – Krause (HK) model; this model and its generalizations have been intensively studied by various authors, see, for example, [5,16,13,1,15,4,3,10,21,22,8]. Mostly, the results were based on computer simulations, and it was noticed that "rigorous analytical results are difficult to obtain [9].

In the paper [18], a modification of the HK model suggested by Campi was studied. Let us consider the dynamics of opinions in a society of voters who have to choose between two options, -1 and 1. Assume that the society is formed by $N$ individuals (usually called "agents"), and let $v_k^n\in[-1, 1]$ be the opinion of individual $k$ at time moment $n$.

Fix a positive ${\varepsilon}<1$ (the level of bounded confidence in the society) and consider for $k\in {\{1, \dots, N\}}$ the set of indices

This is the set of indices of agents whose opinions influence agent $k$ at time moment $n$.

In the classical HK model, the dynamics of voters is based on the following procedure: at the step of the process of opinion formation at time $n$, the new opinion of agent $k$ is obtained by adding to $v_k^n$ a value proportional to the average of values $v_l^n-v_k^n$ over indices $l$ belonging to the set $J(v_k^n)$.

In the model studied in the paper [18], the average of values $v_l^n-v_k^n$ over the set $J(v_k^n)$ is replaced by the average of values $v_l^n$ over the set $J(v_k^n)$.

Thus, when taking the average, the opinion of agent $k$ is included into consideration. In the case where an agent has no other agents with ${\varepsilon}$-close opinions, this means that the agent enforces her/his belief: in absence of counter-arguments, one tends to strengthen her/his own opinion.

Mathematically, this modification of the process may lead to the following consequence: some of the new values may be outside the interval $[-1, 1]$. In [18], a "cutting" procedure was suggested; the new opinion value is obtained by replacing the values less than -1 by -1, and the values more than 1 are replaced by 1.

The dynamics of the appearing dynamical system has been completely described in [18]. It was shown that if ${\varepsilon}\leq 1/2$, then any trajectory tends to a fixed point as time goes to infinity. All possible fixed points have been characterized. It was shown that any fixed point $P = (p_1, \dots, p_N)$ with $|p_k| = 1, \;k\in {\{1, \dots, N\}}$, is attracting, while all the remaining fixed points are Lyapunov unstable. Modifications of the model studied in [18] were considered in the recent papers [2] (where the average of values $v_l^n$ has been replaced by values $i(v_l^n)$ for a wide class of influence functions $i$) and [19] (where the finite set of agents has been replaced by the continuum $[0, 1]$).

In this paper, we study a model similar to that considered in [18] but with a different norming. Instead of "cutting" the values obtained at the first step (when we add to $v_k^n$ a value proportional to the average of values $v_l^n$ over the set $J(v_k^n)$ and obtain values $w_k^n$), now we divide the values $w_k^n$ by the maximal absolute value of $w_k^n$ (see a detailed description of the appearing dynamical system in the next section).

Our main results are as follows:

● we find a condition (see inequality (6)) under which any trajectory tends to a fixed point as time goes to infinity;

● we describe all fixed points in this case;

● we show that both fixed points $P_- = (-1, \dots, -1)$ and $P_+ = (1, \dots, 1)$ are attracting;

● we prove that all the remaining fixed points are Lyapunov stable (thus, the dynamics of our system is completely different from that of the system studied in [18]) but not attracting;

● we give an example of the system for which condition (6) is not satisfied and that has an unstable fixed point.

Of course, our reasoning in this paper essentially differs from that in [18].

The structure of the paper is as follows. Section 2 is devoted to the statement of the problem. In Section 3, basic properties of the system are described. In Section 4, we prove the convergence of trajectories to fixed points. In Section 5, stability of fixed points is analyzed. In Section 6, we give an example of a system with an unstable fixed point. Section 7 contains several examples of computer modeling.

2.   Statement of the problem

We study a dynamical system modeling the following problem of opinion dynamics. A society consisting of $N$ agents has to choose between two options, 1 and -1. Let $v_k^n\in[-1, 1]$ be the opinion of agent with index $k\in {\{1, \dots, N\}}$ at time moment $n = 0, 1, \dots$ and let

be the array of opinions at time moment $n$.

Let us define the operator $\Phi$ determining the iterative process which models the opinion dynamics. Fix two numbers $h, {\varepsilon}\in(0, 1)$ and an array

Introduce the sets

Denote by $I(v_k)$ the cardinality of the (nonempty) set $J(v_k)$.

Define an auxiliary array

where

Now, assuming that $W(V)$ is a nonzero array, we set

and

where

Clearly,

We can represent $W(V)$ in the form

where $E$ is the identity matrix and the matrix $A$ is row-stochastic; it easily follows from the inclusion $h\in(0, 1)$ that if $V\neq 0$, then $W(V)\neq 0$ as well.

Consider an initial array of opinions $V^0 = (v_1^0, \dots, v_N^0)$. If $V^0 = 0$, then we set $V^n = 0$ for $n\geq 0$ and exclude this trivial case from the further consideration.

It follows from the above reasoning that if $V^0\neq 0$, then $V^n = \Phi^n(V^0)$ are defined for $n>0$. Our main goal is to study the behavior of positive trajectories of the appearing dynamical system.

3.   Basic properties of the system

For simplicity, we denote $w_k^n = w_k(V^n)$.

Denote by ${\mathcal V}$ the set of arrays $V$ such that

Lemma 3.1. If $v\in{\mathcal V}$, then $\Phi(V)\in{\mathcal V}$.

Proof. It follows from [18,Corollary 1] that inequality (3) implies the inequalities $w_k(V)\leq w_{k+1}(V)$; division by $m(W(V))$ preserves the required inequalities.

It is easily seen that the value $w_k(V)$ in (1) does not depend on the indexing of components of $V$. Hence, in what follows, we may (and will) consider trajectories belonging to ${\mathcal V}$.

Let us note one important inequality. Without loss of generality, we may assume that, for given $V$, $m(W(V)) = |w_N(V)|$. Then

Lemma 3.2. If $|v_k^n - v_{k+1}^n| > {\varepsilon}$, then $|v_k^\nu - v_{k+1}^\nu| > {\varepsilon}$ for all $\nu > n$.

Proof. It is enough to prove the statement for $\nu = n+1$.

The inequality $|v_k^n - v_{k+1}^n| > {\varepsilon}$ implies that $J(v_k^n) \subset \{1, \ldots, k\}$ and $J(v_{k+1}^n) \subset \{k+1, \ldots, N\}$. Hence,

and

Thus,

Now inequality (4) implies the required inequality

Remark 1. An analog of Lemma 3.2 does not necessarily hold for $v_k^n$ and $v_m^n$ with $|k-m|\neq 1$. Let us consider the following example.

Let $N = 8$, ${\varepsilon} = 1/2$, and $h = 1/3$. If

then $m(W(V^0)) = 1 + h$ and

Hence, $v_7^0-v_2^0 = 10/16> {\varepsilon}$, while $v_7^1-v_2^1 = 1/2 = {\varepsilon}$.

4.   Convergence to fixed points

In this section, we show that if

then any trajectory $\Phi^n(V)$ converges to a fixed point of $\Phi$ as $n\to\infty$.

Now we introduce the object which is the main tool in the following proofs.

Definition 4.1. For an array $V^n = \Phi^n(V^0)$, a set $\{k, k+1, \ldots, m\}\subset\{1, \ldots, N\}$ is called a band at time $n$ if the following properties are satisfied:

(1) if $k>1$, then $|v_{k-1}^n - v_k^n| > {\varepsilon}$, and if $m<N$, then $|v_{m}^n - v_{m+1}^n| > {\varepsilon}$;

(2) $|v_l^n- v_{l+1}^n| \leq {\varepsilon}$ for all $l\in \{k, \ldots, m-1\}.$

The value $|v_k^n - v_m^n|$ is called the diameter of the band $\{k, k+1, \ldots, m\}$.

In what follows, we often use the term band instead of band at time $n$.

Remark 2. Since we work with trajectories in ${\mathcal V}$,

for any band $\{k, k+1, \ldots, m\}$.

It follows from Lemma 3.2 that if $\{k, k+1, \ldots, m\}$ is a band at time $n$ for some $V^n = \Phi^n(V^0)$, then no subset of $\{k, k+1, \ldots, m\}$ can be a subset of a band at time $\nu>n$ for $V^\nu$ containing either $k-1$ or $m+1$. Hence, either a band $\{k, k+1, \ldots, m\}$ at time $n$ for $V^n$ is a band at time $n+1$ for $V^{n+1}$ as well or it splits into a union of several bands of smaller lengths.

Thus, for any band $\{k, k+1, \ldots, m\}$ of any initial array $V^0$ there exists a unique decomposition

with $k_1 = k$, $m_r = m$, and $k_{j+1} = m_{j}+1$ and a time $\nu$ such that any $\{k_j, \dots, m_j\}$ is a band for any $V^n = \Phi^n(V^0)$ for any $n\geq \nu$ (i.e., it does not split into bands of smaller lengths as time grows).

Clearly, if $V^0$ is a nonzero array, then either $v_1^n = -1$ or $v_N^n = 1$ for any $n>0$. We assume that the same holds for $n = 0$.

We introduce the following condition on the initial array $V^0$.

Condition A. The array $V^0$ has a band $\{k, \dots, m\}$ at time $0$ such that $v_k^0, \dots, v_m^0$ are nonzero and have the same sign.

If $V^0$ contains a single band, then this band is ${\{1, \dots, N\}}$, and, by our assumption, either $v_1^0 = -1$ either $v_N^0 = 1$. Then inequality (6) implies that $V^0$ satisfies Condition A.

If $V^0$ contains at least two bands, then it obviously satisfies Condition A.

Thus, inequality (6) implies Condition A for any array $V^0$.

In the remaining part of this section, we assume that any initial array $V^0$ satisfies Condition A.

Lemma 4.2. For any $V^0$, the following relation holds:

Proof. Fix a band $\{k, \dots, m\}$ for $V^0$ at time $0$ such that $v_k^0, \dots, v_m^0$ are nonzero and have the same sign. Without loss of generality, we may assume that these values are positive.

Let us consider the behavior of $v_k^n$ as $n$ grows:

To get a contradiction, assume that relation (8) does not hold. Then there exists a subsequence $n_k$ tending to infinity such that

for some $\alpha\in(0, h)$.

Without loss of generality, we may assume that the above inequalities hold for all $n$. Then

where

Thus,

which contradicts the inequalities $v_k^n\leq 1$.

Let us describe the behavior of a band of diameter not more than ${\varepsilon}$.

Lemma 4.3. Assume that a band $\{k, \dots, m\}$ foran array $V^{\nu}$ at time $\nu$ has diameter not more than ${\varepsilon}$ and does not split as time grows. Then the diametersof this band for the arrays $V^n$ at all times $n>\nu$ are not more than ${\varepsilon}$ as well and

Proof. Without loss of generality, we assume that $\nu = 0$. Applying Lemma 4.2, we may also assume that

It follows from our assumption (the band does not split) that $J(v_k^n) = J$ and $I(v_k^n) = I$ for $n\geq 0$. Hence, if $n\geq 0$, then

This obviously implies the statement of our lemma.

Now we prove that the diameter of every band in decomposition (7) does not exceed ${\varepsilon}$ for times $n\geq\nu$ if $\nu$ is large enough.

Lemma 4.4. For any initial array $V^0$ and any its band $\{k, \dots, m\}$ at time $0$ thereexists a time $\nu$ such that the diameter of any band $\{k_j, \dots, m_j\}$ in decomposition (7) for $V^n$ with $n\geq \nu$ does not exceed ${\varepsilon}$.

First we fix some constants.

Fix a positive ${\delta}$ such that

a positive $\beta$ such that

and a positive $\alpha$ such that

We get Lemma 4.4 as a corollary of the following two lemmas.

Lemma 4.5. Assume that a band $\{k, \dots, m\}$ has diameter larger than ${\varepsilon}$ for all $n\geq 0$ and does not split as time grows. There exists $n_0 \geq 0$ such that the following implication holds. If $v_l^n \in [v_k^n, v_k^n + \delta)$ for all $l \in J(v_k^n)$ and for some $n\geq n_0$, then there exists an index $s$ such that $v_s^{n+1}\in [v_k^{n+1} + \delta, v_k^{n+1} + {\varepsilon}]$.

Proof. Fix a time $n$ and let $s = \max J(v_k^n)$. We will show that the assumption of the lemma implies the inclusion $v_s^{n+1}\in [v_k^{n+1} + \delta, v_k^{n+1} + {\varepsilon}]$.

By assumption, the value $v_m^n-v_k^n$ (the diameter of the band $\{k, \dots, m\}$) is larger than ${\varepsilon}$ for all $n$, and from the inequality

it follows that $s<m$. Hence, $s, s+1\in\{k, \dots, m\}$. Since $\{k, \dots, m\}$ is a band, $s+1\in J(v_s^n)$.

Then we have the following estimates for $n\geq 0$:

In the last line, we apply inequality (10).

To get the upper bound, take a number $n_0 \geq 0$ such that

If $n\geq n_0$, then

where in the last line we take into account that $\delta\leq\dfrac{\varepsilon}{3}$ due to (10).

Lemma 4.6. Assume that a band $\{k, \dots, m\}$ has diameter larger than ${\varepsilon}$ for all $n\geq 0$ and does not split as time grows. There exists $n_0 \geq 0$ such that for any $n\geq n_0$, the following inequality holds:

Proof. We claim that there exists $n_0$ such that

and if there exists an index $s$ such that $v_s^{n}\in [v_k^{n} + \delta, v_k^{n} + {\varepsilon}]$, then

Then the statement of our lemma follows from Lemma 4.5. Indeed, there are two possible cases:

● There exists an index $s$ such that $v_s^{n}\in [v_k^{n} + \delta, v_k^{n} + {\varepsilon}]$.

Applying the inequalities (13) and (14), we get

● For all $l \in J(v_k^n)$ we have $v_l^n \in [v_k^n, v_k^n + \delta)$. From Lemma 4.5 we obtain that there exists an index $s$ such that $v_s^{n+1}\in [v_k^{n+1} + \delta, v_k^{n+1} + {\varepsilon}]$. Then, applying first inequality (14) and the inequality (13), we get

which completes the proof.

To establish estimate (13), let us fix a positive $\alpha$ such that inequality (12) holds.

Consider an $n_0 \geq 0$ such that

If $n\geq n_0$, then

Next, we assume that $v_s^{n}\in [v_k^{n} + \delta, v_k^{n} + {\varepsilon}]$. Let us estimate

To prove Lemma 4.4, we assume that the diameter of the band $\{k, \ldots, m\}$ is more than ${\varepsilon}$ for arbitrarily large $n_0$. Then Lemmas 4.5 and 4.6 lead to a contradiction since the sequence $(v_k^n)$ is bounded.

Theorem 4.7. If condition (6) is satisfied, thenany trajectory $\Phi^n(V^0)$ tends to a fixed point of $\Phi$ as $n\to\infty$.

Proof. It follows from Lemmas 4.3 and 4.4 that for any initial nonzero array $V^0$ the following holds: if $n$ is large enough, then the set ${\{1, \dots, N\}}$ is the union of disjoint subsets,

where $b_1 = 1$, $c_r = N$, $c_{i+1} = b_i+1$, and any set $\{b_i, \dots, c_i\}$ is a band for $V^n$ such that

There are the following possible cases:

● $v^n_{b_i}\geq 0$ for some $n$; then $v^m_{k}\geq 0$ for all $b_i\leq k\leq c_i$ and $m\geq n$;

● $v^n_{c_i}\leq 0$ for some $n$; then $v^m_{k}\leq 0$ for all $b_i\leq k\leq c_i$ and $m\geq n$;

● $v^n_{b_i}v^n_{c_i}< 0$ for some $n$; then $v^m_{k}v^m_k<0$ for all $b_i\leq k\leq c_i$ and $m\geq n$.

In any of these cases, there exist numbers $a_i\in[0, 1]$ such that

(and $a_i = 0$ in the third case).

It follows from the left-hand side of inequality (5) that

hence,

In addition, either $a_1 = -1$ or $a_r = 1$ (or both possibilities are realized). Clearly, the corresponding array

is a fixed point of $\Phi$ such that

Remark 3. In fact, the proofs of Lemmas 4.3 and 4.4 (and hence, of Theorem 4.7) are based not on condition (6) but on the assumption that for any $V^0$, relation (8) holds (which we deduce from Condition A).

We refer to condition (6) in Theorem 4.7 since the above-formulated two assumptions are of "inner" character while condition (6) relates values from the statement of the problem.

5.   Stability of fixed points

In this section, we assume that relation (8) holds. As was noted, this assumption implies the conclusion of Theorem 4.7. Let us study the stability properties of the appearing fixed points of $\Phi$.

First we introduce the following notation. Let $P = (p_1, \dots, p_N)$ be a fixed point of $\Phi$. An array

is called the scheme of the fixed point $P$ if

where $b_1 = 1$, $c_r = N$, and $b_{i+1} = c_i+1$, is a band for $P = \Phi^n(P)$ at any time $n$ and

Let us select two fixed points, $P_-$ and $P_+$, having schemes $(B_1(-1))$ and $(B_1(1))$, respectively, where $B_1(-1) = B_1(1) = {\{1, \dots, N\}}$.

Theorem 5.1. If relation (8) holds, then

(1) both fixed points $P_-$ and $P_+$ are asymptoticallystable for $\Phi$;

(2) any fixed point $P$ different from $P_-$ and $P_+$ is Lyapunov stable but not asymptotically stable.

Proof. Let us first prove item (1). We consider the case of the fixed point $P_+$, for $P_-$ the proof is similar.

First we prove that $P_+$ is Lyapunov stable. Fix a $\Delta>0$; without loss of generality, we assume that $\Delta\leq {\varepsilon}$.

Let ${\delta}\leq\Delta$ and consider a $V = (v_1, \dots, v_N)\in{\mathcal V}$ such that

Then $J(v_k) = {\{1, \dots, N\}}$ for $k\in {\{1, \dots, N\}}$; hence,

and

This implies that

Thus, $P_+$ is Lyapunov stable.

As was said before introducing Condition A, we may assume that, for any $V$, either $(\Phi^n(V))_1 = -1$ or $(\Phi^n(V))_N = 1$ for $n\geq 0$. In our case, inequality (15) implies that $v^n_N = (\Phi^n(V))_N = 1$ for all $n$, and it follows from Lemma 4.3 that

Thus, $P_+$ is asymptotically stable.

Now we prove item (2). Consider two possible cases.

Case 1. The fixed point $P$ has scheme $(B_1(-1), B_2(1))$ with nonempty $B_1(-1),$ $B_2(1)$. In this case, the Lyapunov stability is proved by the same reasoning as above. To prove that $P$ is not asymptotically stable, note that any point with scheme $(B_1(-1+ {\delta}), B_2(1))$, where ${\delta}\in(0, {\varepsilon})$, is a fixed point of $\Phi$.

Case 2. The fixed point $P = (p_1, \dots, p_n)$ has scheme

where $B_l(a_l)$ is nonempty and $|a_l|\neq 1$. In this case, $|a_l|\in(-1+ {\varepsilon}, 1- {\varepsilon})$ and one of the sets $B_1(-1), B_r(1)$ is nonempty. To simplify consideration, assume that $B_1(-1)$ is empty (the remaining cases are treated similarly).

Fix a $\Delta>0$ such that

Without loss of generality, we assume that $\Delta\leq {\varepsilon}/2$. Clearly, if $V = (v_1, \dots, v_N)$ and

then $J(v_k) = J(p_k)$ for $k\in {\{1, \dots, N\}}$.

Take a positive ${\delta}$ such that

Clearly, in this case ${\delta}<\Delta$.

Introduce the following condition on the trajectory of an initial point $V^0$.

Condition C($\nu$):

We show that if

for an initial point $V^0$, then Condition C($\nu$) is satisfied for all $\nu\geq 0$, which, of course, means that $P$ is Lyapunov stable.

Thus, below we assume that inequalities (18) are satisfied.

Since ${\delta}<\Delta$, Condition C($0$) is satisfied. Now we show that Condition C($\nu$) implies Condition C($\nu+1$).

We start with $k\in B_r(1)$. Due to Condition C($\nu$), $J(v_k^n) = B_r(1)$ for $0\leq n\leq \nu$. The same reasoning as in the proof of item (1) shows that

Denote

Since $v^{0}_k\geq 1- {\delta}$ for $k\in B_r(1)$,

and the inequalities

hold.

Now we consider indices $k\in B_l(a_l)$ with $l<r$. Condition C($\nu$) and inequalities (18) imply that

for $0\leq n\leq \nu+1$.

Hence, if $k\in B_l(a_l)$, then it follows from inequality (19) with $n = \nu+1$ that

Similarly one shows that

which proves that Condition C($\nu+1$) is satisfied.

This completes the proof of Lyapunov stability of the fixed point $P$.

To prove that $P$ is not asymptotically stable, note that any point with scheme

where ${\delta}$ is small enough, is a fixed point of $\Phi$.

6.   Example with a single band

The following example shows that if ${\varepsilon}$ is not small, then the dynamics of the system can be essentially different from that described above.

Let $N = 6$ and ${\varepsilon} = 1/2$. Then $\Phi$ has a fixed point

Clearly,

and $\Phi(P) = P$.

This fixed point is unstable; for any small ${\delta}>0$, the point

has a band $\{ {\delta}, {\delta}, 1/2, 1\}$ at time $0$ with nonzero elements of the same sign; the reasoning applied in the proof of Lemma 4.2 shows that

which, compared with relation (20) indicates that the fixed point $P$ is unstable.

In Fig. 3 of the next section, the dynamics with ${\delta} = 0.01$ is shown.

7.   Numerical experiments

The first figure illustrates the dynamics of the system for which condition (6) holds. Figure 1 shows the initial distribution of opinions and the evolution of the system at times 10, 30, and 70. One can see that at time 70, the equilibrium is almost reached. The fixed points of this system are 4 groups of equal numbers.

The second example illustrates the evolution of the system with a larger number of agents. Here, condition (6) is not met, but Condition A holds. Figure 2 shows the initial distribution of such a system with ${\varepsilon} = 0.5, \ h = 0.1$ and its evolution at times 20, 40, and 90.

Figure 3 shows the dynamics of the band

which was mentioned in Section 6. The illustration shows the initial distribution of this system with $\delta = 0.01$ and its evolution at times 10, 30, and 70. In this case, the band of positive values collapses into a band with the same values.

Acknowledgments

The authors are grateful to the reviewers for valuable comments which allowed to improve the presentation.