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 has an opinion which is a vector in . The group of agents interact in some way, i.e., they meet at a time with their opinions , discuss and they adapt their opinions to each other which results in new opinions .
For a total number of agents, the dynamics reads as
In words: The option of the -th agent depends of all other opinions in a time dependent manner. In the following we stack the (row-)vectors of opinions into an matrix and may formulate more compactly .
There are several simplifications one can make:
- Time-independent models, i.e. does not depend on .
- Linear models: The function is linear in the first variables, i.e. there is a -matrix such that
- “Semi-linear” models where the matrix also depends of the present opinions:
The difference between “semi-linear” and non-linear models is in fact not that large. As soon as every vector is in the linear span of the previous vectors one can find a matrix (depending on , of course) auch that . 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 which ensure that the process converge to a consensus, i.e. to a state where all agents share the same opinion .
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 . Then, the agent is influenced by all agents in the set and takes the mean value of these agents as next opinion:
We can formulate this as a semi-linear model: Define the matrix as
Then the dynamics is
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 real number is a mapping which such that (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 vectors in look like? What should be the sandwich inequality? One natural idea is the following: is a generalized mean of is contained in the convex hull of the vectors , in formula: (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, is contained in the smallest cube (i.e. -dimensional interval) which contains all ‘s. We denote this by .
Now we know what a generalized mean could be:
Definition 1 An iteration map is called a cube averaging map if for all it holds that:
Of cource, it is not enough to have cube-averaging maps to get convergence to consensus of (since the identity is valid…). We strengthen the notion of averaging a little bit:
Definition 2 is a proper cube-averaging map if for all which are not a consensus (i.e. not all are equal) the inclusion
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 of compact sets we formulate:
Definition 3 A family of cube-averaging maps is called equi-proper, if for every which is not a consensus there is a such that for every it holds that
And still this is not enough to show convergence to consensus:
Example 2 We consider (one-dimensional opinions), (three agents) and only one averaging map (i.e. a time independent process):
A close inspection shows, that this is indeed a proper (cube-)averaging maps. However,if we start with a consensus will never be reached.
What is missing is continuity. And not only continuiuty, we need that the family is equicontinuous.
Theorem 4 If the maps form a family of equicontinuous and equiproper cube averaging maps, the solution of always converges to consensus.
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 is “approximated by ” which discards all effects which rely on the number itself.
First, let’s get back to Krause’s model and formulate it in “update form”:
with a bounded function which is also symmetric (). We assume that 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
but this gives a different weight to the own opinion:
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 there is a normalized (i.e. probability) measure which we take as a Borel measure of . Now we want to derive a dynamics for this measure which resembles the dynamics of (2).
Informally, the agents with opinion move to another place according to the update in (2), i.e. we have
(often this is written as ).
This is a valid generalization of (2):
Example 3 Consider an opinion distribution that is, there are agents with opinions . We calculate according to (4): For a Borel set we have
It holds that
Now we calculate accroding to (3) (note that the integral becomes a sum since it is with respect to a singular measure consisting of delta’s):
Hence, we have that iff (according to (2)) is in . We combine this with our previous finding and obtain
Theorem 5 Let be non-negative, bounded by and symmetric and let the initial Borel probability measure have finite second moment. Then the second moments of (according to (3) and (4)) are non-increasing in and the sequence converges in the weak- sense to some probability measure . If moreover there exist and such that for then is a purely atomic measure (i.e. a superposition of delta’s) and the atoms are at least 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 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 is a radial function and has radial symmetry with respect to then it holds that .
I.e. if the initial profile is symmetric around some then the dynamics will converge to a consensus in the point . Note that this result has no counterpart for finitely many agents since you can not put finitely many deltas in 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…