The Continuous-Time Weighted-Median Opinion Dynamics
Yi Han Ge Chen Florian Dörfler Wenjun Mei







The Continuous-Time Weighted-Median Opinion Dynamics
    1st Yi Han
Dept. of Mechanics and Engineering Science 

Peking University

Beijing, China 

han_yi@stu.pku.edu.cn
2nd Ge Chen
Academy of Mathematics and Systems Science 

Chinese Academy of Sciences

Beijing, China 

chenge@amss.ac.cn
3rd Florian Dörfler
Automatic Control Laboratory 

ETH Zurich

 Zurich, Switzerland 

dorfler@ethz.ch
4th Wenjun Mei
Dept. of Mechanics and Engineering Science 

Peking University

Beijing, China 

mei@pku.edu.cn

    
====================================================================================================================================================================================================================================================================================================================================================================================================================================================================




Opinion dynamics models are important in understanding and predicting opinion formation processes within social groups. Although the weighted-averaging opinion-update mechanism is widely adopted as the micro-foundation of opinion dynamics, it bears a non-negligibly unrealistic implication: opinion attractiveness increases with opinion distance. Recently, the weighted-median mechanism has been proposed as a new microscopic mechanism of opinion exchange. Numerous advancements have been achieved regarding this new micro-foundation, from theoretical analysis to empirical validation, in a discrete-time asynchronous setup. However, the original discrete-time weighted-median model does not allow for "compromise behavior" in opinion exchanges, i.e., no intermediate opinions are created between disagreeing agents. To resolve this problem, this paper propose a novel continuous-time weighted-median opinion dynamics model, in which agents' opinions move towards the weighted-medians of their out-neighbors' opinions. It turns out that the proof methods for the original discrete-time asynchronous model are no longer applicable to the analysis of the continuous-time model. In this paper, we first establish the existence and uniqueness of the solution to the continuous-time weighted-median opinion dynamics by showing that the weighted-median mapping is contractive on any graph. We also characterize the set of all the equilibria. Then, by leveraging a new LaSalle invariance principle argument, we prove the convergence of the continuous-time weighted-median model for any initial condition and derive a necessary and sufficient condition for the convergence to consensus.





Social Networks, Opinion Dynamics, Weighted Median, Consensus




§ INTRODUCTION



 §.§ Background and Motivations

Opinion dynamics focus on how opinions form, evolve, and stabilize within a group through interactions among individuals. Opinion dynamics also examine the roles of social structure, decision-making processes, and individual interactions, revealing complex patterns of how opinions evolve in these environments. 


As the foundation of dynamic analysis, diverse mathematical models are proposed to understand how individual opinions lead to collective outcomes. The French-DeGroot model is a cornerstone in the study of opinion dynamic models and sets up a framework that incorporates a weighted-averaging mechanism into the opinion updating rules<cit.>. Based on the weighted-averaging mechanism, numerous discrete- and continuous-time models have been developed and thoroughly examined<cit.>. However, the weighted-averaging mechanism is criticized for its unrealistic implication regarding the unreasonable attractiveness of distant opinions, and is challenged as a wildly-adopted foundation<cit.>.



Recently, a new micro-foundation of opinion dynamics, i.e. the weighted-median mechanism, has been developed from theoretical formulations to empirical validations, offering much more realistic insights compared to traditional weighted-averaging methods<cit.>. The weighted-median mechanism updates individual opinions based on the weighted median of neighbours' opinions, and is supported by the psychological theory of cognitive dissonance<cit.>. This method has shown through empirical validation and numerical comparisons to more accurately predict opinion shifts and capture complex real-world opinion dynamics, such as the impact of group size and network structure on consensus formation. Recent research also analyses the dynamical behaviour of discrete-time weighted-median opinion dynamics rigorously including fully characterizing the equilibria set and establishing the almost-sure convergence for any initial condition<cit.>. Moreover, a necessary and sufficient condition for the almost-sure convergence to consensus is given, as well as a sufficient condition for almost-sure dissensus.


The original weighted-median opinion dynamics models are implemented in discrete-time settings, where each individual selects an opinion from either his or his neighbours' opinions at each step. This selection mechanism ensures that no new opinions are generated during the evolution of opinions,  facilitating the analysis of opinion shifts within an unchanging set of opinion options. However, in the real world, individuals often compromise in opinions, i.e. individuals adjust their opinions towards opinions that don't fully align with any single one's initial opinion but reflect a blend. Thus, a new opinion dynamics model is motivated to achieve the compromise of opinions under the weighted-median mechanism.





 §.§ Literature Review

The modelling of opinion behaviour has been a prominent research topic for approximately 70 years, attracting interest from various fields including sociology, economics, mathematics, physics and control theory. In this section, we will provide a brief review of classic opinion dynamics models as well as their variants. For more comprehensive and advanced surveys on opinion dynamic models, please refer to <cit.> and <cit.>. 


By the domain of opinion value, opinion dynamics models can be classified into discrete opinions models, where opinions take only finitely many values like {0,1}, and continuous opinion models, where opinions take values in a closed real interval like [0, 1]<cit.>.


The threshold model, originally proposed by Granovetter<cit.> and Schelling<cit.>, serves as a classic mechanism for understanding discrete opinion dynamics. It operates on a binary system where opinions are represented as 0 and 1, corresponding to "no" and "yes" in practical scenarios. The threshold model is based on the idea that individuals have a personal threshold for adopting a different opinion, which is influenced by the proportion of others in their neighbours who have already adopted that opinion. The ultimate or "equilibrium" number adopted by each opinion can be characterized by a frequency distribution of thresholds<cit.>.


The voter model, another classic discrete opinion dynamics model, is proposed by Clifford and Sudbury to analyze species' competitions for territory<cit.> and was further analyzed by Holley and Liggett<cit.>. Clifford and Sudbury described a stochastic 'swapping process' in which two cells exchange their positions. Following the idea that individuals adopt the state of one of their neighbours, the voter model updates one's opinion in two steps: first, selecting a neighbour; and second, adopting the selected neighbour's opinion. Numerous variations of the voter model have been proposed, modifying the rules for neighbour selection and opinion switching: The q-voter model enhances the classic voter model by incorporating a parameter q, which represents the number of neighbours a voter must consult before potentially changing their opinion<cit.>; The noisy voter model introduces spontaneous state transitions, or "noise" to reflect a more realistic dynamic where changes in state are not solely due to peer influence<cit.>. Granovsky and Madras provide exact formulas for certain crucial time-dependent and equilibrium functionals by the use of duality. The impact of social networks on collective patterns has also been thoroughly explored. 
Sood and Redner offer significant insights into how the voter model behaves on heterogeneous graphs, and relate the mean time to reach consensus with the moment of the degree distribution<cit.>. For a more comprehensive tutorial on voter model dynamics, we refer to <cit.>.

The threshold model and the voter model discussed above, however, do not take into account the degree of difference between opinions. That is, opinions that differ significantly exert the same influence on one‘s opinion switching as those that differ slightly, implying that opinion values are not ordered. By contrast, the weighted-median dynamics consider ordered discrete opinions, demonstrating that social influence depends on the weighted-median opinions of one's neighbour<cit.>. Mei et al. conduct a detailed analysis of the weighted-median opinion dynamics including characterizing the equilibria set and establishing the almost-sure convergence<cit.>.


Although research into discrete opinion models is extensive, the inherent settings of these models prevent the generation of new opinions during the evolution, thereby limiting their ability to explain the phenomenon of compromise in opinions. On this point, continuous opinion dynamics models offer a more nuanced illustration of social influence.


The most fundamental mechanism to achieve compromise in opinions is the weighted-averaging mechanism originated from the French-DeGroot model. The French-DeGroot model proposes a process in which each individual repeatedly updates his/her opinion by averaging the opinions of his neighbours in a network<cit.>. This model effectively describes how continuous interactions among group members lead to consensus, provided that the associated influence network satisfies certain requirements<cit.>. Its simplicity and explicit convergence endow it with border applications such as in coordination algorithms <cit.>. However, as persistent disagreement is commonly observed in daily life, a great number of variants have been proposed and studied extensively to better model the diversity of opinions: The Friedkin-Johnsen (F-J) model introduces prejudice to explain the dissensus of opinions<cit.>; The Hegselmann-Krause (H-K) model assume that individuals only assign weights to opinions within certain distances from their own opinions<cit.>; The Altafini model considered the presence of negative weights in the influence network<cit.>.

Additionally, dynamics of other influence factors are incorporated into the weighted-averaging mechanism to suit sophisticated scenarios:  <cit.> extends traditional opinion dynamics models to multidimensional settings, then the influence among different dimensions of opinions, which co-evolves as logic constraints, is discussed in <cit.>; For a general model, <cit.> considers four types of couplings of options and agents, then establish a nonlinear multioption opinion dynamics model covering a series of nonlinear consensus models. The behaviours of this general model include bifurcations of multistable agreement and disagreement, and is tractably analyzed by a few key parameters, offering both theoretical insights and practical methods for analyzing opinion dynamics within a unified framework. The weighted-averaging mechanism also advances social learning by averaging local Bayesian updates and beliefs of neighbours<cit.>.  Moreover, the impact of social networks structure on collect pattern is also deeply studied assuming the weighted-averaging mechanism<cit.>.


However, the weighted-averaging is criticized for having severely unrealistic implications. <cit.> exemplifies a simple but representative case where  individual i is influenced by individuals j and k via the weighted-averaging mechanism, and rewrites the dynamics as

    x_i(t+1)=x_i(t)+w_ik(x_k(t)-x_i(t))+w_ij(x_j(t)-x_i(t)),
 
where x_i(t) represents the opinion of i at time t and w_ij represents j's influence weight on i. Equation (<ref>) indicates that a more divergent opinion unreasonably earns a higher "attractiveness" to drive one's opinion moving towards it, which results in a consensus under mild network connectivity conditions. 


 §.§ Contribution

As reviewed, the weighted-averaging mechanism is now considered inadequate as a foundation, while the original weighted-median dynamic discrete opinion model fails to account for the emergence of compromise in opinions. In this paper, we propose a continuous-time weighted-averaging model and conduct a rigorous analysis of its dynamics. The contributions of this paper are as follows:

First, we model the weighted-median mechanism within a continuous-time framework. Our proposed model extends the existing discrete opinion dynamics to a continuous opinion setting and captures the dynamics of compromise. Additionally, this dynamic is based on a more realistic foundation, preventing distant opinions from generating  absurdly large attractiveness.

Second, we conduct a solid analysis on the solution to the proposed ordinary differential equation. We establish the existence and uniqueness of the solution to the dynamics by proving the weighted-median operator is non-expanding. We characterize the set of all the equilibria and prove their stability. Moreover, by refining the invariants sets, this paper obtains the convergence of the dynamics for any initial condition, and then derives a sufficient and necessary graph-theoretic condition for almost-sure convergence to consensus equilibria. Furthermore, a sufficient condition for almost-sure convergence to disagreement equilibria is provided.




 §.§ Organization

The rest of the paper is organized as follows. Section II introduces some basic definitions and notions, as well as the formulation of the continuous-time weighted-median opinion dynamics. Section III contains all the theoretical analysis and proofs of the main results. Section IV concludes. Proofs of lemmas can be found in the appendices.



§ BASIC DEFINITIONS AND MODEL SETUP

Let ⊆ (⊂ resp.) be the symbols for subset (proper resp.). Denote by ℕ the set of natural numbers, i.e., ℕ={0,1,2,…}. Let ℤ (ℤ_+ resp.) be the set of (positive resp.) integers. Let 1_n (0_n resp.) be the n-dimension vector whose entries are all ones (zeros resp.).

Consider a group of n individuals labelled by = {1,…,n}. The interaction relationships among the group are described by a directed and weighted graph (W), where W=(w_ij)_n× n is the associated adjacency matrix. Here, w_ij > 0 means that there is a link from node i to node j with weight w_ij, or, equivalently, individual i assigns w_ij > 0 weight to individual j. Since nodes in (W) represent individuals in opinion dynamics, we also call (W) influence matrix. Denote by _i the set of node i's out-neighbours, i.e., _i = {j∈𝒱|w_ij≠ 0}, which includes node i itself if w_ii≠ 0.
Conventionally, an influence matrix W is assumed to be row-stochastic.

The formal definition of weighted median is given below.

Given any n-tuple of real values x=(x_1,…, x_n) and any n-tuple of non-negative weights w=(w_1,…, w_n) with ∑_i=1^n w_i=1, x^*∈{x_1,…, x_n} is a weighted median of x associated with the weights w if x^* satisfies 
   
    ∑_i:  x_i<x^* w_i ≤ 1/2,  and  ∑_i:  x_i>x^*w_i ≤ 1/2.

 

For simplicity, we also say that x^* is a weighted median of x associated with w. The following lemma characterized some basic properties on the uniqueness of the weighted median <cit.>.

Given any n-tuple of real values x=(x_1,…, x_n) and any n-tuple of non-negative weights w=(w_1,…, w_n) with ∑_i=1^n w_i=1, 



  * the weighted median of x associated with w is unique if and only if there exists x^*∈{x_1,…, x_n} such that
   
    ∑_i:  x_i<x^* w_i < 1/2,  ∑_i:  x_i=x^* w_i >0,  ∑_i:  x_i>x^*w_i <1/2.
 
Such an x^* is the unique weighted median;

  * the weighted medians of x associated with w are not unique if and only if there exists z∈{x_1,…, x_n} such that ∑_i:  x_i<z w_i = ∑_i:  x_i≥ z w_i = 1/2. In this case, x^*∈{x_1,…, x_n} is the smallest weighted median if and only if

    ∑_i:  x_i<x^* w_i < 1/2,   ∑_i:  x_i=x^* w_i > 0,  ∑_i:  x_i>x^* w_i = 1/2,

and x^*∈{x_1,…, x_n} is the largest weighted median if and only if 

    ∑_i:  x_i<x^* w_i = 1/2,   ∑_i:  x_i=x^* w_i > 0,  ∑_i:  x_i>x^* w_i < 1/2.

Moreover, for any x̂∈{x_1,…, x_n} such that x^*<x̂<x^*, x̂ is also a weighted median and ∑_i: x_i = x̂w_i =0.





Compared to the straightforward picking of opinions at discrete time steps, the continuous-time variant aims to entail ongoing effects of the weighted-median mechanism. Consequently, the dynamics are constructed on the assumption that individuals' opinions gradually shifts towards the weighted median of their out-neighbours' opinions.    The continuous-time weighted-median opinion dynamics is formally defined as follows:

Given any directed and weighted influence network (W) with n individuals, denote by x(t)∈ℝ^n the vector of the individuals' opinions at time t. Starting from any initial condition x_0∈ℝ^n, the continuous-time weighted-median opinion dynamics is given as

    ẋ(t) = f(x(t)) = (x(t);W) - x(t),
 
where _i(x(t);W) is the weighted median of x(t) associated with the weights given by the i-th row of W, i.e., (w_i1,w_i2,…, w_in). If the weighted-median is not unique, then let _i(x(t);W) be the weighted median that is the closest to x_i(t).



Note that compared with the discrete-time model, the continuous-time weighted-median model differs in two aspects:


  * The updating of opinions has no time steps and is asynchronous, which means the convergence cannot be established by finding update sequences.

  * New opinions can be generated during the dynamic.
   





§ DYNAMICAL BEHAVIOR OF THE CONTINUOUS-TIME WEIGHTED-MEDIAN OPINION DYNAMICS

 In this section, we establish the existence and uniqueness of system (<ref>)'s solution, characterize the set of all the equilibria of (<ref>), and then prove its convergence. A necessary and sufficient graph theoretic condition for convergence to consensus, as well as a sufficient condition for convergence to disagreement equilibria, is also provided and proved. 




 §.§ Notations

Before proceeding to the rigorous analysis, we first introduce some notations frequently used in this section, see Table <ref>.

 

For any function f: ℝ→ℝ^n, if f is right-differentiable, denote by d^+f(t)/dt the right derivative of f at t, i.e.,

    d^+f(t)/dt = lim_Δ t↓ 0  f(t+Δ t) - f(t)  /Δ t.
 
For any autonomous system ẋ=f(x), denote the omega-limit set of any x by ω(x) and denote by ϕ(t,x) the solution at t≥ 0 starting from x, i.e., ϕ(0,x)=x. Given a dynamical system ẋ = f(x), where f: ℝ^n →ℝ^n, and a function V: ℝ^n →ℝ, define D^+V(x) with respect to the dynamics ẋ = f(x) as the lower Dini derivative:
   
    D^+V(x) = lim inf_Δ t ↓ 0  V(x+Δ t f(x)) - V(x)  /Δ t.

   Note that x+Δ t f(x) is the first-order Euler approximation of ϕ(Δ t,x), but the definition of D^+V(x) is NOT necessarily equivalent to the limit lim inf_Δ t ↓ 0( V( ϕ(Δ t, x) ) - V(x) )/Δ t.
   
   
When analysing the discrete-time weighted-median model, two network structures: the cohesive sets and the decisive links, are introduced to illustrate the dynamical behaviour of the weighted-median mechanism. These concepts are equally valuable in our analysis and we adopt the same definitions as presented in <cit.>. For a more detailed discussion and proofs of lemmas, we refer to <cit.>.

Given an influence network 𝒢(W) with node set V, a cohesive set ℳ⊂𝒱 is a subset of nodes that satisfies ∑_j∈ℳ w_ij≥ 1/2 for any i∈ℳ. A cohesive set  is a maximal cohesive set if there does not exist i∈∖ such that ∑_j∈ w_ij>1/2.



Given the concept of cohesive sets, we further introduce a process called cohesive expansion.

Given an influence network (W) with node set  and a subset of nodes ⊂, the cohesive expansion of , denoted by (), is the subset of  constructed via the following iteration algorithm:


  * Let _0=;

  * For k=0,1,2,…, if there exists i∈∖_k such that ∑_j∈_k w_ij>1/2, then let _k+1=_k ∪{i};

  * Terminate the iteration at step k as long as there does not exist any i∈∖_k such that ∑_j∈_k w_ij>1/2, and let ()=_k.



The following lemma presents some important properties of cohesive sets and cohesive expansions.

Given an influence network 𝒢(W) with the node set , the following statements hold:


  * If _1, _2⊆ are both cohesive sets, then _1∪_2 is also a cohesive set;

  * For any ⊂, the cohesive expansion of  is unique, i.e., independent of the order of node additions;

  * For any , ⊂, if ⊂, then ()⊂();

  * For any , ⊂, ()∪() ⊂ (∪); and

  * If  is a cohesive set, then () is also cohesive and is the smallest maximal cohesive set that includes , that is, for any maximal cohesive set  such that ⊂, we have ()⊂. 



Below we present another useful lemma on cohesive sets, which is a straightforward consequence of Definition <ref>.

Given an influence network 𝒢(W) with node set  and a cohesive set ⊂, if  is maximally cohesive and ⊂, then ∖ is also maximally cohesive; If  is not maximally cohesive, then either of the following two statements holds:

0em 

  * ()=;

  * () and ∖() are both non-empty and maximally cohesive. 



Another important concept involved in called decisive link. 

Given an influence network 𝒢(W) with the node set , define the out-neighbor set of each node i as _i = {j∈ |  w_ij≠ 0}. A link (i,j) is a decisive out-link of node i, if there exists a subset θ⊂_i such that the following three conditions hold: (1) j∈θ; (2) ∑_k∈θ w_ik > 1/2; (3) ∑_k∈θ∖{j} w_ik<1/2. Otherwise, the link (i,j) is an indecisive out-link of node i.






 §.§ Useful Lemmas


Before analyzing the dynamical behavior of the continuous-time weighted-median opinion dynamics (<ref>), we present and prove some lemmas that will be used in the proof of our main theorems.
The following lemma states that, if the trajectory of an ODE system converges to a set of stable equilibria, then it converges to a unique equilibrium. Its proof is given in Appendix <ref>.

Consider an ODE system ẋ=f(x) with domain D⊆ℝ^n. Let ‖·‖ be a norm in ℝ^n and let χ be a set of equilibria of the system, i.e., f(x)=0 for any x∈χ. Suppose that any equilibrium x∈χ is stable. Given any x_0∈ D, if its ω-limit set satisfies ω(x_0)⊆χ, then the solution trajectory ϕ(t,x_0) converges to a unique x^*∈χ, i.e., ω(x_0)={x^*}.


The following lemma is a slightly more conservative version of the original LaSalle invariance principle proposed as Theorem 2 in <cit.>.

   Consider an autonomous system ẋ=f(x), where f:ℝ^n →ℝ^n is globally Lipschitz on ℝ^n. If G⊆ℝ^n is a compact and positively invariant set of the system; and there exists a locally Lipschitz function V:ℝ^n →ℝ such that D^+V(x) exists and is non-positive for any x∈ G, then for any x∈ G, the solution ϕ(t,x) converges to M as t→∞, where M is the largest invariant set in E={x∈ G |  D^+V(x)=0}. 
   
By applying LaSalle invariance principle we usually obtain the convergence of the solution to some subset of the dynamical systems' domain. The lemma below helps to further refine the set that the solution converges to. The proof is given in Appendix <ref>.

Consider an ODE system ẋ=f(x), where f:ℝ^n→ℝ^n is globally Lipschitz and G⊆ℝ^n is compact and positively invariant with respect to the system dynamics. For any given x∈ G, if there exists an open set B⊆ G such that 
   
   0em
   
  * x∉ B∪∂ B;
   
  * there exists T>0 such that ϕ(t,x)∈ B for any t≥ T;
   
  * B∪∂ B is positively invariant,
   
then x∉ω(y) for any y∈ G.



For any x∈ℝ^n, the function V: ℝ^n→ℝ defined by V(x)=max {x_1,x_2,…,x_n} is globally Lipschitz.



Proof of Lemma <ref>:  For any x,  y∈ℝ^n, |V(x)-V(y)|=|max_i x_i - max_j y_j|. Let i^*∈_i x_i and j^*∈_j y_j and, without loss of generality, assume that max_i x_i ≥max_j y_j. We have

    0    ≤ |V(x)-V(y)| = |x_i^*-y_j^*|=x_i^*-y_j^*≤ x_i^*-y_i^*
       ≤‖ x-y ‖_∞.

Therefore, V(x) is globally Lipschitz in x.



 §.§ Main results


We first establish the existence and uniqueness of the solution to the continuous-time weighted-median opinion dynamics (<ref>) starting from any initial condition.

Given the influence matrix W, (x;W), as a map for x, is non-expanding in the sense that, for any x, y∈ℝ^n, ‖(x;W)-(y;W) ‖_∞≤‖ x-y ‖_∞. Therefore, the function f in equation (<ref>) is globally Lipschitz in ℝ^n. As a result, for any initial condition x_0∈ℝ^n, the solution ϕ(t,x_0) exists and is unique.

Proof of Theorem <ref>:
We prove by contradiction. Suppose 

    ‖(x;W)-(y;W) ‖_∞ > ‖ x-y ‖_∞,

i.e.,  there exists i∈𝒱 such that 

    | _i(x;W)-_i(y;W) |> |x_k-y_k|

for any k∈𝒱. Apparently this implies that 

    |_i(x;W)-_i(y;W)|>‖ x-y ‖_∞≥ 0.

Without loss of generality, assume that _i(x;W)>_i(y;W). Let 

    𝒳_i     = { j∈𝒩_i | x_j≥_i(x;W) }, and 
    𝒴_i   ={ j∈𝒩_i  | y_j≤_i(y;W) }.

According to Definition <ref>,

    ∑_j∈𝒳_i w_ij≥ 1/2,  and ∑_j∈𝒴_iw_ij≥ 1/2.

Now we show that these two inequalities lead to contradictions.

We first consider the case when the strict inequality holds in at least one of the two inequalities above. Since ∑_j∈𝒩_i w_ij=1 and w_ij≥ 0 for any j, we have that 𝒳_i∩𝒴_i must be non-empty, otherwise we obtain

    1<∑_j∈𝒳_i ∪𝒴_iw_ij≤∑_j=1^n w_ij,
 
which cannot be true. For any j^*∈𝒳_i∩𝒴_i, since x_j≥_i(x;W) and y_j≤_i(y;W), we have 

    x_j^*-y_j^*≥_i(x;W)-_i(y;W)>0,

which contradicts the assumption that | _i(x;W)-_i(y;W) |> |x_k-y_k| for any k∈𝒱. 

Now we consider the case when ∑_j∈𝒳_iw_ij=1/2 and ∑_j∈𝒴_iw_ij=1/2. We aim to show that these equations lead to x_i-y_i ≥_i(x;W)-_i(y;W), which contradicts the pre-assumption _i(x;W)-_i(y;W)  > ‖ x-y ‖_∞. Let us first investigate the implication of the equation ∑_j∈𝒳_iw_ij=1/2. Since 

    ∑_j∈𝒳_iw_ij = ∑_j:  x_j≥_i(x;W) w_ij=1/2,

according to Lemma <ref>, the weighted median of x associated with the i-th row of W are not unique, and, among all such weighted medians, _i(x;W) is not the smallest. As a result, _i(x;W) is either the largest weighted median or a weighted median between the largest and the smallest. According to Definition <ref> and Lemma <ref>, if _i(x;W) is the largest weighted median, then x_i≥_i(x;W); if _i(x;W) is between the largest and the smallest, then x_i = _i(x;W) must hold. In either case, we have x_i≥_i(x;W). Following the same line of argument, ∑_j∈𝒴_iw_ij=1/2 implies that _i(y;W) is either the smallest weighted median of y associated with the i-th row of W, or a weighted median between the smallest and the largest. As a consequence, we have y_i ≤_i(y;W). Therefore, we obtain that 

    x_i-y_i ≥_i(x;W)-_i(y;W),

which contradicts the inequality

    _i(x;W)-_i(y;W)>‖ x-y ‖_∞.

This leads to the conclusion that the map (s;W) is non-expanding. As straightforward results, the function f(x)=(x;W)-x is globally Lipschitz in ℝ^n and the solution to the dynamics (<ref>) exists and is unique.


The following theorem characterizes the set of all the equilibria and their stability.

Consider the weighted-median opinion dynamics (<ref>) with the influence matrix W. The set of all the equilibria is given by the following set:

    = {    x∈ℝ^n  | ≤ r(x) is a maximal cohesive set
       on 𝒢(W), for any r∈{1,…,(x)}}
 
Moreover, each equilibrium x∈ is stable. 


The proof of Theorem <ref> is partly based on the following lemma and its proof is provided in Appendix <ref>.

Consider the weighted-median opinion dynamics (<ref>) with the influence matrix W. If  is a cohesive set on the influence network 𝒢(W), then, for any x∈ℝ^n, max_k∈ϕ_k(t,x) is non-increasing and min_k∈ϕ_k(t,x) is non-decreasing, for any t≥ 0.


As a consequence of Lemma <ref>, if  is a cohesive set in (W), then, for any x∈ℝ^n, ϕ(t,x),  is bounded in the compact set [min_k∈x_k,  max_k∈ x_k]^n for any t≥ 0. With Lemma <ref>, Theorem <ref> is proved as follows.

Proof of Theorem <ref>: We first point out that an x^*∈ℝ^n is an equilibrium of (<ref>) if and only if x_i^*=_i(x^*;W). That is, the continuous-time weighted-median opinion dynamics (<ref>) and the original weighted-median dynamics given in <cit.> in fact have the same equilibria set. If (x^*)=1, then x^* is a consensus state and it is in  since 1(x^*)= is always maximally cohesive. Suppose that (x^*)>1. For any r∈{1,…,(x^*)-1}, by applying Theorem 6 from <cit.> for some y∈ [r(x^*),r+1(x^*)), we immediately obtain that x^*∈ if and only if x^* satisfies the conditions in Theorem 6 from <cit.>. Namely,  in Theorem <ref> is exactly the set of all the equilibria of (<ref>).

Now we proceed to prove that each equilibrium is stable. For any x^*∈, either x^*_i=x^*_j for any i, j∈𝒱, or (x^*)>1 and ≤ r(x^*) is maximally cohesive for any r≤(x^*). we refer to these two cases as Case 1 and Case 2 respectively.

In Case 1, for any ϵ>0, let δ = ϵ/2. Then, for any x_0 such that ‖ x_0-x^* ‖_∞<δ, we have max_i x_0,i<x_i^*+δ and min_ix_0,i>x_i^*-δ. According to Lemma <ref>, we have

    max_i∈𝒱ϕ_i(t,x_0)    ≤max_i∈𝒱 x_0,i < x_i^*+δ,  and
    min_i∈𝒱ϕ_i(t,x_0)    ≥min_i∈𝒱 x_0,i > x_i^* -δ.

Therefore, ‖ϕ(t,x_0)-x^* ‖_∞<ϵ for any t≥ 0, i.e., x^* is stable.

In Case 2, for any ϵ>0, let

    δ = min{   ϵ/2,  max^(1)(x^*)-max^(2)(x^*) /2,…,
        max^((x^*)-1)(x^*)-max^((x^*))(x^*) /2}>0.

For any x_0 such that ‖ x_0-x^* ‖_∞<δ, we have

    max_i∈ x_0,i    < max_i∈ x^*_i + δ,
    min_i∈ x_0,i    > min_i∈ x^*_i - δ,

and, for any r<,

    min_i∈≤ r(x^*)x_0,i    > max_i∈r(x^*)-δ
        >max_i∈r+1(x^*) + δ
        > max_i∈>r(x^*) x_0,i.

Moreover, since ≤ r(x^*) is a maximal cohesive set for any r∈{1,…,}, according to Lemma <ref>, min_i∈≤ r(x^*)ϕ_i(t,x_0) is non-decreasing and max_i∈≤ r(x^*)ϕ_i(t,x_0) is non-increasing. Therefore, the inequalities above hold not only for x_0, but also for ϕ(t,x_0) with any t≥ 0. That is, ‖ϕ(t,x_0) - x^* ‖_∞<δ<ϵ for any t≥ 0. Combining Case 1 and Case 2, we conclude that any x^*∈ is stable.


In what follows, we establish the convergence of the continuous-time weighted-median opinion dynamics, and then provide a sufficient and necessary graph-theoretic condition for almost-sure convergence to consensus equilibria. A sufficient condition for almost-sure convergence to disagreement equilibria is also provided.

Consider the weighted-median opinion dynamics defined by equation (<ref>) with the influence matrix W. The following statement hold:

0em

  * For any x_0∈ℝ^n, there exists x^*∈, depending on x_0, such that the solution ϕ(t,x_0) converges to x^* as t→∞;

  * If 𝒱 is the only maximal cohesive set on 𝒢(W), then, for any x_0∈ℝ^n, ϕ(t,x_0) converges to a consensus equilibrium.

  * If 𝒱 is not the only maximal cohesive set on 𝒢(W), then there exists a subset X_0,disagree⊆ℝ^n with non-zero measure, such that, for any x_0∈ X_0,disagree, ϕ(t,x_0) converges to a disagreement equilibrium;





In order to prove Theorem <ref>, we need to introduce the following definition and lemmas.


Consider a scalar ODE system ẏ(t) = β(t) - y(t), where β(t) is an integrable function. If there exists y^*∈ℝ such that lim_t→ +∞β(t)=y^*, then lim_t→ +∞y(t)=y^*.

The proof of Lemma <ref> is provided in Appendix <ref>.


Given a set of nodes 𝒜 on an influence network (W), the largest cohesive set  contained in 𝒜 is a cohesive subsets of 𝒜 such that any subset  of 𝒜 satisfying ⊂ is not cohesive. 


By Definition <ref>, the largest cohesive set contained in 𝒜 is either empty (when none of the subsets of 𝒜 is cohesive) or unique. The proof for uniqueness is straightforward as follows: Suppose _1 and _2 (_1≠_2) are both the largest cohesive sets contained in 𝒜. Then, according to Lemma <ref>, _1∪_2 ⊆𝒜 is also cohesive and therefore _1 and _2 cannot be the largest cohesive set. The difference between “maximal cohesive set” and “the largest cohesive set” are illustrated in Fig. <ref>.



The largest cohesive set exhibits some important properties in the continuous-time weighted-median opinion dynamics (<ref>), characterized by the following lemma. The proof is provided in Appendix <ref>.

Consider the continuous-time weighted-median opinion dynamics (<ref>) on the influence network (W). For any x∈ℝ^n, define ^(1)(x;W) as the largest cohesive set contained in 1(x). The following statements hold:

0em

  * For any j∉1(x), ϕ_j(t,x)<max^(1)(x) for any t≥ 0;

  * If ^(1)(x;W) is an empty set, then 1( ϕ(t,x) )<1(x) for any t>0;

  * If ^(1)(x;W) is non-empty, then, for any i∈^(1)(x;W), ϕ_i(t,x)=1(x) for any t≥ 0. Moreover, there exists Δ t>0 such that ϕ_j(Δ t,x)<1(x) for any j∉^(1)(x;W);

  * Denote by ^(1)(x;W) the cohesive expansion of ^(1)(x;W). If ^(1)(x;W) is non-empty, then lim_t→∞ϕ_i(t,x)=1(x) for any i∈^(1)(x;W).
 


With all the preparations above, now we are ready to prove Theorem <ref>.

Proof of Theorem <ref>: The main part of this proof is the establishment of convergence. Regarding the convergence of system (<ref>), the sketch of the proof is as follows: We first apply Lemma <ref> and Lemma <ref> to show that, for any given initial condition x_0, the solution ϕ(t,x_0) converges to the set of x's such that 1(x) forms a maximal cohesive set on the influence network (W). Then we further refine the result by proving that, for any x in such a set but not in , x cannot be an omega limit point of x_0. That is, ϕ(t,x_0) converges to . Finally, according to the stability of any fixed point, which is already established in Theorem <ref>, we prove that, for any given x_0∈ℝ^n, ϕ(t,x_0) must converge to a unique fixed point in .

First of all, in order to apply Lemma <ref>, we need to check that all the conditions in Lemma <ref> are satisfied in system (<ref>).  According to Lemma <ref>, function f(x)=(x;W)-x is globally Lipschitz. For any x∈ℝ^n, since 

    _i(x;W) ≤ x_i,  for any i    ∈^(1)(x) and,
    _j(x;W) ≥ x_j,  for any j    ∈^((x))(x)
        =_k x_k,

we have that max_k ϕ_k(t,x) is always non-increasing and min_k ϕ_k(t,x) is always non-decreasing. Therefore, for any given x_0∈ℝ^n, G=[ min_k x_0,k, max_k x_0,k]^n is a compact and positively invariant set and x_0∈ G. Moreover, given any initial opinion x_0∈ℝ^n, define 

    V(x)=1(x)=max_k x_k

for any x∈ G. According to Lemma <ref>, V(x) is globally Lipschitz. Now we compute D^+V(x). By definition,

    D^+V(x) 
       = lim inf_Δ t↓ 0  V(x+Δ tf(x))-V(x)  /Δ t
        = lim inf_Δ t ↓ 0 max_k ( x_k +Δ t ( _k(x;W)-x_k )) -max_k x_k  /Δ t.

For sufficiently small Δ t, we have

    _k  x_k + Δ t ( _k(x;W)-x_k )  ⊂ 1(x)

Let 

    θ^(1)(x;W)={  i∈1(x)  |    _i(x;W)≥_j(x;W),
       for any j∈1(x) }.

That is, θ^(1)(x;W) is a subset of 1(x) such that the weighted-median opinion for any i∈θ^(1)(x;W) is no less than that of any other j∈1(x)∖θ^(1)(x;W). Therefore,

    _k  x_k + Δ t ( _k(x;W)-x_k ) = θ^(1)(x;W),

and, for any i∈θ^(1)(x;W),

    D^+V(x)
        = lim inf_Δ t ↓ 0  x_i + Δ t ( _i(x;W)-x_i )   - 1(x) /Δ t
        = lim inf_Δ t ↓ 0 1(x) + Δ t ( _i(x;W)-x_i )   - 1(x) /Δ t
        = lim inf_Δ t ↓ 0 Δ t ( _i(x;W)-x_i )    /Δ t
        = lim_Δ t ↓ 0 Δ t ( _i(x;W)-x_i )    /Δ t
        = _i(x;W)-x_i  ≤ 0.

Now, applying Theorem <ref>, we have that, as t→∞, ϕ(t,x_0) converges to the largest invariant set in

    E_1 = { x∈ G |    _i(x;W)-x_i=0,
       for any i∈θ^(1)(x;W) }.

For this proof, we only need the result that ϕ(t,x_0) converges to E_1.

Now we refine this result on convergence by proving that ϕ(t,x_0) converges to a subset of E_1. We first prove that, for any x∈ E_1, if 1(x) does not contain any cohesive set, then x cannot be an ω-limit point of the given initial condition x_0∈ℝ^n. We prove this by using Lemma <ref>. In order to apply Lemma <ref>, we need to construct an open set satisfying all the conditions given in Lemma <ref>. Such an open set is constructed as follows: For any given x∈ E_1, such that 1(x) does not contain any cohesive set, according to the statement 2) of Lemma <ref>, there exists Δ t^(1)>0 such that ϕ_i(Δ t^(1),x)<1(x) for any i∈𝒱. For this given x∈ E_1, construct an open set 

    B^(1) = {    z∈ G  |
       1(z) <1/2( 1(x)+1( ϕ(Δ t^(1),x) ) ) }.

Obviously, if x∈ E_1, then x∉ B^(1)∪∂ B^(1). Since 1( ϕ(t,z) ) is non-increasing for any z∈ℝ^n, we have that B^(1)∪∂ B^(1) is positively invariant. Moreover, since 

    ϕ_i(Δ t^(1),x)    ≤1( ϕ(Δ t^(1),x) )
        <( 1(x) + 1( ϕ(Δ t^(1),x)) )/2

for any i∈𝒱, we have ϕ(t,x)∈ B^(1) for any t≥Δ t^(1). According to Lemma <ref>, such an x cannot be an ω-limit point of x_0. Therefore, in order for x∈ E_1 to be an ω-limit point of x_0, 1(x) must contain a cohesive subset. That is, as t→∞, ϕ(t,x_0) converges to 

    M_0 = { x∈ G |    1(x) contains
       at least one cohesive set.}⊂ E_1.


Now we further refine the above result by proving that any x∈ M_0∖ is not an ω-limit point of x_0, i.e., ω(x_0)⊆. For any r∈ℤ_+, define

    M_r = { x∈ G  |    (x)≥ r and ≤ s(x)
       is maximally cohesive ∀  s≤ r }.

Since (W) only has a finite number of maximal cohesive sets, there exists R(W)∈ℤ_+ such that M_R(W) is non-empty and M_r is empty for any r> R(W). In addition, we know that M_1 must be non-empty, since the node set  as an entirety must be maximally cohesive and any consensus state x∈ G satisfies x∈ M_1. Namely, R(W)≥ 1 always holds. Moreover, according to the definition of M_r, we have

    M_R(W)⊆ M_R(W)-1⊆…⊆ M_1⊆ M_0.


For any given x∈ M_0∖, according to Theorem <ref>, there exists r∈{0,1,…,R(W)-1} such that x∈ M_r but x∉ M_r+1. For any such x, now we construct an open set B based on properties of the trajectory ϕ(t,x), and prove x∉ω(x_0) by leveraging Lemma <ref>. For any i∈≤ r(x), since x∈ M_r, we have _i(x;W)=x_i and thereby ϕ_i(t,x)=x_i>r+1(x) for any t≥ 0. For any i∈∖≤ r(x), properties of the trajectory ϕ_i(t,x) are established via analyzing an auxiliary trajectory ϕ(t,y) starting from y∈ G defined as follows:

    y_i = 
    r+1(x)      if i∈≤ r+1(x),
     x_i      if i∈∖≤ r+1(x).

As immediate results, we have 

    s(y)     =r+s(x),  ∀ s∈{1,…, (x)- r};
    1(y)     =≤ r+1(x) and 
    s(y)     =r+s(x),  ∀ s∈{2,…,(x)-r}.

Now we establish the relations between ϕ(t,x) and ϕ(t,y). Since ≤ r(x) is a maximal cohesive set, according to Lemma <ref>, both ≤ r(x) and ∖≤ r(x) are maximally cohesive. Therefore, according to Lemma <ref>, for any t≥ 0,

    ϕ_i(t,x)     >r+1(x)≥ϕ_j(t,x),
    ϕ_i(t,y)     =r+1(x)≥ϕ_j(t,y),

for any i∈≤ r(x) and any j∈∖≤ r(x). According to the definition of weighted median and the fact that ∖≤ r(x) is maximally cohesive, as long as inequality (<ref>) holds, the value of _j(ϕ(t,x);W) (_j(ϕ(t,y);W) resp.), for any j∈∖≤ r(x) does not depend on the value of ϕ_i(t,x) (ϕ_i(t,y) resp.), for any i∈≤ r(x). Moreover, since x_j=y_j for any j∈∖≤ r(x), we have 

    ϕ_j(t,x) = ϕ_j(t,y),

for any j∈∖≤ r(x) and any t≥ 0. In the following, we establish some properties of the trajectory ϕ_j(t,x), for any j∈∖≤ r(x), by analyzing the auxiliary trajectory ϕ(t,y).

According to how y is constructed, 1(y) contains at least one cohesive set, e.g., ≤ r(x). Denote by (y;W) the largest cohesive set contained in 1(y) and denote by (y;W) the cohesive expansion of (y;W). Since 1(y) is not maximally cohesive, we have 1(y)≠(y;W), which in turn implies that either of the following two cases holds:

    Case 1:     (y;W)⊆1(y)⊂(y;W);
    Case 2:     ∃  j∈1(y) such that j∉(y;W).


In Case 1, since 1(y)⊂(y;W), it holds that y_i<1(y) for any i∈(y;W)∖1(y). That is, min_k∈(y;W)y_k<1(y). In addition, max_k∈∖(y;W)y_k<1(y) holds by definition. Let

    b_1 = max{    max_k∈∖(y;W)y_k + 1(y)/2,
       min_k∈(y;W)y_k+1(y)/2 },

and construct the following open set:

    B_1 = { z∈ G |     z_i>b_1>z_j,
       ∀  i∈(y;W),  ∀  j∈∖(y;W)  }.

Now we prove that x and B_1 satisfies the conditions in Lemma <ref>. Firstly, according to how y is constructed, we have 

    min_k∈(y;W)x_k=min_k∈(y;W) y_k<b_1,

which implies that x∉ B_1∪∂ B_1. That is, condition 1) in Lemma <ref> is satisfied. Secondly, since (y;W) and ∖(y;W) are both cohesive, and 

    min_i∈(y;W)z_i≥ b_1≥max_j∈∖(y;W)z_j,

for any z∈ B_1∪∂ B_1, according to Lemma <ref>, we have

    min_i∈(y;W)ϕ_i(t,z)≥ b_1≥max_j∈∖(y;W)ϕ_j(t,z),

which implies that B_1∪∂ B_1 is positively invariant. That is, condition 3) in Lemma <ref> is satisfied. Thirdly, since ∖(y;W) is cohesive, according to Lemma <ref>, we have

    max_j∈∖(y;W)ϕ_j(t,y) ≤max_j∈∖(y;W)y_j < b_1,

for any t≥ 0. In addition, since 

    ( ∖(y;W) ) ⊂( ∖≤ r(x) )

and ϕ_j(t,x)=ϕ_j(t,y) for any j∈∖≤ r(x), we have

    max_j∈∖(y;W)ϕ_j(t,x)<b_1,   t≥ 0.

Moreover, according to statement 4) of Lemma <ref>, lim_t→∞ϕ_i(t,y)=1(y)=r+1(x) for any i∈(y;W). As an immediate result, there exists T_1>0 such that ϕ_i(T_1,y)>b_1 for any i∈(y;W). In addition, since  

    ϕ_j(t,x)     =ϕ_j(t,y) and 
    ϕ_i(t,x)     =r+1(x)=1(y)>b_1

hold for any t≥ 0, any j∈( (y;W)∖≤ r(x) )⊆( ∖≤ r(x) ), and any i∈≤ r(x), we have

    min_i∈(y;W)ϕ_i(T_1,x)>b_1.
 
Now we have proved that ϕ(T_1,x)∈ B_1, i.e., condition 2) in Lemma <ref> is satisfied. Therefore, any given x∈ M_0∖ such that the associated y is in Case 1 cannot be an ω-limit point of x_0.

In Case 2, according to statement 3) of Lemma <ref> and the continuity of ϕ(t,y) in t, there exists sufficiently small Δ t such that ϕ_j(Δ t, y)<1(y) for any j∈∖(y;W). Let

    b_2 = 1(y)+max_k∈∖(y;W)ϕ_k(Δ t,y)/2

and construct the open set 

    B_2 = { z∈ G  |     z_i>b_2>z_j,
       ∀ i∈(y;W),  ∀ j∈∖(y;W) }.

Now we prove that x and B_2 satisfies all the conditions in Lemma <ref>. Firstly, according to the assumptions of Case 2, there exists j∈1(y)=≤ r+1(x) such that j∉(y;W). In addition, since ≤ r(x)⊂(y;W), such j can only be in r+1(x). Therefore, 

    max_k∈∖(y;W)x_k=r+1(x)=1(y)>b_2,

i.e., x∉ B_2∪∂ B_2. That is, condition 1) in Lemma <ref> is satisfied. Secondly, since (y;W) and ∖(y;W) are both cohesive and min_i∈(y;W)z_i>b_2>max_j∈∖(y;W) z_j for any z∈ B_2, according to Lemma <ref>, we have

    min_i∈(y;W)ϕ_i(t,z)≥ b_2≥max_j∈∖(y;W)ϕ_j(t,z),
 
for any t≥ 0. That is, the closure B_2∪∂ B_2 is positively invariant, i.e., condition 3) in Lemma <ref> is satisfied. Thirdly, according to Lemma <ref>, 

    max_k∈∖(y;W)ϕ_k(t,y)≤max_k∈∖(y;W)ϕ_k(Δ t,y)<b_2

for any t≥Δ t. Since ( ∖(y;W) )⊆( ∖≤ r(x) ) and ϕ_j(t,x)=ϕ_j(t,y) for any j∈∖≤ r(x), we get 

    max_k∈∖(y;W)ϕ_k(t,x)<b_2, for any t≥Δ t.

In addition, since 

    lim_t→∞ϕ_i(t,y)     =1(y)>b_2,  ∀ i∈(y;W),
    ϕ_i(t,x)     = ϕ_i(t,y),  ∀ i∈(y;W)∖≤ r(x),
    and ϕ_i(t,x)     = x_i > r+1(x) = 1(y) > b_2,
           ∀ i∈≤ r(x),

there exists T_2≥Δ t>0 such that min_i∈(y;W)ϕ_i(T_2,x)>b_2. Therefore, ϕ(T_2,x)∈ B_2, i.e., condition 2) is satisfied. According to Lemma <ref>, any given x∈ M_0∖ such that the associated y is in Case 2 cannot be an ω-limit point of x_0.

Combining the arguments for Case 1 and Case 2 together, we conclude that ω(x_0)⊆∩ G. According to Lemma <ref>, there exists an equilibrium x^*∈∩ G such that ω(x_0)={x^*}, i.e., lim_t→∞ϕ(t,x_0)=x^*. This concludes the proof of statement 1).

If 𝒱 is the only maximal cohesive set of 𝒢(W), then M^*_r is empty for any r>1, i.e., = M^*_1. Therefore, for any x_0, ϕ(t,x_0) converges to a point x^*∈ M^*_1, which is a consensus equilibrium. This concludes the proof of statement 2).

If 𝒱_1⊂𝒱 is a maximal cohesive set, then 𝒱_2=𝒱∖𝒱_2 is also maximally cohesive. The set

    X = { x∈ℝ^n  |  x_i>x_j for any i∈𝒱_1,  j∈𝒱_2 }

is a subset of ℝ^n with non-zero measure. For any such x, according to Lemma <ref>, 

    min_k∈𝒱_1ϕ_k(t,x) ≥min_k∈𝒱_1 x_k > max_k∈𝒱_2 x_k ≥max_k∈𝒱_2ϕ_k(t,x).

Therefore, ϕ(t,x) does not converges to any consensus equilibrium. This concludes the proof of statement 3). 






§ CONCLUSIONS

In conclusion, this paper has developed a continuous-time weighted-median opinion dynamics model that advances the illustration of opinion compromise based on the weighted-median mechanism. We have rigorously established the foundational mathematical properties of the model, including the existence and uniqueness of solutions and the characterization of equilibria. Moreover, we have derived both necessary and sufficient graph-theoretic conditions for consensus and provided sufficient conditions for dissensus. These insights are pivotal for designing strategies in social networks to foster agreement or understand persistent disagreements. Future work will focus on exploring the role of networks structure on these dynamics under this model under this model. 










§ PROOF OF LEMMA <REF>


Suppose x^*, y^* are both in ω(x_0)⊆χ, and x^*≠ y^*. There exists ϵ>0 such that 

    inf_z∈ B(x^*,ϵ)‖ y^*-z‖ > ϵ,

where B(x^*,ϵ) = { z∈ D  | ‖ z-x^*‖ < ϵ}. Since x^* is stable, for the ϵ given above, there exists δ>0 such that, for any z satisfying ‖ z - x^* ‖< δ, ϕ(t,z)∈ B(x^*,ϵ) for any t≥ 0. Moreover, since x^* is an ω-limit point of x_0, there exists a time sequence {t_p}_p∈ℕ such that t_p→∞ as p→∞, and lim_p→∞ϕ(t_p,x_0) = x^*. As a consequence, there exists P such that 
‖ϕ(t_P,x_0) - x^* ‖<δ, which implies that ϕ(t,x_0)∈ B(x^*,ϵ) and thereby ‖ϕ(t,x_0)-y^* ‖>ϵ for any t≥ t_P. Therefore, y^* cannot be an ω-limit point of x_0. This concludes the proof.




§ PROOF OF LEMMA <REF>


Since f(x) is globally Lipschitz, for any given x∈ G, the solution ϕ(t,x) exists and is unique for any t≥ 0, and ϕ(t,x) is a continuous function of x.
   
   Since B is an open set and there exists T>0 satisfying ϕ(T,x)∈ B, there exists ϵ>0 such that, for any z satisfying ‖ z-ϕ(T,x) ‖<ϵ, we have z∈ B. Here ‖·‖ is some norm in ℝ^n. Moreover, since B∪∂ B is positively invariant, ϕ(t,z)∈ B∪∂ B for any t≥ 0. Additionally, since ϕ(t,x) is a continuous function of x, for the ϵ>0 given above, there exists ξ>0 such that, for any x̂ satisfying ‖x̂-x‖<ξ, ‖ϕ(T,x̂)-ϕ(T,x)‖<ϵ. Therefore, ϕ(t+T,x̂)∈ B∪∂ B, for any t≥ 0.
   
   Suppose there exists y∈ G such that x∈ω(y), then there exists a sequence {t_k}_k∈ℕ such that lim_k→∞t_k=∞ and lim_k→∞ϕ(t_k,y) = x, which implies that there exists K∈ℕ such that, for any k≥ K, ‖ϕ(t_k,y)-x ‖<ξ. Therefore, 
   
    ‖ϕ(T,ϕ(t_K,y))-ϕ(T,x) ‖ = ‖ϕ(T+t_K,y)-ϕ(T,x) ‖ <ϵ.
  
As a consequence, ϕ(t+T+t_K,y)∈ B∪∂ B for any t≥ 0, and thereby ‖ϕ(t,y)-x ‖≥(x,B∪∂ B)>0 for any t≥ T+t_K, which contradicts the assumption that x∈ω(y). This concludes the proof.



§ PROOF OF LEMMA <REF>


Given any x∈ℝ^n and any t≥ 0, let c_t = min_k∈ϕ_k(t,x) and c_t = max_k∈ϕ_k(t,x). For any j∈, since 

    ∑_k: ϕ_k(t,x)>c_t w_jk≤∑_k∉ w_jk< 1/2

and

    ∑_k: ϕ_k(t,x)<c_t w_jk≤∑_k∉ w_jk<1/2,

according to Definition <ref>, we have that 

    c_t ≤_j( ϕ(t,x);W ) ≤c_t

for any j∈. Therefore, for any j∈_k∈ϕ_k(t,x),

    dϕ_j(t,x)/dt = _j( ϕ(t,x);W ) - c_t ≤ 0,

and, for any j∈_k∈ϕ_k(t,x),

    dϕ_j(t,x)/dt = _j( ϕ(t,x);W ) - c_t ≥ 0.

This concludes the proof.




§ PROOF OF LEMMA <REF>


From ẏ(t)=β(t)-y(t) we immediately obtain 

    y(t) = ∫_0^t β(τ)e^τdτ + y(0)e^-t.

Let h(t)=∫_0^t β(τ)e^τdτ. Since lim_t→ +∞β(t)=y^*, we have that, for any ϵ>0, there exists T>0 such that |β(t)-y^*|<ϵ hold for any τ≥ T. Therefore, for any t≥ T,

    h(t) < ∫_0^T β(τ)e^τdτ/e^t + (y^*+ϵ)(e^t-e^τ)/e^t.

The right-hand side of the above inequality converges to y^*+ϵ as t→+∞. Therefore, we have lim sup_t→+∞h(t)≤ y^*+ϵ. Similarly, we have

    h(t) > ∫_0^T β(τ)e^τdτ/e^t + (y^*-ϵ)(e^t-e^τ)/e^t,

of which the right-hand side converges to y^*-ϵ and thereby lim inf_t→_∞h(t)≥ y^*-ϵ. Now we have that

    y^*-ϵ≤lim inf_t→+∞ h(t) ≤lim sup_t→+∞ h(t) ≤ y^*+ϵ

holds for any ϵ>0. Therefore, we obtain 

    lim inf_t→+∞ h(t)=lim sup_t→+∞ h(t)=y^*,

i.e., h(t) converges to y^* as t→+∞. Moreover, since y(t)=h(t)+y(0)e^-t and lim_t→+∞ y(0)e^-t = 0, we eventually have lim_t→+∞ y(t) = y^*.




§ PROOF OF LEMMA <REF>


The proof of statement 1) is straightforward. According to Lemma <ref>, for any x∈ℝ, 1( ϕ(t,x) ) is non-increasing with t. Therefore, for any i∈, we have

    d^+ϕ_i(t,x)/dt    = _i( ϕ(t,x);W ) - ϕ_i(t,x) 
       ≤1(x) - ϕ_i(t,x),

which leads to

    ϕ_i(t,x)≤1(x)  - ( 1(x) - x_i )e^-t.

Therefore, for any i∈1(x), ϕ_i(t,x)<1(x) for any t>0. This concludes the proof of statement 1).

Now we prove statement 3). Statement 2) can be easily inferred from the proof of Statement 3). Suppose ^(1)(x)⊆1(x) is non-empty. For any i∈^(1)(x;W), since ^(1)(x;W) is cohesive, we have _i(x;W)=x_i = 1(x). Therefore, for any i∈^(1)(x;W), ϕ_i(t,x)=x_i=1(x) for any t≥ 0. Now we prove that, for any j∉^(1)(x;W), ϕ_j(Δ t,x)<1(x) for some Δ t>0. Suppose ^(1)(x;W)=1(x), according to statement 1), ϕ_j(t,x)<1(x) for any j∉1(x)=^(1)(x;W) and any t≥ 0. Now suppose ^(1)(x;W)⊂1(x;W). Define 𝒱_-1=𝒱∖1(x). According to statement 1), for any j∈𝒱_-1, ϕ_j(t, x)<1(x) for any t≥ 0. Moreover, since 1(x) is not cohesive, there exists j∈1(x) such that ∑_k∈_-1 w_jk>1/2, which implies that _j(x;W)<1(x). Define the set of all such j's as ϑ_1, i.e., the set of nodes in 1(x) who assign more weights to the nodes outside 1(x) than the nodes inside 1(x). For any j∈ϑ_1,

    d^+ϕ_j(t,x)/dt|_t=0    = _j(x;W)-x_j 
        = _j(x;W) - 1(x) < 0.

Therefore, there exists Δ t>0 such that ϕ_j(t,x)<ϕ_j(0,x)=1(x) for any t∈ (0,Δ t]. We thereby have ϕ_j(Δ t, x)<1(x) for any j∈𝒱_-1∪ϑ_1. 

With the nodes in ϑ_1 removed, the set 1(x)∖ϑ_1 is still not necessarily cohesive, since there could exist j∈1(x)∖ϑ_1 such that j assigns more weights to ϑ_1 ∪_-1 than 1(x)∖ϑ_1. If such a j does exist, then ^(1)(x;W)⊂1(x)∖ϑ_1 and 1(x)∖ϑ is still not cohesive, which implies that the set 

    ϑ_2 = {  j∈1(x)∖ϑ_1  | ∑_k∈𝒱_-1∪ϑ_1 w_jk>1/2  }

is non-empty. For any j∈ϑ_2,

    d^+ ϕ_j(t,x)/dt    = _j(ϕ(t,x);W) - ϕ_j(t,x) 
       ≤max_k∈𝒱_-1∪ϑ_1ϕ_k(t,x) - ϕ_j(t,x).

At any time instant t∈ (0,Δ t], if 

    ϕ_j(t,x)>max_k∈𝒱_-1∪ϑ_1ϕ_k(t,x),
 
then d^+ϕ_j(t,x)/dt <0; If 

    ϕ_j(t,x)≤max_k∈𝒱_-1∪ϑ_1ϕ_k(t,x),
 
then ϕ_j(t,x)<1(x). Therefore, during the time period (0,Δ t], either d^+ϕ_j(t,x)/dt <0 or ϕ_j(t,x)≤max_k∈𝒱_-1∪ϑ_1ϕ_k(t,x)<1(x), which implies that ϕ_j(Δ t,x)<ϕ_j(0,x)=1(x). 

Following the same argument above, if 1(x)∖ (ϑ_1∪ϑ_2) is still not cohesive, then ^(1)⊂1(x)∖ (ϑ_1∪ϑ_2) and the set

    ϑ_3 ={  j∈1(x)∖ (ϑ_1∪ϑ_2) | ∑_k∈𝒱_-1∪ϑ_1 ∪ϑ_2w_jk>1/2  }

is non-empty. Moreover, for any j∈ϑ_3, ϕ_j(Δ t,x)<1(x). Since the cardinality of 1(x) is finite, by repeating this argument, we eventually obtain a finite K such that ^(1)(x;W)=1(x)∖ (ϑ_1∪…∪ϑ_K), and for any j∈𝒱∖^(1)(x;W), ϕ_j(Δ t, W)<1(x). Moreover, for any i∈^(1)(x), since ^(1)(x) is cohesive, ϕ_i(t,x)=1(x) for any t≥ 0. This concludes the proof of statement 3).

The argument above implies that, if ^(1)(x;W) is empty, then there exists a finite K̃ such that 1(x) = ϑ_1∪…∪ϑ_K̃ and thereby ϕ_i(Δ t,x)<1(x) for any i∈1(x). This concludes the proof of statement 2).


Now we proceed to prove statement 4). Define 

    _1 ={ j∈^(1)(x;W)∖^(1)(x;W) | ∑_k∈^(1)(x;W)w_jk>1/2. }.

If _1 is empty, then ^(1)(x;W)=^(1)(x;W) and we already show that, for any i∈^(1)(x;W), ϕ_i(t,x)=1(x) for any t≥ 0, which concludes the proof of statement 4). If _1 is non-empty, then, for any j∈_1, we have _j(ϕ(t,x),W)=1(x) for any t≥ 0. Therefore,

    d^+ ϕ_j(t,x)/dt = 1(x) - ϕ_j(t,x),

which leads to lim_t→∞ϕ_j(t,x)=1(x). Define

    _2 = {    j∈^(1)(x;W)∖( ^(1)(x;W)∪_1 ) |
       ∑_k∈^(1)(x;W)∪_1 w_jk>1/2. }.

If _2 is empty, then ^(1)(x;W)=^(1)(x;W)∪_1 and we already prove that, for any j∈^(1)(x;W)∪_1, lim_t→∞ϕ_j(t,x)=1(x). If _2 is non-empty, then, for any j∈_2, since ∑_k∈^(1)(x;W)∪_1w_jk>1/2, we have 

    min_k∈^(1)(x;W)∪_1ϕ_k(t,x) ≤_j(ϕ(t,x);W) ≤1(x).

Since, for any t≥ 0, we have ϕ_j(t,x)≤1(x),

    min_k∈^(1)(x;W)∪_1ϕ_k(t,x) - ϕ_j(t,x)    ≤d^+ϕ_j(t,x)/dt
       ≤1(x) - ϕ_j(t,x),

and

    lim_t→∞min_k∈^(1)(x;W)∪_1ϕ_k(t,x) = 1(x),

according to Lemma <ref>, we have lim_t→∞ϕ_j(t,x)=1(x). Define

    _3 = {    j∈^(1)(x;W)∖( ^(1)(x;W)∪_1 ∪_2 ) |
       ∑_k∈^(1)(x;W)∪_1 ∪_2 w_jk>1/2. }.

Following the same argument for _2, if _3 is empty, then ^(1)(x;W)=^(1)(x;W)∪_1∪_2. If _3 is non-empty, then, according to Lemma <ref>, lim_t→∞ϕ_j(t,x)=1(x) for any j∈_3. Repeating this argument, since ^(1)(x;W) is a finite set, there exists K∈ℕ such that ^(1)(x;W)=^(1)(x;W)∪_1∪…∪_K, and lim_t→∞ϕ_j(t,x)=1(x) for any j∈^(1)(x;W). 







IEEEtran




