Hegselmann-Krause system

There is an interesting preprint today on arxiv by Sascha Kurz:
How long does it take to consensus in the Hegselmann-Krause model? http://arxiv.org/abs/1405.5757

Consider $k$-particle system with total energy $E$, and let $\delta=\delta(E)$ be the range of interactions. The evolution of energy distribution $x=(x_i):\mathbb{N}\to \mathbb{R}^k$ is defined by the following algorithm:

1. set the initial energies $x_i(0)\ge 0$ with $E=\sum_{i} x_i(0)$.
2. as time develops, $x_i$ interacts (i.e. exchanges energy) only with the particles with similar energies: let $N_i(0)=\{1\le j\le k: |x_j(0)-x_i(0)|\le \delta\}\ni i$ and $n_i(0)=|N_i(0)|\ge 1$. Then set $x_i(1)=\frac{1}{n_i(0)}\sum_{j\in N_i(0)}x_j(0)$.
3. Suppose we have defined $x_i(n)$. Then let $N_i(n)=\{1\le j\le k: |x_j(n)-x_i(n)|\le 1\}\ni i$ and $n_i(n)=|N_i(n)|\ge 1$. Then set $x_i(n+1)=\frac{1}{n_i(n)}\sum_{j\in N_i(n)}x_j(n)$.
• Note that the total energy $E$ is preserved, and the system is scaling invariant. So we can assume $\delta=1$. Then the system can be viewed as a map on the simplex $\Delta_k=\{x=(x_i)\in\mathbb{R}^k:x_i\ge0\text{ and }E=\sum_i x_i\}$.
• Note that the order is preserved during the process: $x_i(0)\le x_{i+1}(0)$ implies $x_i(n)\le x_{i+1}(n)$ for all $n$. In particular, if $x_i(n)= x_{i+1}(n)$ for some $n$, then these two particles are identical in the system. So we can replace them by a single particle but with weight $2$. In general we can consider the weighted system $\Omega_k=\{(x_i,k_i):x_i\ge0, k=\sum_i k_i\text{ and }E=\sum_i k_ix_i\}$ (mass conservation and energy conservation). How to characterize the dynamics on $\Omega_k$?
• A simple test example is $x_i(0)=i$ for $i=1,\cdots k$.

1. $k=1$: trivial system.
2. $k=2$: $x_1(0)=1$ and $x_2(0)=2$. Then $x_i(n)=1.5$ for all $i=1,2$ and all $n\ge 1$. All $x_i(n)$ reach the same energy at time $T(2)=1$.
3. $k=3$: $x_i(0)=i$. Then $x_1(1)=1.5$, $x_2(1)=2$ and $x_3(1)=2.5$. Now note that $N_i(1)=\{1,2,3\}$ for all $i$. So $x_1(n)=2$ for all $i=1,2$ and all $n\ge 2$. Then reach the same energy at time $T(3)=2$.

The set $N_i(n)$ plays an important role. One can check that $T(4)=5$ and $T(5)=6$: the small groups can always reach the same energy. But the case $k=6$ is different:

• $X(0)=\langle 1,2,3,4,5,6 \rangle$
• $X(1)=\langle \frac{3}{2},2,3,4,5,\frac{11}{2} \rangle$
• $X(2)=\langle 1\frac{3}{4},2\frac{1}{6},3,4,4\frac{5}{6},5\frac{1}{4} \rangle$
• $X(3)=\langle 1\frac{23}{24},2\frac{11}{36},3\frac{1}{18},3\frac{17}{18},4\frac{25}{36},5\frac{1}{24} \rangle$
• Eventually this leads to two different clusters $x_i(6)=A$ for $i=1,2,3$ and $x_i(6)=B$ for $i=4,5,6$ with large energy difference $B-A > 1$. The two groups of particles never intersect with the other group and will stay in this status forever. So we set $T(6)=6$.

There is no general formula for $T(k)$. It is proved that $T(k)=O(k^3)$, and conjectured that $T(k)=O(k)$, and the worse scenario is given the initial data $x_i(0)=i$ for $i=1,\cdots, k$.