In my last post I treated a model for opinion dynamics. The specific feature of this model by Canuto, Fagnani and Tilli was that it is not based on a finite number of agents, each moving around in opinion space, but on the density of agents on the opinion space. On the one hand, this makes the “agents” somehow disappear in the model and especially, it is not possible to “track an individual agent” anymore (correct me, if I’m wrong). On the other hand, this “approximation by infinity” makes the analysis a bit easier.
In this post I’d like to collect similar equations for other related phenomena, namely flocking and synchronization.
1. Flocking dynamics
Some animals (as well as humans) build flocks and usually, this happens without a kind of leader. Flocks can be visually appealing, as you can see here or here. There are several mathematical models around to describe the leaderless formation of flocks.
One of the first flocking models is due to Vicsek at al. and a very popular one is more recent and due to Cucker and Smale: At time there are agents at positions with velocities and each agent moves according to its velocity and adapts its velocity in view of the velocities of its neighbors. The equations read like this:
In the second equation for the velocities, you recognize that the velocities of the th agent is a weighted mean of the velocities of the other agents and the weight for the th agent depends on their mutual distance.
For the continuous counterpart of this model, we need a density function of the phase space, that is a density function and describes “how many agents are at time at position with velocity ”. This is very similar to the famous Boltzmann equation from gas dynamics. The evolution of this density function according to the above model has been derived by Ha and Tadmor. With the operator
the model reads as
The term “” leads to the movement of the agent along the velocities, while the last term “” is the term which models the interaction of the velocities.
Another natural phenomenon where group behavior arises is that of synchronization. Different “oscillators” are mutually coupled and may evolve to a state in which all of them oscillate with the same frequency. This phenomenon is modelled by the Kuramoto equation: The state of the th oscillator at time is given by its phase (which is a real number but has to be considered modulo ). If an oscillator has natural frequency (or phase velocity), its phase evolves according to . Put differently, its phase satisfies the differential equation . The Kuromoto equation for coupled oscillators is
The coupling strength is given by and the coupling term says that an oscillator “slows down” if it sees some oscillators “behind him” and “speeds up” if it sees some “ahead of him”.
In the limit for we consider a distribution and described “how many oscillators at time have phase and natural frequency ”. Further, the distribution of natural frequencies is given by . Then, the equation for the evolution of the oscillators is
For more information, see the Wikipedia page or this article by Strogatz.
Finally, I’d like to mention another model for opinion formation, the model by Ben-Naim, Krapivsky and Redner: The density describes how many agents at time have the opinion and evolves according to
The model is derived from the Deffuant-Weisbuch model in which two randomly chosen agents meet in each step, and if their opinion is close enough to each other, they agree on their mean value.
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:
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.
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 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”:
In the paper by Canuto et al. they slightly deviate from Krause’s model. They consider the dynamics
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
Since describes how the density is moved, the dynamics of is described as the “push-forward” of by that is: For every Borel set 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
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 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…