It happened again that I found a paper that I would have liked to write myself. Actually, this is not too bad this time because I did not really started to work on the subject. The paper is “An Eulerian Approach to the Analysis of Krause’s Consensus Models” by Claudio Canuto, Fabio Fagnani and Paolo Tilli. Actually, my brother Jan did his PhD thesis on “Krause’s Consensus Model” together with Ulrich Krause himself. I got a little bit involved through discussions with Jan on analytic aspects of the consensus models and we even wrote a small note the topic.

The general theme of “consensus models” is, to model, simulate and analyze the process in which opinions evolve and especially describe the phenomenon that a consensus may or may not form.

1. A time discrete consensus model with finitely many agents

The abstraction to mathematics usually goes like this: Each agent {j} has an opinion {x_j} which is a vector in {{\mathbb R}^d}. The group of agents interact in some way, i.e., they meet at a time {t} with their opinions {x_j(t)}, discuss and they adapt their opinions to each other which results in new opinions {x_j(t+1)}.

For a total number of {n} agents, the dynamics reads as

\displaystyle x_j(t+1) = F_j(x_1(t),\dots,x_n(t),t).

In words: The option of the {j}-th agent depends of all other opinions in a time dependent manner. In the following we stack the {n} (row-)vectors of opinions into an {n\times d} matrix {x(t)} and may formulate more compactly {x(t+1) = F(x(t),t)}.

There are several simplifications one can make:

  • Time-independent models, i.e. {F} does not depend on {t}.
  • Linear models: The function {F} is linear in the first {n} variables, i.e. there is a {n\times n}-matrix {A(t)} such that

    \displaystyle x(t+1) = A(t)x(t).

  • “Semi-linear” models where the matrix also depends of the present opinions:

    \displaystyle x(t+1) = A(x(t),t)x(t).

    The difference between “semi-linear” and non-linear models is in fact not that large. As soon as every vector {x_j(t+1)} is in the linear span of the previous vectors {x_1(t),\dots,x_n(t)} one can find a matrix {A} (depending on {x(t)}, of course) auch that {x(t+1) = Ax(t)}. However, the semi-linear view is sometimes useful when one tries to formulate conditions on the process which imply some wanted properties.

One special goal in opinion dynamics is, to find conditions of the mappings {F} which ensure that the process converge to a consensus, i.e. to a state where all agents share the same opinion {x_1 = \cdots = x_n}.

Example 1 (Krause’s model) Krause’s model for opinion dynamics say’s that in each step, each agent forms an average of the opinions of other agents if their opinion is not too far away (one also say’s that the agent have bounded confidence). Put in formula, the models needs a confidence bound {R>0}. Then, the agent {j} is influenced by all agents in the set {I_j(t) = \{i\ |\ \|x_j(t) - x_i(t)\|\leq R\}} and takes the mean value of these agents as next opinion:

\displaystyle x_j(t+1) = \frac{1}{|I_j(t)|}\sum_{i\in I_j(t)} x_i(t). \ \ \ \ \ (1)

We can formulate this as a semi-linear model: Define the matrix {A(x(t))} as

\displaystyle A(x(t))_{i,j} = \begin{cases} \frac{1}{|I_j(t)|} & \text{ if } \|x_j(t) - x_i(t)\|\leq R\\ 0 & \text{ else.} \end{cases}

Then the dynamics is

\displaystyle x(t+1) = A(x(t))x(t)

It turned out that it is quite difficult to analyze this model properly. One specific difficulty is that the “communication topology” keeps changing over time. Especially, it seems quite hard to analyze under which circumstances the system converges to a consensus.

Together with Jan we proved a theorem about non-linear models which uses a very general notion of “average” or “mean”.

A “generalized mean” of {n} real number is a mapping {g:{\mathbb R}^n\rightarrow{\mathbb R}} which such that {\min x^i \leq g(x)\leq\ max x^i} (which is called “sandwich inequality”). Of course the usual arithmetic mean, the geometric mean and so on are genealized means in this sense. But how would a generalied mean of {n} vectors in {{\mathbb R}^d} look like? What should be the sandwich inequality? One natural idea is the following: {g:({\mathbb R}^d)^n\rightarrow{\mathbb R}^d} is a generalized mean of {g(x)} is contained in the convex hull of the vectors {x^1,\dots,x^n}, in formula: {g(x)\in\text{conv}(x^1,\dots,x^n)} (could be called the “convex-hull sandwich inclusion”). However, then the “componentwise geometric mean” is not a generalized mean… Hence, it seems more appropriate to use the notion of “cube mean”, that is, {g(x)} is contained in the smallest cube (i.e. {d}-dimensional interval) which contains all {x^i}‘s. We denote this by {g(x)\in\text{cube}(x^1,\dots,x^n)}.

Now we know what a generalized mean could be:

Definition 1 An iteration map {F:({\mathbb R}^d)^n\rightarrow({\mathbb R}^d)^n} is called a cube averaging map if for all {x} it holds that:

\displaystyle \textup{cube}(f^1(x),\dots,f^n(x)) \subset \textup{cube}(x^1,\dots,x^n).

Of cource, it is not enough to have cube-averaging maps {F(\cdot,t)} to get convergence to consensus of {x(t+1) = F(x(t),t)} (since the identity is valid…). We strengthen the notion of averaging a little bit:

Definition 2 {F} is a proper cube-averaging map if for all {x = (x^1,\dots,x^n)} which are not a consensus (i.e. not all {x^i} are equal) the inclusion

\displaystyle \textup{cube}(f^1(x),\dots,f^n(x)) \subset \textup{cube}(x^1,\dots,x^n).

is strict.

However, this notion is still not enough: It may happen that the “cube-hulls” shrink too slow, i.e. the decrease of the cube-hull slows down so much that it will not shrink to a single point. Hence we strengthen a little bit more. With the help of the Hausdorff distance {d_H} of compact sets we formulate:

Definition 3 A family {\mathcal{F}} of cube-averaging maps is called equi-proper, if for every {x} which is not a consensus there is a {\delta>0} such that for every {F\in\mathcal{F}} it holds that

\displaystyle d_H(\textup{cube}((f^1(x),\dots,f^n(x)), \textup{cube}(x^1,\dots,x^n))>\delta

And still this is not enough to show convergence to consensus:

Example 2 We consider {d=1} (one-dimensional opinions), {n=3} (three agents) and only one averaging map (i.e. a time independent process):

\displaystyle f(x^1,x^2) =\left\{ \begin{array}{cl} (x^1,x^2,\frac{1}{2}x^3 + \frac{1}{2}\min\{x^1,x^2\}) &\hbox{ if } x^3<\min\{x^1,x^2\} ,\\ (x^1,x^1,x^1) & \hbox{ otherwise. } \end{array} \right.

A close inspection shows, that this is indeed a proper (cube-)averaging maps. However,if we start with {x_3<\min(x_1,x_2)} a consensus will never be reached.

What is missing is continuity. And not only continuiuty, we need that the family {F(\cdot,t)} is equicontinuous.

Theorem 4 If the maps {F(\cdot,t)} form a family of equicontinuous and equiproper cube averaging maps, the solution of {x(t+1) = F(x(t),t)} always converges to consensus.

The (technical) proof, a generalization, more examples and counterexample can be found in our paper “On conditions for convergence to consensus” (or the preprint version).

In general, Krause’s model is not covered by the above theorem, however, one could adapt the theorem to this situation and deduce a bit more.

2. The model of Canuto et al.

Canuto et al. want to analyze Krause’s model in the limit of infinitely many agents. Often this limit allows for a more detailed analysis, since the quite arbitrary large number {n} is “approximated by {\infty}” which discards all effects which rely on the number {n} itself.

First, let’s get back to Krause’s model and formulate it in “update form”:

\displaystyle x_j(t+1) = x_j(t) + \sum_{i}A(x(t))_{ij}(x_i(t) - x_j(t))

In the paper by Canuto et al. they slightly deviate from Krause’s model. They consider the dynamics

\displaystyle x_j(t+1) = x_j(t) + \frac{1}{n}\sum_{i=1}^n \xi(x_i(t) - x_j(t))\, (x_i(t) - x_j(t)) \ \ \ \ \ (2)

with a bounded function {\xi} which is also symmetric ({\xi(x) = \xi(-x)}). We assume that {\xi} is non-negative and bounded by one. The non-negativity says, that other opinions do not contribute negatively to the average (which would mean that one agent actually distrusts another agent so strongly that he moves away from him). The symmetry says that confidence is mutual.

Note that Krause’s model (1) can not be modelled like this: One can get close by setting

\displaystyle \xi(x) = \begin{cases} 1, & \|x\|\leq R\\ 0, & \text{ else} \end{cases}

but this gives a different weight to the own opinion:

\displaystyle \begin{array}{rcl} x_j(t+1) &=& x_j(t) + \frac{1}{n}\sum_i \xi(x_i(t) - x_j(t))\, (x_i(t) - x_j(t))\\ & =& \Big(1 - \frac{1}{n}\sum_{i=1}^n \xi(x_i(t) - x_j(t))\Big) x_j(t) + \frac{1}{n}\sum_{i=1}^n \xi(x_i(t) - x_j(t))\, x_i(t)\\ & = & \sum_{i=1}^n\tilde A(x(t))_{i,j} x_i(t) \end{array}

with

\displaystyle \tilde A(x(t))_{i,j} = \begin{cases} \frac1n & \text{ if } \|x_i(t) - x_j(t)\|\leq R, \text{ and } i\neq j\\ 1 - \frac{|I_j(t)|}{n} & i=j\\ 0 & \text{ else.} \end{cases}

In other words: The modified model of Canuto et al. gives a larger weight to the own opinion.

3. A time discrete consensus model with “infinitely” many agents

Now we want to go to infinitely many agents. Canuto et al. suggest not to assume to have a countably infinite number of agent but that we identify the set of agents and their opinions by their distribution of opinions. In mathematical terms: We consider a measure on the set of possible opinions: At each time {t} there is a normalized (i.e. probability) measure {\mu_t} which we take as a Borel measure of {{\mathbb R}^d}. Now we want to derive a dynamics for this measure which resembles the dynamics of (2).

Informally, the agents with opinion {x} move to another place {\gamma_t(x)} according to the update in (2), i.e. we have

\displaystyle \gamma_t(x) = x + \int_{{\mathbb R}^d}(y-x)\xi(y-x)d\mu_t(y). \ \ \ \ \ (3)

Since {\gamma_t} describes how the density is moved, the dynamics of {\mu_t} is described as the “push-forward” of {\mu_t} by {\gamma_t} that is: For every Borel set {E} we have

\displaystyle \mu_{t+1}(E) = \mu_t(\gamma_t^{-1}(E)) \ \ \ \ \ (4)

(often this is written as {\mu_{t+1} = \gamma_t\# \mu_t}).

This is a valid generalization of (2):

Example 3 Consider an opinion distribution {\mu_t = \frac{1}{n}\sum_{j=1}^n \delta_{x_j(t)}} that is, there are {n} agents with opinions {x_j(t)}. We calculate {\mu_{t+1}} according to (4): For a Borel set {E} we have

\displaystyle \begin{array}{rcl} \mu_{t+1}(E) & = & \mu_t(\gamma_t^{-1}(E))\\ & = & \frac1n \sum_j \delta_{x_j(t)}(\gamma_t^{-1}(E)). \end{array}

It holds that

\displaystyle \delta_{x_j(t)}(\gamma_t^{-1}(E)) = \begin{cases} 1 & \text{ if } \gamma_t(x_j(t))\in E\\ 0 & \text{ else.} \end{cases}

Now we calculate {\gamma_t(x_j(t))} accroding to (3) (note that the integral becomes a sum since it is with respect to a singular measure consisting of {n} delta’s):

\displaystyle \gamma_t(x_j(t)) = x + \frac1n\sum_i (x_i(t) -x_j(t))\,\xi(x_i(t) - x_j(t)).

Hence, we have that {\gamma_t(x_j(t))\in E} iff {x_j(t+1)} (according to (2)) is in {E}. We combine this with our previous finding and obtain

\displaystyle \mu_{t+1}(E) = \frac1n\sum_j \delta_{x_j(t+1)}(E).

I found that pretty neat. Now Canuto et al. prove a few results about the dynamics of (3) and (4) which I quote without proof:

Theorem 5 Let {\xi} be non-negative, bounded by {1} and symmetric and let the initial Borel probability measure {\mu_0} have finite second moment. Then the second moments of {\mu_t} (according to (3) and (4)) are non-increasing in {t} and the sequence {\mu_t} converges in the weak-{*} sense to some probability measure {\mu_\infty}. If moreover there exist {R>0} and {\delta>0} such that {\xi(x)>\delta} for {\|x\|\leq R} then {\mu_\infty} is a purely atomic measure (i.e. a superposition of delta’s) and the atoms are at least {R} apart from each other.

In words: The system always converges to a state in which the opinions are clustered at points which are at least {R} apart. If the initial condition has a bounded support, we can conclude that in the limit there are only finitely many opinions left.

By investigating symmetry-perserving properties of the dynamics, Canuto et. al obtain the following intersting side-result:

Corollary 6 If {\xi} is a radial function and {\mu_0} has radial symmetry with respect to {x_0} then it holds that {\mu_\infty = \delta_{x_0}}.

I.e. if the initial profile is symmetric around some {x_0} then the dynamics will converge to a consensus in the point {x_0}. Note that this result has no counterpart for finitely many agents since you can not put finitely many deltas in {{\mathbb R}^d} in a radially symmetric way…

Canuto et al. also derive a numerical scheme for their modell and maybe I’ll blog about this in the future…