Consensus problems on networks with free protocol*

Xiaodong Liu(柳曉東) and Lipo Mo(莫立坡)

1School of Mathematics and Statistics,Beijing Technology and Business University,Beijing 100048,China

2Key Laboratory of Power Big Data of Guizhou Province,Guizhou Institute of Technology,Guiyang 550003,China

Keywords: multi-agent systems,random protocol,consensus with probability one

1. Introduction

In recent decades,more and more studies for multi-agent systems have been carried out and many excellent results have been reported.[1-24]In Refs. [1-14], agents were assumed to keep cooperative relationships with each other. However, in Refs. [15-24], the antagonistic relation was considered. By studying the differences between the above literature,we consider the following four questions: Firstly, why should we give agents the freedom? Secondly, how do we describe the agents’requirement that they want to have a standby choice to deal with the change of the outside environment of the system?Thirdly, what control protocols will they be able to choose if we give agents the right to choose? Fourthly,what is the final outcome of the system if we give agents the rights to choose their relationship with neighbors?

As is known to all, humans cannot be controlled like a machine. In the social network, humans have always been controlled as agents. In order to better study the effects of human behavior on social networks,we should give agents the freedom as humans. That’s the answer to the first question.

For the second question,we designed a new control protocol called the free protocol to describe the agent’s requirement of having alternate protocols to be chosen. According to Refs.[16,17], the weight between agents can be explained in symbol and size. The symbol represents whether agents are cooperative or antagonistic between each other. The size represents the strength of information that the agent responds to its neighbors. The larger the size is,the more eager the agent is to keep the same or opposite state with its neighbor agent.Hence,we propose two simple control protocols for agents to choose.

For the third question,we consider how an agent makes a choice. When we make a decision, we always simulate what we are going to do at first. Listing and evaluating all the options, then we choose one of them to execute. In this paper,based on this behavior pattern,we assume all agents randomly select the two control protocols and count the probability distribution that the agent follows.

For the last question,we analyze all the possible patterns when agents are free to choose. If all agents select once on the whole time, we call it static selection. Instead, if there is an agent changing its choice frequently,we call it dynamic selection. When the information interaction between agents is single-orientation,we call it single-orientation communication. Otherwise,we call it double-orientation communication.When an agent chooses a policy independently,we call it unilateral pattern. In addition,when the protocol is chosen jointly by two communicating agents,we call it bilateral pattern.

The contributions of this paper are as follows: (i) Compared with previous papers such as Refs.[1-24],we consider the willingness of agents in a multi-agent system, which is more reasonable and realistic. (ii)Different from the noise in the previous works,such as Ref.[24],the method used in this paper combines probabilistic science with control science in a new perspective. (iii)The concept of the structurally balanced is used to calculate the probability of bipartite agreement in some cases firstly, then by the knowledge of probability, the sufficient conditions for achieving agreement with probability one are obtained.

2. Preliminaries

Suppose that all agents choose their relationship with their neighbors based one their own willing and the relationship between them is cooperative at first. Moreover,we use a random processes to represent the random selection of agents to the corresponding relationships.

The signed graphGis expressed asG={V,ε,Φ(A)},whereV={υ1,...,υn}is a set of nodes,ε ?V×Vis a set of edges,A=[ai j]∈Rn×n,Φ(A)=[Yi j(t)ai j],aijis the fixed size of weight between agents. We assume thataij ＞0 if (υi,υj)∈ε, otherwiseai j=0. If (υi,υj)∈ε, then agentican obtain the information of agentj. The neighbor set of agentiare defined asNi={j|(υi,υj)∈ε}. The degree matrix ofGis defined asD=diag{d1,d2,...,dn},wheredi=∑j∈Ni aij,i=1,2,...,n. The Laplace matrix ofGis defined asL=D-Φ(A).

Definition 1A graphG(Φ(A)) is said to be structurally balanced if it admits a bipartition of the nodesV1,V2,V1∪V2=V,V1∩V2= /0, such thatφ(ai j)∈R+?υi,υj ∈Vq(q ∈{1,2})andφ(ai j)∈R-?υi ∈Vq,υj ∈Vr q/=r(q,r ∈{1,2}). Otherwise,it is said to be structurally unbalanced.

Definition 2If limt→∞|xi(t)-xj(t)|=δa.s.?i,j ∈V,whereδis a random variableP(δ ＞0)=1,the system is said to reach bipartite consensus.

Definition 3IfP{limt→∞|xi(t)-xj(t)|=0 for alli,j ∈V}=1,the agents are said to reach consensus with probability one.

Lemma 1[16,17]If the graphG(Φ(A)) is either strongly connected graph or connected graph. Then the system admits a bipartite consensus solution if and only ifG(Φ(A))is structurally balanced.

Lemma 2[16]If the graphG(Φ(A)) is structurally balanced, then there existsQ= diag{σ}withσ=[σ1,...,σn],σi ∈{±1}such thatQΦ(A)Q=A.

Lemma 3[16]If the graphG(Φ(A))is structurally unbalanced,thenλ1(L)＞0,i.e.,-Lis Hurwitz stable.

3. System model and free protocol

Since we are going to give agents freedom,the first thing we need to analyze is the decisions they might make. From Refs.[16,17],we know that agents respond to neighbor information in only two ways,that is,to get closer or to move away.This is also why the relationship between agents is divided into cooperation and antagonism.

Consider a first order multi-agent system consisting ofnagents,suppose that the dynamic of each agent is as follows:

wherexi(t),ui(t)∈Rrepresent the position and control input of the agenti,respectively.

In this paper,we propose the following control protocol:

whereYij(t) is a random variable depending on the choice made by the agenti.

RemarkIn social networks,we cannot control individuals in our society,such as robots,which does not mean we cannot limit their behavior. In this paper, suppose that all agents have the right to choose control protocols and we calculate the corresponding probability distribution.

4. Static selection

In social networks,social individuals often do not change their choices after they have identified their relationships with others,which we call the static selection. There are three situations based on the orientation of communication and the pattern they make decisions.

4.1. Single-orientation communication pattern

Single-orientation communication means that the exchange of information between agents is single orientation.Therefore, an agent receiving information from its neighbors can only unilaterally make cooperative or antagonistic decisions. Thus the graph of single-orientation communication pattern is equivalent to a special directed graph.

Supposeaijaji=0,?i,j=1,...,n,Yij(t)=Yijis timeinvariant andP(Yij=1)=pij,P(Yij=-1)=1-pij,?(i,j)∈ε,where 0＜pij ＜1 is the probability of agents choosing their protocols. Then the system equation is changed into

ProofFrom Lemma 1, the system with a strongly connected directed graph admits a bipartite consensus solution if and only ifGis structurally balanced. It follows from Lemma 2 that the system wants to be structurally balanced, it should beQ ∈∪nl=1Bl,QΦ(A)Q=A, whereBl={Q: there arelentries inσto beland othern-lentries to be-1}andA=[aij]∈Rn×n.

Note thatQΦ(A)Q=-QΦ(A)(-Q),Q=diag{σ1,...,σn},σi ∈{±1}. Hence,

Note thatQΦ(A)Q=Ais equivalent toσiaijσj=Yijaij,we have

4.2. Double-orientation communication and unilateral pattern

If the communication of information between agents is bidirectional but the choice of relations between agents is made independently, we call it double-orientation communication and unilateral pattern. In this case, although the graph appears to be an undirected graph, the existence of random parameters makes the graph equivalent to a special directed graph in nature.

Theorem 2Suppose that the undirected graphG(Φ(A))is connected. The probability of the system (2) reaching the bipartite consensus is

ProofThe first part follows from Theorem 1,we have

The proof is completed.

4.3. Double-orientation communication and bilateral pattern

If the information exchange between agents is bidirectional,and the relationship between agents is a decision jointly made by both parties, we call it double-orientation communication and bilateral pattern. In this case, the graph is also equivalent to an undirected graph.

Theorem 3Suppose that the undirected graphG(Φ(A))is connected. The probability of the system (3) reaching the bipartite consensus is

ProofThe first part follows from Theorem 1,we have

The proof is completed.

5. Dynamic selection

In a social network, the attitude of agents towards other agents is always not constant in some situations. In this section, we mainly discuss the case of dynamic selection, where attitudes between agents change randomly over time.

According to the time point denoted byh0=0,h1,h2,...,at which the agent changes its attitude.We divide the time into some nonoverlapping time slotst0-0,t1=h1,t2=h2-h1,....

It is clear thatXmax(t)is non-increasing.

Next,we discuss the corresponding probability according to the following two cases.

Case 1

There are structurally unbalanced graphs at [0,∞). According to Lemma 3 and Eq.(6),we have

The proof is completed.

6. Simulations

Example 1Here, we consider the case of Theorem 1.The interaction graph is shown in Fig.1.

Fig.1. Single-orientation communication pattern.

The experimental results are shown in Table 1.

Table 1. Simulation parameters.

According to Theorem 1, the probability of the system reaching the bipartite consensus isP1=0.375. Let us do theχ2test.

Its original hypothesisH0: there is no difference between the probability of the system reaching the bipartite consensus andP1.

Formn=24,n1=9,n2=8,n3=11,n4=6,n5=11,n6=11,n7=10,n8=9,n9=10,n10=10,the degree of freedom ism=10-2=8 and the confidence level isα=0.05,we have

Inquiring theχ2table,we note the significance of 2.78=χ2＜χ20.95(8)=15.507, which is not obvious, and we cannot reject the original hypothesisH0, the actual probability distribution is not different from the probability distribution.Therefore,our conclusion is verified.

Example 2Here, we consider the case of Theorem 2.The interaction graph is given in Fig.2.

Fig.2. Double-orientation communication and unilateral pattern.

The experimental results are listed in Table 2.

Table 2. Simulation parameters.

According to Theorem 2, the probability of the system reaching the bipartite consensus isP2=3/16=0.1875. Let us do theχ2test.

Its original hypothesisH0: there is no difference between the probability of the system reaching the bipartite consensus andP2.

Formn=48,n1=9,n2=10,n3=7,n4=9,n5=9,n6=10,n7=12,n8=10,n9=7,n10=14,the degree of freedom ism=10-2=8 and the confidence level isα=0.05,we have

Through inquiring theχ2table, we note the significance of 5=χ2＜χ20.95(8)=15.507,which is not obvious,and cannot reject the original hypothesisH0, the actual probability distribution is not different from the probability distribution.Therefore,our conclusion is verified.

Example 3Here,we consider the case of Theorem 3.The interaction graph is shown in Fig.3.

Fig.3. Double-orientation communication and Bilateral pattern.

The experimental results are listed in Table 3.

Table 3. Simulation parameters.

According to Theorem 3, the probability of the system reaches the bipartite consensus ofP3=0.25. Let us do theχ2test.

Its original hypothesisH0: there is no difference between the probability of the system reaching the bipartite consensus andP3.

Fromn=24,n1=4,n2=9,n3=8,n4=3,n5=5,n6=5,n7=4,n8=4,n9=8,n10=5,the degree of freedom ism=10-2=8 and the confidence level isα=0.05, we have

Fig.4. Dynamic selection graph.

Example 4Here, we consider the case of Theorem 4.The interaction graph is given in Fig.4.

The experimental results are shown in Fig.5.

Fig.5. One result of dynamic selection.

The results of 100 trials were consistent. Hence,we verify the correctness of the theoretical results.

7. Conclusion

In this paper,we have extended the concept of consensus to the autonomous network of agents, and the autonomy of agents is constructed with a random parameter. In the case of static selection,we could use the structure of the communication topology to calculate the probability of reaching consensus.Under the dynamic selection mechanism,a sufficient condition for consensus with probability one is given. In the future,we will analyze the combination of dynamics and statistics from another perspective. In order to make the agent in a higher degree of freedom,it is still necessary to achieve the consensus and to find the boundary of freedom.