If a set of agents tries to reach an agreement, there will exist an Agreement Space that models the maximum valid space according to the individual constraints of each agent, regarding the terms of the agreement. Previous approaches to Agreement Spaces model them by means of a Counsellor Agent that will help to agents trying to obtain an agreement knowing all the possible terms in that agreement, and monitoring such Agreement Space as it is being built. But, what happens when there is no Counsellor Agent? Is there any way of modeling such space in a distributed way by the different agents trying to achieve such agreement? This paper presents a possible solution to that question using a Consensus Network to build such Agreement Space, allowing to know if there are possibilities to achieve an agreement or not.
Nowadays, there is a growing interest in the Multi-Agent Systems (MAS) area
regarding concepts about cooperation such as Consensus, Commitments,
Contracts, or Agreements. All these concepts are related, but it is necessary to clarify
in some way such relation. A Consensus is the negotiation of a value in one term,
including the final decision where all the negotiation parts agree in the value.
A Commitment or, more concretely, a Social Commitment [
When a set of agents try to reach an agreement, if such agreement is possible,
there will exist an Agreement Space [
The internal structure of many biological, social and economic systems
displays complex topological properties such as clustering, a scale-free degree
distribution and the presence of degree correlations, which are not reproduced by
simple random graph models [
The objective of this paper is to present a way of modeling such space in a distributed way by the different agents that are trying to achieve such agreement by means of a Consensus Network, allowing them to know if there are possibilities to achieve an agreement or not. Just to show the validity of the present approach, a market-based case of study is presented, with some interesting results when applying this proposal.
The rest of the paper is structured in the following way: the next section presents some related work, regarding agreements and consensus networks. After that, the modeling of Agreement Spaces by Consensus Networks is presented. The following section presents a case of study regarding right–based markets. Last, some conclusions are commented. 2
Looking for a common space where agents can interact can be analyzed as a constraint satisfaction problem. Different strategies to solve this kind of problems have been widely studied in the last years. Two of these techniques are commented in the rest of this section. 2.1
One of the most promising ones are Distributed Constraint Optimization
Problems (DCOP) [
As [
The theoretical framework for solving consensus problems in dynamic networks
of agents was formally introduced by Olfati-Saber and Murray [
Let G be a directed graph of order n with the set of entities E as nodes and weighted adjacency matrix A = [aij ]. Let (G, X ) be the state of a network with value X and topology G, where X = (x1, . . . , xn)T ∈ Rn, where xi is a real value associated with the node Ei. The value of a node might represent physical quantities measured in a distributed network of sensors (temperatures, voltages,. . . ), or also quantities of interest in a network of buyer’s and seller’s in the market (prices, rights, quality,. . . ). A network is a dynamic system if (G, X ) evolves in time. A consensus algorithm is an interaction rule that specifies the information exchange between the agents and all of its neighbors on the network in order to reach the agreement. Consensus of complete network is reached if and only if xi = xj ∀i, j. Distributed solutions of consensus problems in which no node is connected to all nodes are especially interesting. The most commonly used consensus protocols are Average, Maximum and Minimum because the have broad applications in distributed decision-making multi-agent systems.
These authors have demonstrated that a convergent and distributed consensus algorithm in discrete-time can be written as follows: xi(k + 1) = xi(k) + ε
X (aij (xj (k) − xi(k))), j∈Ni (1) where Ni denotes the set formed by all nodes connected to the node i (neighbors of i). The collective dynamics of the network for this algorithm can be written as
X (k + 1) = Px(k) (2) where P is the Perron matrix of a graph with parameter ε, defined as P = I −ε L, with I is the Identity matrix, ε is the step size, ε > 0, and L is the Laplacian matrix, L = D − A, that is the difference of the degree matrix D and the adjacency matrix A of the graph. The algorithm converges to the average of the initial values of the state of each agent and allows computing the average for very large networks via local communication with their neighbors on a graph.
Solving consensus is a cooperative task because if a single agent decides not to cooperate and keep its state unchanged all others asymptotically agree with them. However, if there are multiple non cooperative agents then no consensus can be asymptotically reached. When an agent does not cooperate with the rest its links in the network might be disconnected in order all others will asymptotically agree. In this case it is impossible for all agents to reach an agreement but is possible to reach an agreement for the rest of the agents. 3
In this section, some definitions regarding Agreement Spaces and what is an agreement process are presented, along with how can be used a consensus network to quickly determine if it will be possible to arrive to an agreement. That is, if there exist an agreement space between the agents involved. 3.1
In order to deal with Agreements [
Definition 1 (Agreement): is defined as Agr = (E, Cx), where: (i) E = {E1, E2, . . . En} is a set of entities participating in the agreement Agr, so that ∀Ei, i = 1, . . . n, ∃!Oi = {oij}, j = 1, . . . m, the ontology known by Ei; and (ii) Cx = {(cxo, cxIo)|cxo ∈ Si Oi, cxIo ⊆ Do}, where Do is the domain of the ontology term cxo. Thus, this context is formed by a set of ontological terms cxo with its corresponding set of valid instances cxIo that have been agreed by E.
Definition 2 (Agreement Space of an agreement Agr –AS(Agr)–): That is, this space will be defined by the features the different entities Ei making the agreement are going to negotiate (Cx), each one of such features defining a dimension in this space (∀i : di ∈ dim(Ei, Agr)).
In order to be possible an agreement Agr, for each entity Ei participating in it there will exist at least one other participating entity Ej so that dim(Ei, Agr)∩ dim(Ej, Agr) 6= 0.
Definition 3 (Agreement Process): As it has been stated before, an agreement has associated a wide and complex process comprising several different phases: 1. Calculating the ADU (Agr): that is, to calculate the common ontology shared by all the agents interested in the agreement. Associated to this ADU (Agr) will exist the corresponding ADS(Agr). 2. Reaching an agreement (defining the agreement context Cx): It comprises the negotiation process between two or more entities (belonging to E) to reach an agreement. In fact, it is decided in three levels: (a) Definition of the AS Dimensions: a decision must be taken about what are the concepts around which such agreement is going to be related, that is, Cx ⊆ ADU (Agr). Or, if the concepts are considered as dimensions, decide the dimensions in which the agreement will be expressed, that is, define the Agreement Space dimensions as a subset of the existing ADS(Agr) dimensions. (b) Definition of the own AS: it is checked if it is possible to reach an agreement by calculating if there exists an AS, identifying both the concrete boundaries of such space and the entities involved, because at this level, entities may abandon the process if they disagree on the specific space boundaries. (c) Reaching the concrete agreement: the specific terms of such agreement (the values or intervals for the concepts in Cx) must be fixed, that is, the satisfying values or intervals for each one of the different dimensions comprising the AS(Agr). 3. Agreement execution: In this phase each entity must fulfill the accomplished agreement executing the needed actions or calculus according to the context defined by such agreement. This execution could not even imply any kind of additional coordination.
In this way, the outcome of the first phase of the agreement will be the definition of this Agreement Space, fixing the satisfying values for each one of the different dimensions comprising this space. The second phase of the agreement will be to carry out the execution of the agreement taking into account that it has to be carried out inside the previously defined Agreement Space. 3.2
This section presents the application of consensus networks to assure, in a distributed fashion, that there are possibilities to reach an agreement between the involved agents, that is, to assure that there is an Agreement Space. In this way, following the Agreement Process presented in Definition 3, this Consensus Network will be used to check that it is possible to carry out b and c levels of the second phase of such process. That is, in the phase where the agreement is reached, after the dimensions of the Agreement Space has been fixed, the Consensus Network will calculate that there exists an Agreement Space, being possible to reach an agreement calculating the specific terms of the different dimensions (values or intervals).
The process of Agreement Space’s boundaries calculation may be defined in two different ways: 1. Unlimited: it continues till the boundaries of the AS are defined or it is not possible to define an AS between any two different entities. In this case, both 2.b and 2.c levels of the agreement process are carried out by the Consensus Network. 2. Limited: it is possible to define different limitations to the process: (a) A deadline. (b) A minimum number of participant entities, so during the process when too much entities abandon it, the process will end saying that it is not possible to define an Agreement Space. (c) A maximum number of interactions or messages. (d) A minimum length of an AS dimension.
In this way, the Consensus Network is only in charge of the level 2.b of the Agreement Process. 3.3
Based on the basic model of consensus network of Section 2, a complete model useful to define Agreement Spaces has been defined.
Let (G, X) be the basic model, where G is a network and X the values of the nodes for the consensus variable x. Both, the network and the values, evolves with time, so we define the consensus problem as (G(t), X(t)): a consensus network with switching topology, meaning that the structure of the network change along with the agreement process. In the general case, this switching can be model through the adjacency matrix A = [aij]. In out case, this matrix is divided in two components: the first one refers to the existence of a link between agents i and j (as usual). The other component is a weight that represents the strength of the link between both agents. This weight can be use to model many different things depending on the application domain: centrality measures, importance, reputation, trust, and so on. Le W = [ωij] this weight matrix. Then,the component that can change with the time can be A, W or both. xi(k + 1) = xi(k) + ε X ((ωij(k)aij (k))(xj (k) − xi(k)),
j∈Ni
In the construction of the Agreement Space, only some changes in the topology are allowed. Specifically, agents can leave the agreement process if it is out of the agent’s bounds. No agent can be incorporate to an agreement in process. We do not consider the possibility of creating new groups that evolve independently of the original group either.1
Each agent has its own utility function to determine if it stays in the agreement process or if it leaves it. Then, a permanence function can be defined as ui(x) for each agent i.
aij(k + 1) = 1 if ui(xi(k)) ≥ 0 0 otherwise So the switching nature of the network can be captured and included in the model as a function of the current calculated value of the consensus dimension and the expected utility value for the agent. Including this utility function ui, the resulting consensus problem can be modeled as (G(t), X(t), U ), where – G(t) is a network with switching topology, 1 This case can be considered as two independent consensus problems and the same model can be applied to each isolated group, without considering any kind of transference of agents or information among them. (3) (4) – X (t) = {x1(t), . . . , xn(t)}T is the vector of values for the agreement dimension (consensus variable), and – U = {u1(x), . . . , un(x)}T is a vector of the utility functions for each agent. The dynamic of the agreement is defined by Equations 3 and 4.
If the network contains one connected component (see Figure 1) then the convergence of the method is ensured. The result is an agreement about the value of the negotiated parameter. But it is possible that, if one or more agents leave the agreement process, the network is segregated in two (or possibly more) independent networks, each one of them eventually reaching their own agreement. For example, Figure 2 shows the effect of a node that leaves the agreement process in a very early stage. 4 4.1
Networks allow to model interactions when certain agents are not aware of each other by informational, regulatory or physical reasons. In particular this paper is focused in some kind of markets in which price, supply and demand should be previously balanced (agreement space) before negotiations begin. There exist markets in which some regulations are required and also the topology of the network induced by the internal relationships must be considered.
In order to verify that the proposed framework is adequate to generate the required initial data sets different repetitions are randomly generated using the previously specified probability distributions of agents, rights, optimal rights and prices. This framework of data generation is more similar to Montecarlo models.
Suppose rights price must be fixed in the market (a constraint) and some previous agreements, acceptable by the maximum number possible of agents, are required in order to establish this value. The average of the prices Pi is probably one the most acceptable agreement value for the price, and also can be calculated asymptotically using consensus algorithms. Dynamics of agents are defined by the following equations:
PiS (k + 1) = PiS (k) + ε PiB(k + 1) = PiB(k) + ε
X (Bj (PjB (k) − PiS(k) + Ci(k))), j∈Ni
X (Sj (PjS (k) − PiB(k) + Ci(k))) j∈Ni where k is the discrete time and the index S and B denotes seller and buyers respectively. The added term Ci(k) is proportional to rights bought and sold by agents in each iteration, and is calculated as follows: where δ > 0.
Pj∈Ni Bj Ci(k) = δ · Pj∈Ni Sj (5) (6) (7) Fig. 1. Agreement process when the complete group is connected. All the agents reach a consensus about the value exchanging information with their neighbors. They do not know the structure of the network nor any other global information.
Agreement process with separate communities 50
100 iterations 150 200
Seller agents adapt iteratively prices in order to converge to the mean price of the connected buyer agents and simultaneously buyer agents adapt their prices in order to converge to the mean price of the connected seller agents. In this iterative process non cooperative agents are disconnected of the network in order all others agents to have the possibility of asymptotically agree. The algorithm converges and stops when prices converge to the consensus value the mean prices of buyers and sellers are approximately equal.
In order to include the topology of the networks, the scale-free network
models (SFN) have been considered [
The scaling exponent γ is a constant whose value is typically in the range
2 < γ < 3. A framework which enables generate scale-free networks of buyer and
seller agents has been developed in Matlab. The purpose of this framework is not
simulating real and complex markets but only analyze the possible application
of consensus algorithms in these problems. The Lev Muchnik’s package [
The number of agents N (number of nodes in the network) and the scaling exponent γ are input parameters in the experiments. In some experiments the networks considered are “all connected” and then γ = 0.
The networks generated for this paper are undirected (edges have no orientation) and adjacency matrix is symmetric. Once this network has been generated the rights must be generated and distributed between the agents. The Number of Rights R is an input parameter of experiments:
R =
X i=1,...,N
Ri (8) (9) where Ri are the number of rights of agent i. Rights are randomly generated and distributed between the N agents. Uniform distribution of rights is used in the simulations.
In order to simulate the roles of the agents in the market (buyers, seller and agents not interested in the market) the “optimal rights” of an agent Rei are defined as the number of rights this agent would have. The comparison between Rei and Ri allows to establish the role of agent i in the market: – If Rei = Ri then the agent i is not interested in the market. – If Rei > Ri then the agent i would buy (Rei − Ri) rights (Buyer). – If Rei < Ri then the agent i would sell (Ri − Rei) rights (Seller).
The Number of Optimal Rights Re is an input parameter of experiments: Re =
X i=1,...,N
Rei The optimal rights Re are also randomly generated and uniformly distributed among the N agents. Similar values of Rights and Optimal Rights represents markets where supply and demand is in equilibrium. In this paper only these “equilibrated markets” (R ≃ Re) are considered in the experiments. Once the agent roles have been established only buyers and sellers are considered in order to estimate the agreement space. Agents not interested in the market are deleted of the network. For this reason some buyers and sellers could be disconnected of the network when an agent is deleted. Disconnected agents are also deleted of the network iteratively until all agents are connected with others. The result is a bipartite, undirected graph, where buyers are connected with sellers.2 2 The general case where agents of any type are connected each other has no effect on the behavior of the algorithm and barely affects to the convergence time of the method.
The next step is generate the initial prices each agent would pay (if is a buyer) PiB or receive (if is a seller) PiS in order to buy or sell rights in this market. These prices are randomly generated using normal distributions. The mean and standard deviation of the buyer and seller prices distributions are input parameters in experiments.
In our framework agents are allowed to leave the network when the consensus price is out of their acceptable boundaries. In order to simulate price boundaries an additional parameter is included in the model, the limit price for agent i (LPi):
LPi = Pi ∗ (1 ± Fi) (10) Where Fi values are randomly generated in the interval [0, 0.5] using an uniform distribution and the sign (+ or -) depends if the agent is a buyer or a seller. Boundaries prices for agents are included in the interval [Pi, LPi].
Once initial data sets are generated then the consensus protocol (see Eq. 6) can be computed in order to obtain when the consensus price is possible. An additional restriction of the proposed simulation framework must be clarified: agents must necessarily adapt their prices in each iteration of the consensus algorithm because this algorithm only converges when all agents collaborate in the process. 4.2
The initial parameters of all experiments presented in this paper, except the scaling exponent γ, are the same those discussed previously (see Table 1). These experiments show that in general, the number of initial buyers and sellers, and the corresponding selling and buying rights are similar (supply and demand is in equilibrium) and also that initial prices are distributed around the initial mean values (parameters of the simulation). A more detailed analysis of these results shows that seller and buyer price distributions are not normal but this factor is not important in our experiments, the only one important is to be able to generate data sets adequate for our experiments.
Different conditions and parameters (see tables 2 and 3) are combined and analyzed in the proposed experiments: – ε and δ (learning parameters) of consensus algorithm used as λ = δ ∗ ε. – Epoch: number of iterations: 50, 100 and 200. – The scaling exponent γ of the network distribution: γ = 0.0 (complete network) and γ = 2.0 (scale free network).
– β: agents are allowed to leave the network when β = 1.
Experiments Set 1 The results obtained in these experiments (1A and 1B) are summarized in Table 4. When β = 0 agents are not allowed to leave the network and therefore the number of consensus agents and rights are the initial ones (if a consensus is reached, it has to be by all the agents beginning the process), and the “consensus price” is the mean of all initial prices. When β = 1 agents are allowed to leave the network if price (k) is out of their boundaries, and therefore the number of “consensus agents and rights” may be lower than the ones that initiated the process. Particular consensus value depends of initial simulation parameters.
When λ = 0, the additional term in the equation of consensus (see Eq. 7) is not considered, and simulations show that final supply and demand rights are unbalanced. The lowest value of rights limits the “possible agreement space”. However when λ > 0 this additional term tends to balance supply and demand rights, and the obtained equilibrium value is higher than the lowest value obtained when λ = 0. Therefore the “possible agreement space” is better. Experiments Set 2 The basic difference with experiment 1 is that the input scaling exponent γ 6= 0 and, therefore, scale free networks are considered. The results obtained in these experiments (2A and 2B) are summarized in Table 4. The proposed framework excludes explicitly not connected agents before consensus algorithm starts, and for this reason the initial date set (number of agents with the roles of seller or buyer and their corresponding rights) is minor than previous experiment (all connected network). These results are very similar to previously obtained when γ = 0 (all connected networks) except for the slightly higher variances see Table 5). However a detailed analyses of this experiments show than the simultaneous combination of scale free networks (γ > 0) with the possibility agents can leave the network when the price is out of their boundaries (β = 1) sometimes does not converge. Some simulations have been chosen to show the behavior of the network to achieve a decision. The algorithm converges and stops when the mean prices of buyers and sellers are approximately equal.
– The simplest case (Figure 3, row 1) is a complete graph where all the agents are forced to stay and reach a consensus value. This experiment shows that the number of exchanged rights remains constant (because no agents leave the system), but there is a difference between the desired rights and the offered rights. The modification of the basic algorithm solves this problem by introducing a second factor, represented by the Ci(k) term and analyzed in the λ parameter. – In the experiments 1A and 1B (Figure 3, row 2), besides the adjustment between the involved rights, agents are allowed to leave the system if the terms of the negotiation (the consensus value for the price of the rights) is out of its bounds. In this case, the number of rights decreases while the consensus evolves. Nevertheless, the offer and the demand are biased (see how the lower lines matches in the upper graphic). – Finally, in the experiments 2A and 2B (Figure 3, row 3) a scale free network is used instead of the full connected graph. Furthermore, the initial price distribution is different too. In this case, the network does not converge to one unique value. The topology just affect to the speed of the convergence. But when an agent leaves the consensus it can split the network apart. This fact prevents the hole group to reach a common consensus value, because each isolated group converges to their own consensus value and they never receive the values agreed by the other group. The result is that, instead a unique consensus value, there are as many as isolated groups. This can be seen in Figure 3, where the prices do not converge. Anyway, the values of the prices stabilizes. In this case, instead of a final agreed value, a range is found. This fact allows to identify which agents are interested in the agreement and the range of prices. After this process, some other techniques can be used to find an agreement. Then, the consensus network can be used at least to identify the subset of participants interested in reaching and agreement and the boundaries of such an agreement. 5
This paper shows the application of consensus networks to model agreement spaces for virtual organizations in a distributed and self-organized fashion. The results obtained show that this approach seems to be valid and it has been applied to a rights-based markets (such as water, electrical or stocks) in order to check its viability in real-world problems.
Consensus networks are used to check the existence of an Agreement Space among a network of agents. If such space exists, then an agreement is possible and the involved agents can obtain the concrete terms of such agreement using different approaches that are out of the scope of this paper.
The topology of the networks has been introduced in the consensus and its influence has been tested.
When scale-free networks are combined with the possibility of agents to leave the system provokes that the convergence is not guaranteed, as some experiments have shown. This will be object of a more deep study in the future.
An experimental framework has been created in order to simulate the behavior of the consensus algorithm varying fundamental parameters such as the number of agents, the topology of the network, some learning adaptive parameters and the effects that the kind of Agreement Space boundaries calculation process has in the performance of the system.
As additional future works, we want to apply this approach to a real environment, where topological, dynamics and multidimensional factors have to be taken into account.
This work is supported by TIN2009-13839-C03-01 and PROMETEO/2008/051 projects of the Spanish government, CONSOLIDER-INGENIO 2010 under grant CSD2007-00022, and PAID-06-11-2084.