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.

    Advertisements
    Post a comment or leave a trackback: Trackback URL.

    Leave a Reply

    Please log in using one of these methods to post your comment:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out / Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out / Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out / Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s

    %d bloggers like this: