Opinion formation in voting processes under bounded confidence

1.   Introduction

Studies on opinion dynamics aim to describe the processes by which opinions develop and take form in social systems, and research in this field goes back to the early fifties, [10,12]. In opinion studies, the word "consensus" refers to the agreement among individuals of a society towards a common view, a concept relevant to diverse endeavors of societal, commercial and political interest. Consensus in opinion dynamics has been the object of several contributions such as [11,23,24,28,4,5,6,14]. A commonplace of these studies is that public opinion often evolves to a state in which one opinion predominates, but complete consensus is seldom achieved. Some basic models for opinion dynamics are described in the recent monographs [27] and [21].

Most models in opinion dynamics are linear. One of the first nonlinear models was analyzed in [19,18], where the notion of "bounded confidence" was also introduced. Bounded confidence concepts were further developed in [15,8], while other nonlinear models based on similar approaches were studied in [7,30]. As we shall see, the notion of bounded confidence is quite relevant to the present contribution. In 2002, Hegselmann and Krause, [15], published an interesting study about an opinion model with bounded confidence, later called the Hegselmann - Krause (HK) model, and provided computer simulations to illustrate the behavior of this model. In the same publication, they also noted that "rigorous analytical results are difficult to obtain". After that, the HK model, and its generalizations, attracted a significant deal of attention, see e.g. [9,26,20,1,22,3,2,17,29,31,13]. In particular, some theoretical results on sufficient conditions of convergence valid for a wide class of models of continuous opinion dynamics based on averaging (including the HK model and some models studied by Weisbuch and Deffuant) were obtained in [25]. Paper [16] extends the HK model by also including leaders and radical groups and derives various interesting behaviors resulting from this extension.

In this paper, we are especially interested in the dynamics of voters that have to choose between two alternatives. In this context, a natural assumption is that voters are more influenced by individuals sharing a similar opinion, which, when taken to its extreme, leads to models with bounded confidence. We shall discuss more in detail this aspect below after introducing the model. We contend that this situation leads to fixed points in the dynamics that correspond to the formation of opinion clusters. We study analytically these fixed-points, and also analyze their stability properties. Although the present study refers to a simplified model, it is able to unveil and explain at a theoretical level fundamental features that have been observed in practice.

While the model is described in detail in the next section, for explanation purposes we feel advisable to introduce here certain salient features of it. A population is formed by $ N $ individuals, also called "agents". The agents' opinion in regard of an electoral question with two options (identified by the numbers $ -1 $ and $ 1 $) is described by $ v_k \in [-1, 1] $, $ k = 1, \dots, N $, where a value close to $ -1 $ means that the individual $ k $ carries an opinion more in favor of the option $ -1 $, while the opposite holds with a value $ v_k $ close to $ 1 $. Opinions $ v_k $ evolve in discrete time through interaction. At any point in time, the new opinion of agent $ k $ is formed by taking into account the opinions of agents whose value $ v_l $ are not too distant from $ v_k $ (bounded confidence). More precisely, fix a number $ \epsilon > 0 $ (not necessarily a small number) and denote by $ J(v_k) $ the set of indices $ l $ of agents with opinions $ {\epsilon} $-close to $ v_k $, i.e.

The new opinion of agent $ k $ is obtained by adding to $ v_k $ a value proportional to the average of opinions $ v_l $ over the set $ J(v_k) $ and "cutting" the new value if it exceeds the boundaries of the interval $ [-1, 1] $ (for a precise description, refer to the next section). It turns out that, apart from special configurations that give unstable equilibria, this dynamics leads to final configurations where the population splits in two clusters, having values $ -1 $ and $ 1 $. When taking the average to compute the value by which $ v_k $ is updated, also the value of agent $ k $ is included in the calculation. In the extreme case where an agent has no other $ {\epsilon} $-close agents, this implies that this agent reinforces her/his belief: in absence of counter-arguments, one tends to strengthen her/his own initial opinion; in general, one's opinion is compared with the opinion of others in a neighborhood to determine the evolution.

In the proposed model, an agent is only influenced by agents who are having a similar idea. This modeling assumption only holds in first approximation as agents may also interact with others that think quite differently and get influenced by them. Hence, this model only captures the predominant elements in a social interaction, while it neglects various second-order aspects. We also note that assuming that agents are "deaf" to others thinking differently is getting more realistic as the world evolves towards interaction schemes based on social media and the web where the contacts and sources of information are selected by the users.

The structure of the paper is as follows. In Section 2, the mathematical definition of the model is given. Section 3 is devoted to study the dynamical behavior of the solutions generated by the model: we describe fixed points, study their stability, and show that any positive trajectory tends to a fixed point. Numerical examples are finally presented in Section 4. These examples show interesting features, for example that the level of interaction influences the opinions in the long run to the point that the predominance of one option over the other can be reversed depending on the interaction level in the society.

2.   Definition of the opinion model

The opinion of $ N $ agents is described by the finite array

where $ v_k $ has to be interpreted as the level of appreciation of agent $ k $ for one among two options: a value $ v_k $ close to $ -1 $ means that agent $ k $ has a preference for option $ -1 $, and the closer $ v_k $ to $ -1 $, the stronger the preference; the opposite holds for option $ 1 $. Denote by $ \mathcal{V} = [-1, 1]^N $ the set of such arrays.

We fix two numbers $ h, {\epsilon}\in(0, 1) $. In addition, we fix two functions, $ a(v, w) $ and $ i(v) $ (called affinity and influence function, respectively).

In this study, the function $ a(\cdot, \cdot) $ is defined as follows:

If $ a(v_k, v_l) = 1 $, we sometimes say that "$ v_k $ is influenced by $ v_l $."

The $ i(\cdot) $ function is instead defined simply as:

For $ k = 1, \dots, N $, denote by $ J(v_k) $ the set of indices $ l \in [1, N] $ (here and below, we denote by $ [a, b] $ the set of indices $ \{a, \dots, b\} $) such that $ |v_l-v_k|\leq {\epsilon} $ and by $ I(v_k) $ the cardinality of the set $ J(v_k) $.

We study the dynamics on $ \mathcal{V} $ defined by the following operator $ \Phi $. First we fix a $ V\in \mathcal{V} $ and consider the auxiliary array

defined as follows

Note that the second term in the equation also contains agent $ k $ itself, which reflects the fact that an agent's opinion has a tendency to reinforce and drift towards a higher level of belief in the absence of opposite voices. In social sciences, this behavior is in agreement with the so-called "reinforcement theory" according to which people do not like to change their opinions and are keen on recognizing cognitive support to their pre-existing beliefs.

Sometimes, when this does not lead to confusion, we write $ W(V) = (w_1, \dots, w_N) $ instead of $ W(V) = (w_1(V), \dots, w_N(V)) $.

Due to (1),

After that, we define

by "cutting" the elements of $ W(V) $ according to the rule

and

Obviously,

Note that if we replace in (2) $ v_l $ by $ v_l-v_k $ and take $ h = 1 $, then we get the HK model.

We want to study the fixed points of the operator $ \Phi $, and their stability.

3.   Dynamics of the opinion model

We start with an initial array $ V = V^0 $ with the following property:

This choice is without loss of generality because we can always arrange initial opinions in non-decreasing order and the dynamics described in the previous section does not depend on the order, it only depends on the values. In our case, an ordering reflecting the initial preferences of the voters seems to be the most convenient.

Let

First let us note some important properties of the operator $ \Phi $.

We need a simple technical statement (for its proof, see, for example, item (ⅰ) of Lemma 2 in [18]).

Lemma 3.1. If

then

Take an array $ V = (v_1, \dots, v_N) $ such that

and consider the "increments"

Lemma 3.2. The following inequalities hold:

Proof. Let $ J(v_k) = [a, a+l] $ with $ v_a\leq\dots\leq v_{a+l} $ and $ J(v_{k+1}) = [b, b+m] $ with $ v_b\leq\dots\leq v_{b+m} $. By formula (2),

and

If $ J(v_k)\cap J(v_{k+1}) = \emptyset $ (which is equivalent to the inequality $ a+l<b $), then (3) obviously holds.

Otherwise, let $ J(v_k)\cap J(v_{k+1}) = [b, a+l] $; it follows from Lemma 3.1 that

which completes the proof.

The following statements are more or less obvious but since we use them many times, we formulate them separately.

Applying induction on $ n $ based on Lemma 3.2, the following properties of $ V^n = \Phi^n(V^0) $ can be easily established.

Corollary 1. (a) Every array $ V^n $ is non-decreasing;

(b) If $ v^n_k = 1 $, then $ v^n_l = 1 $ for $ l>k $;

(c) If $ v^n_k = 1 $, then $ v^m_k = 1 $ for $ m>n $.

We do not explicitly formulate obvious analogs of items (b) and (c) for $ v^n_k = -1 $.

Let us explain a step of the induction in proving item (a) when we pass from $ n = 0 $ to $ n = 1 $ (the other steps are similar). Inequalities (3) for $ {\Delta}_k = w_k(V^0)-v_k^0 $ and the non-decreasing property of $ V^0 $ imply that the $ W(V^0) $ is non-decreasing; hence, $ V^1 $ is non-decreasing as well.

(b) follows from (a).

(c) If $ v^0_k = 1 $, then $ v^0_k $ is not influenced by negative $ v^0_l $ (since $ {\epsilon}<1 $); hence, $ w^1_k \geq 1 $ and $ v^1_k = 1 $.

We next move to consider fixed points of $ \Phi $. Recall that $ P\in \mathcal{V} $ is a fixed point of $ \Phi $ if $ \Phi(P) = P $.

First, we mention a class of fixed points which is important for us (as we show below, almost all positive trajectories of $ \Phi $ tend to such fixed points). Let $ P = (-1, -1, \dots, -1, 1, \dots, 1) $, where the first $ L $ entries equal $ -1 $ while the remaining equal $ 1 $. We do not exclude the cases of $ P = (-1, \dots, -1) $ (in which $ L = N $) and $ P = (1, \dots, 1) $ (in which we formally set $ L = 0 $). Any such $ P $ is a fixed point of $ \Phi $. This follows from item (c) of Corollary 1 (and its analog for $ v^n_k = -1 $).

Let us call any such $ P = (-1, -1, \dots, -1, 1, \dots, 1) $ a basic fixed point of $ \Phi $. We are going to show that any basic fixed point is asymptotically stable for $ \Phi $ (see Theorem 3.4).

Let us start with a simple statement which we often use below.

Lemma 3.3. If $ v_k^0\geq {\epsilon} $, then there exists an $ n_0\geq 0 $ such that $ v_k^n = 1 $ for $ n\geq n_0 $.

Proof. Condition $ v_k^0\geq {\epsilon} $ gives that $ v_k^0 $ is not influenced by negative $ v_l^0 $. On the other hand, $ k\in J(v_k) $ so that

If $ w_k(V^0)\geq 1 $, then $ v_k^1 = 1 $, and our statement follows from item (c) of Corollary 1. Otherwise,

and so on, which obviously implies our statement.

The same reasoning shows that if $ v_k^0\leq - {\epsilon} $, then there exists an $ n_0\geq 0 $ such that $ v_k^n = -1 $ for $ n\geq n_0 $.

Introduce the following metric on $ \mathcal{V} $: if

set

Theorem 3.4. Let $ P $ be a basic fixed point. If

then there exists an $ n_0 $ such that

Proof. Let $ V^0 = (v^0_1, \dots, v^0_N) $ satisfy inequality (4). Then

and our theorem follows from Lemma 3.3 since the number of components of $ V^0 $ is finite.

Remark 1. One can establish the convergence to basic fixed points under weaker conditions than (4). Assume, for example, that

and

Then the same reasoning as in Lemma 3.3 shows that $ \Phi^n(V^0) = P $ for some finite $ n $, where $ P $ is a basic point.

There exist fixed points that are not basic; we show below that they are unstable. A simple example of such a fixed point is as follows. Let $ N = 3 $; clearly, $ P = (p_1, p_2, p_3) = (-1, 0, 1) $ is a fixed point of $ \Phi $. We first describe all possible nonbasic fixed points of $ \Phi $.

Theorem 3.5. If $ P $ is a nonbasic fixed point of $ \Phi $, then either

or

where

and

Proof. It is clear that if $ P $ is a nonbasic fixed point that does not have form (5), then it has form (6) with $ p_a, \dots, p_l\in(-1, 0) $ and $ p_b, \dots, p_m\in(0, 1) $.

Inequalities (7) and (8) follow from Lemma 3.3.

Let us prove the remaining statements.

Since $ p_a<0 $ and $ P $ is a fixed point, $ p_a $ is influenced by positive $ p_i $ and it cannot be influenced by $ p_i = 1 $. Hence, there exists an index $ r(a)\in[b, m] $ such that either

or

Note that these cases are different only if $ a>1 $.

Since $ P $ is a fixed point,

in the first case and

in the second case.

It follows from (7) that any $ p_k $ with $ k\in[a, l] $ is influenced by $ p_a $.

Thus, if $ p_{a+1} < 0 $, then there exists an index $ r(a+1)\in[b, m] $ such that either

or

We claim that

● if $ a>1 $, then (11) implies (15);

● (12) implies (16);

● in both cases (15) and (16), $ r(a+1) = r(a) $.

To prove the first claim, we note that if $ a>1 $ and (11) holds, then

while if (16) holds, then

and

The second claim follows from the fact that if $ p_a $ is not influenced by $ p_i = -1 $, then $ p_{a+1}\geq p_a $ cannot be influenced by $ p_i = -1 $ as well.

To prove the third claim, we compare the equality

with (13) in the first case and the equality

with (14) in the second case and note that $ p_{r(a+1)} $ must be positive.

Continuing this process, we conclude that either $ J(p_k) = [1, r(k)] $ for all $ k\in[a, l] $ or $ J(p_k) = [a, r(k)] $ for all $ k\in[a, l] $, and, in both cases,

Clearly, this common value must be equal to $ m $ (since, otherwise, $ p_m $ is not influenced by negative $ p_i $, which is impossible for the fixed point $ P $).

In the second case, the equality $ r(a) = m $ implies (9), and equality (14) implies (10).

To complete the proof of the theorem, it remains to show that if $ a>1 $, then the first case is impossible.

To do this, let us start with $ p_m $ and "move in the opposite direction": find $ t(m)\in[a, l] $ such that $ J(p_m) = [t(m), N] $ or $ J(p_m) = [t(m), m] $, and so on.

Repeating the above reasoning, we get either the equality

or equality (10); both contradict the equality

obtained above.

Now we are going to prove that if $ P $ is a nonbasic fixed point of $ \Phi $, then $ P $ is unstable in a strong sense: $ P $ has a neighborhood $ U $ such that for any point $ V\in U $ not belonging to a subset of $ U $ of positive codimension, the trajectory $ \Phi^n(V) $ leaves $ U $ as $ n $ grows. The authors are grateful to A. Proskurnikov who have noticed this fact and suggested the idea of the proof of the following theorem.

Theorem 3.6. If $ P $ is a nonbasic fixed point of $ \Phi $ having form (5) or (6), then there exists a $ d>0 $ such that if

and

then for any point $ V\in U\setminus \Pi $ there exists an $ n>0 $ such that $ \Phi^n(V)\notin U $.

Proof. We impose several conditions on $ d $.

First, it follows from (7) and (8) that we can take $ d $ so small that if $ V\in U $, then

Second, condition (9) implies that if $ a\neq 1 $ (i.e., $ P $ has components equal to $ -1 $), then $ p_a $ is not influenced by these components (i.e., $ p_a+1> {\epsilon} $). Similarly, $ p_m $ is not influenced by components $ +1 $ (if they exist). Hence, we can take $ d $ so small that if $ V\in U $, then

Finally, we take $ d $ so small that

(recall that $ p_m>0 $ and $ p_a<0 $).

Denote

First we claim that if $ V\in U $ and

then $ \Phi(V)\notin U $.

Assume that $ s(V)\geq 0 $. It follows from (17) and (19) that $ J(v_m) = [k, m] $, where $ k\leq b $ (since $ v_m $ is influenced by all positive components of $ V $ with indices in $ [b, m] $).

If $ w_m(V)\geq 1 $, then $ v^1_m $ equals $ 1 $, and our claim follows from (17). Otherwise,

Since

(we take into account that $ s(V)\geq 0 $ and $ v_{a+1}, \dots, v_{k-1}\leq 0 $), it follows from the inequalities $ m-k+1\leq N $, $ v_a<p_a+d $, and (18) that

which is impossible if $ V \in U $ and $ \Phi(V)\in U $.

If $ s(V)<0 $, we apply a similar reasoning taking into account that relation (19) implies the relation $ J(v_a)\neq[a, m] $.

Now let us take a point $ V\in U $ and assume that $ \Phi^n(V)\in U $ for all $ n>0 $. It follows from our previous reasoning that in this case,

for all $ n $. Then, with the notation $ s_0 = s(v) $, we have

which yields

Similarly,

and so on.

If $ V\notin \Pi $, then $ s_0\neq 0 $, and the above value is unbounded as $ n\to\infty $, which is impossible since the values $ S(V) $ for $ V\in U $ are bounded.

This completes the proof.

Now we prove that if

then the trajectories of $ \Phi $ tend to fixed points.

Theorem 3.7. If condition (20) is satisfied, then any trajectory $ \Phi^n(V^0) $ tends to a fixed point of $ \Phi $ as $ n\to\infty $.

Proof. Corollary 1 implies that if $ v^n_k = -1 $, then $ v^m_l = -1 $ for $ m\geq n $ and $ l\leq k $; similarly, if $ v^n_k = 1 $, then $ v^m_l = 1 $ for $ m\geq n $ and $ l\geq k $.

Since the number of components of $ V^n = \Phi^n(V^0) $ is finite, we conclude that there exist integers $ 1\leq a<b\leq N $ and $ n_1\geq 0 $ such that if $ n\geq n_1 $, then

where

in words, the number of components equal to $ \pm 1 $ "stabilizes."

If the "middle" part $ (v^{n_1}_a, \dots, v^{n_1}_b) $ is absent, $ \Phi^{n_1}(V) $ is a fixed point, and our statement is proved.

To simplify further the notation, assume that $ n_1 = 0 $. Clearly, our problem is to describe the behavior of $ (v^n_a, \dots, v^n_b) $ as $ n $ grows.

It was shown in Lemma 3.3 that if $ |v^0_k|\geq {\epsilon} $ for some $ k\in[a, b] $, then $ |v^n_k| = 1 $ for large $ n $, which is impossible. Hence,

These inequalities and condition (20) imply that

It follows that the behavior of $ (v^n_a, \dots, v^n_b) $ is determined by components of $ V^n $ with indices from $ a $ to $ b $. Thus, without loss of generality, we may assume that we study the behavior of $ V^n $ with $ |v^n_k|< {\epsilon}, \;1\leq k\leq N, \quad n \geq 0 $.

Let

be the set of pairs $ (k, l) $ of indices such that $ v_k $ is not influenced by $ v_l $ et vice versa.

We prove the following simple but relevant statement separately.

Lemma 3.8.

Proof. Inclusion (22) means that if $ |v^n_k-v^n_l|> {\epsilon} $, then

as well.

Assume, for the sake of clarity, that $ v^n_k-v^n_l> {\epsilon} $ (the symmetric case is treated similarly). Then $ k>l $, and if we write

our statement follows from the inequality $ {\Delta}_k\geq {\Delta}_l $ (see Lemma 3.2) and from the equalities $ v^{n+1}_k = w_k(V^n) $ and $ v^{n+1}_l = w_l(V^n) $ (see inequalities (21)).

Thus, we get a nondecreasing sequence of subsets of $ [1, N]\times [1, N] $:

Since the set $ [1, N]\times [1, N] $ is finite, there exists an $ n_2 $ and a subset $ \mathcal{N}(V)^* $ of $ [1, N]\times [1, N] $ such that

We again assume that $ n_2 = 0 $ and consider the set

By construction, this set has the following property: for any $ n\geq 0 $, $ v^n_k $ and $ v^n_l $ influence each other if and only if

Hence,

Note that the set $ J(v^n_k) $ does not depend on $ n $; denote it $ J(k) $ and let $ I(k) $ be the cardinality of $ J(k) $.

It is clear that, for any $ k\in[1, N] $, the set $ J(k) $ has the form $ [k-\mu(k), k+\nu(k)] $, where $ \mu(k), \nu(k)\geq 0 $ and $ \nu(k)+\mu(k)+1 = I(k) $.

Introduce an $ N\times N $ matrix $ T $ as follows: $ t_{k, l} = 1/I(k) $ if $ (k, l)\in \mathcal{M} $ and $ t_{k, l} = 0 $ otherwise.

It follows from (23) that (note that we are studying the evolution of an array such that condition (21) holds, so that the truncation operator that defines $ \Phi(V) $ from $ W(V) $ does not apply and $ \Phi(V) = W(V) $)

where $ E_N $ is the unit $ N\times N $ matrix.

Hence,

Let us show that the spectrum of the matrix $ T $ is real.

Represent $ T = SU $, where $ S $ is a diagonal matrix with positive diagonal elements,

and entries $ u_{k, l} $ of $ U $ are as follows: $ u_{k, l} = 1 $ if $ (k, l)\in \mathcal{M} $ and $ u_{k, l} = 0 $ otherwise. Clearly, $ U $ is symmetric.

Then, $ T $ is conjugate to

but the last matrix is symmetric:

Hence, the spectrum of $ T = SU $ (and so the spectrum of $ E_N+hT $) is real.

The $ k $th row of the matrix $ T $ has the form

where the number of nozero entries is precisely $ I(k) $.

This means that $ T $ is stochastic. A classical result states that $ T $ has an eigenvalue 1 and all other eigenvalues $ \lambda $ satisfy the inequality $ |\lambda|\leq 1 $.

Hence, the eigenvalues of $ T $ are real and belong to $ [-1, 1] $, which, since $ h\in(0, 1) $, implies that the eigenvalues of $ E_N+hT $ are positive.

In this case, any bounded sequence $ V^n $ that satisfies (24) tends to a vector $ W $ such that $ W = (E_N+hT)W $. To show this, consider a Jordan form $ J $ of the matrix $ E_N+hT $:

where $ J_1, \dots, J_l $ are Jordan blocks.

Let us assume that $ J_1 $ is a $ d\times d $ block corresponding to an eigenvalue $ \lambda $ and $ d>1 $ (the case $ d = 1 $ is trivial), i.e.,

Let $ {k\choose j} $ be the binomial coefficients,

If $ k\geq d-1 $, then

Hence,

(where we have taken the liberty of using the same symbol $ v_i^0 $ to denote the components in the Jordan representation). It follows that if the sequence $ V^n $ is bounded and $ \lambda>1 $, then $ v^0_1 = \dots = v^0_d = 0 $.

If $ \lambda = 1 $, then $ v^0_2 = \dots = v^0_d = 0 $, and if we denote $ u = (v^0_1, 0, \dots, 0) $, then $ J_1^n u = u $ for all $ n\geq 0 $.

Finally, if $ \lambda<1 $, then $ v^n_1, \dots, v^n_d\to 0 $ as $ n\to\infty $.

Of course, similar statements hold for all Jordan blocks.

This implies that if the sequence $ V^n $ is bounded, then we can represent $ V^0 $ in the form $ W_1+W_2 $ such that $ (E_N+hT)W_1 = W_1 $ is a fixed point and $ (E_N+hT)^nW_2\to 0 $ as $ n\to\infty $. This completes the proof.

4.   Numerical examples

The first simulation illustrates a typical evolution of the opinions. Figure 1 gives the initial distribution and Figure 2 illustrates the evolution at steps $ 10 $, $ 20 $, $ 30 $ and $ 34 $, when the equilibrium is reached. Interestingly enough, for higher values of $ {\epsilon} $ than the value $ 0.3 $ used in this simulation, the same initial condition gives an evolution where the opinions' distribution transits through a state where the majority of the population has positive opinion before finally achieving an equilibrium where $ -1 $ is dominating.

The second example shows that the final outcome of an election process may change depending on the level of interaction of the society. This has the interesting interpretation that a society is a complex entity which cannot be reduced to the simple union of many individuals: beliefs in the society evolve differently depending on the quality and level of mutual influence, which in turn is highly dependent on technology and on the possible existence of rules that limit the circulation of information.

Figure 3 shows the initial distribution of opinions that was used in this test. When $ {\epsilon} = 0.45 $ (high level of interaction), Figure 4 shows the evolution at steps $ 5 $, $ 10 $, $ 20 $ and $ 27 $. At step $ 27 $ a clustering equilibrium is reached where option $ 1 $ achieves majority. Suppose now that the level of interaction is drastically reduced to the level $ {\epsilon} = 0.05 $. Figure 5 shows the evolution starting from the same initial distribution as before: the decreased level of interaction leads to an opposite result that option $ -1 $ now turns out to win the election.