AN IMPROVED ENERGY ARGUMENT FOR THE HEGSELMANN-KRAUSE MODEL ANDERSMARTINSSON Abstract. Weshowthatthefreezingtimeofthed-dimensionalHegselmann- KrausemodelisO(n4) wherenisthenumberofagents. Thisimproves thebest known upperboundwheneverd≥2. 5 1 0 2 1. Introduction n a The Hegselmann-Krause bounded confidence model, or simply the HK- J model, is a simple model for opinion dynamics, first introduced in [1] and 9 popularizedin[2]. Inthismodel,weconsidernagents,indexedbyintegersin ] [n] = {1,2,...,n}. Each agent i initially has the opinion x (i), represented Y 0 byavectorinV =Rd forsomed ≥ 1. Twoagentsconsidereachothersopin- S ions reasonable if their Euclidean distanceis at most aconstant ε, called the . s confidence radius. The agents update their opinions synchronously in dis- c [ cretetimestepsbycompromisingwithallopinionstheyconsiderreasonable. 1 More precisely, for each t = 0,1,... we recursively define v 1 3 (1.1) x (i) = x (j). 8 t+1 |Nt(i)| X t 1 j∈Nt(i) 2 where N (i) = {j ∈ [n] : kx (i)−x (j)k ≤ ε}. We will refer to (1.1) as the t t t 2 0 HK update rule. In this paper we will always assume that ε= 1. . 1 Arguably, the most fundamental result about the HK-model is that, for 0 any initial configuration, the system freezes after a finite number of time 5 1 steps. That is, for sufficiently large T we have that xT = xt for any t ≥ T. : We will refer to the smallest such T as the freezing time of the system, and v Xi let Td(n) denote the maximal freezing time of any configuration of n agents with d-dimensional opinions. r a In [3] it is shown that, for any d, Td(n) = nO(n) and is furtherconjectured that T (n) grows polynomially in n. In dimension one, this was first shown d in [4] who proved that T (n) = O(n5). This has later been improved to 1 T (n) = O(n3) in [5], see also [6,7]. Polynomial freezing time in arbitrary 1 dimension was shown in [5], which obtains the bound T (n) = O(n10d2). As d opinions will always be contained in the affine space spanned by the initial opinions, we may assume that d ≤ n − 1. Hence, this implies a uniform upper bound of T (n) = O(n12) independentof d. In a recent paper [8], this d was improved to T (n)= O(n8). d Theproblem of findinglower boundson T (n) has received less attention. d In [5] it was noted that it is possible to obtain freezing times of order n2 2010 Mathematics Subject Classification. 93A14, 39A60, 91D10. Key words and phrases. Hegselmann-Krause model, energy,freezing time. 1 2 ANDERSMARTINSSON for any d ≥ 2 by placing opinions equidistantly on a circle. More recently, [9] shows that a certain “dumbbell”configuration achieves freezing time of order n2 also in d= 1. Theaimofthispaperistoprovethefollowingupperboundonthefreezing time. Theorem 1.1. The maximal freezing time for the n-agent HK model in any dimension is O(n4). 2. Proof of Theorem 1.1 For a given sequence {x } ∈ Vn, we define the communication graph G t t as the graph with vertex set [n] and where i and j are connected by an edge if kx (i)−x (j)k ≤ 1. Note that all vertices in G have an edge going to t t 2 t themselves. We will here write i ∼ j to denote that i is adjacent to j in G . t t We further let P denote the transition matrix for a simple random walk on t G . Hence, if we think of x as a n×d matrix, we can formulate the HK t t dynamics as (2.1) x = P x . t+1 t t For a configuration x = (x(1),x(2),...,x(n)) ∈ Vn of n agents, we define its energy as n n (2.2) E(x) = min kx(i)−x(j)k2,1 . XX (cid:8) 2 (cid:9) i=1 j=1 Notethattheenergy ofanyconfigurationliesbetween0andn2. Let{x }be t a sequence in Vn which satisfies (1.1). This energy function has the impor- tant property that E(x ) is non-increasing in t. The following inequality has t played a central roll in obtaining the upper bounds on the high-dimensional freezing time in [5,8]. Proposition 2.1. (2.3) E(x )−E(x )≥ 4kx −x k2. t t+1 t+1 t 2 Proof. See Theorem 2 in [10]. (cid:3) Here, we propose another way to estimate the energy decrement in a step in the HK-model. For a given state x and for any ordered pair (i,j) ∈ [n]2, we say that (i,j) is active if kx(i)−x(j)k ≤ 1. We consequently define the 2 active part of the energy of x as (2.4) E (x) = kx(i)−x(j)k2 active X 2 (i,j)active Proposition 2.2. For each t ≥ 0, let (2.5) λ =max{|λ|: λ 6= 1 is an eigenvalue of P }. t t Then (2.6) E(x )−E(x ) ≥ 1−λ2 E (x ). t t+1 (cid:0) t(cid:1) active t AN IMPROVED ENERGY ARGUMENT FOR THE HEGSELMANN-KRAUSE MODEL 3 Proof. Let A denote the adjacency matrix of G , and let D denote its t t t degree matrix, that is, the diagonal matrix whose (i,i):th element is given by the degree of i. Recall that every vertex in G has an edge to itself. t Observe that P = D−1A . We have t t t E(x ) = kx (i)−x (j)k2 + 1 t X t t 2 X i∼tj i6∼tj = 2Tr x⊤(D −A )x + 1, (cid:16) t t t t(cid:17) X i6∼tj where Tr(·) denotes trace. Here, we again interpret x as an n×d matrix. t Similarly, we have E (x )= kx (i)−x (j)k2 = 2Tr x⊤(D −A )x , active t X t t 2 (cid:16) t t t t(cid:17) i∼tj and E(x ) = kx (i)−x (j)k2 + 1 t+1 X t+1 t+1 2 X i∼t+1j i6∼t+1j ≤ kx (i)−x (j)k2 + 1 X t+1 t+1 2 X i∼tj i6∼tj = 2Tr x⊤ (D −A )x + 1 (cid:16) t+1 t t t+1(cid:17) X i6∼tj = 2Tr x⊤A D−1(D −A )D−1A x + 1. (cid:16) t t t t t t t t(cid:17) X i6∼tj Hence, it suffices to show that (2.7) Tr x⊤A D−1(D −A )D−1A x ≤ λ2Tr x⊤(D −A )x . (cid:16) t t t t t t t t(cid:17) t (cid:16) t t t t(cid:17) 1/2 1/2 −1/2 −1/2 −1/2 Let y = D x and B = D P D = D A D . It is straight- t t t t t t t t t t forward to show that (2.7) simplifies to (2.8) Tr y⊤B (I −B )B y ≤ λ2Tr y⊤(I −B )y . (cid:16) t t t t t(cid:17) t (cid:16) t t t(cid:17) When d= 1, this inequality follows bystandardlinear algebra: writey as a t linear combination of eigenvectors of B and observe that B is a symmetric t t matrix which is similar to P . For the case when d≥ 2, let e ,...,e denote t 1 d the standard basis of V. We can rewrite (2.7) as d d (2.9) (y e )⊤B (I −B )B y e ≤ λ2 y⊤e (I −B )y e . X t i t t t t i X t (cid:16) t i(cid:17) t t i i=1 i=1 By the one-dimensional case, we know that this inequality holds term-wise. (cid:3) Proposition 2.3. For any t ≥ 0, we have 1 (2.10) |λ | ≤ 1− t n2diam(G ) t 4 ANDERSMARTINSSON where diam(G ) denotes the graph diameter of G . If G is not connected, t t t we interpret diam(G ) as the largest diameter of any connected component t of G . t Proof. See for instance Corollary 13.24 in [11]. Note that it suffices to con- sider the case where G is connected. (cid:3) t Proof of Theorem 1.1 . We call a time t = 0,1,... a merging time if two agents with different opinions at time t move to the same opinion at time t+1. As merges are irreversible, there can at most be n−1 such times. Assume that t < T is not a merging time. Then diam(G ) ≥ 2. Observe t that for any i,j ∈ [n], every second edge in a minimal path from i to j must have length at least 1, hence E (x ) = Ω(diam(G )). Applying 2 active t t Proposition 2.2, it follows that the energy decrement in this step is Ω 1 , (cid:0)n2(cid:1) and can hence occur at most O(n4) times. (cid:3) Remark 2.4. The energy argument presented here is optimal in the sense that there are configurations where the energy decrement is of order 1 . In n2 particular, for the dumbbell in [9], this is the case during the first Θ(n2) time steps until the communication graph changes. Acknowledgements TheauthorwouldliketothankPeterHegartyandEdvinWedinforhelpful discussions. References [1] U. Krause, Soziale Dynamiken mit vielen Interakteuren, eine Problemskizze, Mod- ellierung und Simulation von Dynamiken mit vielen interagierenden Akteuren (U. Krauseand M. St¨ockler, eds.), Universit¨at Bremen, 1997. [2] R. Hegselmann and U. Krause, Opinion dynamics and bounded confidence: mod- els, analysis and simulations, Journal of Artificial Societies and Social Simulation 5(2002), no. 3. [3] B.Chazelle,Thetotal s-energy ofamultiagentsystem,SIAMJournalonControland Optimization 49, no. 4, 1680–1706. [4] S. Martinez, F. Bullo, J. Cortes, and E. Frazzoli, On Synchronous Robotic Networks - Part II:TimeComplexity of Rendezvous and Deployment Algorithms,IEEETrans. Automat.Control 52 (2007), no.12, 2214–2226. [5] A.Bhattacharya,M.Braverman,B.Chazelle,andH.L.Nguyen,OntheConvergence ofthe Hegselmann-Krause System,Proceedingsofthe4thConferenceonInnovations inTheoreticalComputerScience,2013,pp.61–66,DOI10.1145/2422436.2422446, (to appearin print). [6] S.MohajerandB.Touri,OnconvergencerateofscalarHegselmann-Krausedynamics, available at http://arxiv.org/pdf/1211.4189v1.pdf. [7] B. Touri and A. Nedic, Discrete-time opinion dynamics., In Signals, Systems and Computers(ASILOMAR),2011 Conference Record of theFortyFifth Asilomar Con- ference, 2011, pp.1172–1176. [8] S. R. Etesami and T. Basar, Game-Theoretic Analysis of the Hegselmann- Krause Model for Opinion Dynamics in Finite Dimensions, available at http://arxiv.org/pdf/1412.6546v1.pdf. [9] E. Wedin and P. Hegarty, A Quadratic Lower Bound for the Convergence Rate in the One-Dimensional Hegselmann-Krause Bounded Confidence Dynamics, Discrete & Computational Geometry, posted on 2015, 1-9, DOI 10.1007/s00454-014-9657-7, (toappear in print). AN IMPROVED ENERGY ARGUMENT FOR THE HEGSELMANN-KRAUSE MODEL 5 [10] M. Roozbehani, A. Megretski, and E. Frazzoli, Lyapunov analysis of quadratically symmetric neighborhood consensus algorithms, CDC, 2008, pp.2252–2257. [11] D.A.Levin,Y.Peres,andE.L.Wilmer,Markovchainsandmixingtimes,American MathematicalSociety,Providence,RI,2009. WithachapterbyJamesG.Proppand DavidB. Wilson. MR2466937 (2010c:60209) Department of Mathematical Sciences, Chalmers University Of Technol- ogy and University of Gothenburg, 41296 Gothenburg, Sweden E-mail address: [email protected]