An agreement is an arrangement between two or more entities to do something. This implies a context in which terms the agreement is developed. This paper presents a model of such agreement context as an euclidean space. On the other hand, an agreement can also be seen as a Constraint Satisfaction Problem (CSP) which solution space models an agreement space. This will allow to have a mediator that could not only model the agreement as an space, but also to check the viability of the agreement as it is being built. This mediator, that could even give some counsels about the agreement terms being formulated, is called here Counselor Agent. The protocols to interact with such agent to build an agreement are also presented.
According to the Merrian-Webster dictionary, agreement is “an arrangement as
to a course of action. Compact, treaty a: a contract duly executed and legally
binding b: the language or instrument embodying such a contract”. This
agreement, this contract, assumes or implies a context in which it is going to be
carried out. So, using a classical example by Castelfranchi [
This paper continues the work of [
So, one of the main differences between this approach and previous works
related with agreements and agents, is the focus of the approach. In works as
Contract-related agents [
The rest of the paper is structured as follows. Context Spaces are introduced in section 2. Section 3 provides a set of general definitions needed to describe the proposed protocols and algorithms. Agreement-related interaction protocols are described in section 4 and section 5 explains how the Counselor Agents works to help participant agents to reach an agreement. A simple example is shown in section 6 and, finally, section 7 summarizes this approach and concludes. 2
This term is used in the pervasive computing field related to context-aware
computing [10] [
This approach also includes a context algebra to express situations in terms of Context Spaces and to reason about such situations by means of a set of operators and calculations. The operators defined are the scalar difference (it calculates the degree of similarity between two comparable context states), and the intersection (it produces a new context space containing shared regions of values of the same attributes between two comparable context spaces).
By representing situations and system’s state as multi-dimensional objects, it is possible to generically describe and consequently reason about context of a system. A region of acceptable values is defined as a set which satisfies some predicate, hence, it can consist of any information (numerical or non-numerical) that best reflect the context attribute behavior (in terms of possible values) for the specific situation.
This section presents some generic concepts and definitions related to agreements
needed to explain the algorithms and protocols designed for a counselor agent to
guide the agreement process. A more detailed definition can be found in [
An agreement is the definition of a working context for two or more beings or entities (agents, organizations, . . . ) so that it is obtained as the result of a negotiation process.
Definition 1 (Agreement). An agreement Ag is defined as Ag = (E, Cx), where: – E = {E1, E2, . . . En} is a set of entities participating in Ag, so that ∀Ei, i = 1, . . . n, ∃!Oi = {oij }, j = 1, . . . m, ontology or set of concepts known by Ei – 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.
Universe of an agreement Ag –ADU (Ag)– is the whole set of concepts known by all the entities participating in the agreement. So, if Oi is the set of all the ontologies known by the entity Ei participating in the agreement Ag (i = 1..n), then D = {o/o ∈ Oi △ Ok, ∀i 6= k/i, k = 1..n} (the symmetric difference of all the agreement participating entities’ ontologies),1 and the ADU (Ag) is defined as ADU (Ag) = Si Oi − D.
The ADU (Ag) is formed by all the concepts that at least one pair of entities participating in the agreement Ag share (Figure 1). If this set is empty, entities have not anything in common and they can not reach any kind of agreement. 3.2
An agreement Ag has two phases: 1. 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 two levels: (a) A decision must be taken about what are the concepts around which such agreement is going to be related, that is, Cx ⊆ ADU (Ag). 1 The symmetric difference is defined as A △B = (A ∩B′) ∪(A′ ∩B), where A′ denotes the complementary set of A (b) After that, the specific terms of such agreement must be fixed, that is, the values or intervals for the concepts in Cx. 2. 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. 3.3
As it has been stated before, an agreement can be seen as the definition of a common context. As commented in section 2 an space metaphor such as the one used in Context Spaces can be used to express such contexts. So, an agreement space can be defined.
of an agreement Ag ADS(Ag) is defined by considering as a dimension (in an Euclidean space) each concept included in an Agreement Discourse Universe of an agreement Ag. That is, the ADS(Ag) is an n-dimensional space, where n is the cardinality of the ADU (Ag) (number of common terms). Figure 1 shows an example with 3 dimensions, where the points represent the possible combination values of such space (assuming a discrete domain for every dimension). Definition 4 (Agreement Space). According to the first phase of an agreement, a decision must be taken about the concepts, that is, the dimensions in which the agreement will be expressed. So, an Agreement Space is a projection of the Agreement Discourse Space onto the dimensions defining the agreement. 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, Ag)).
In order to be possible an agreement Ag, for all entity Ei participating in the agreement there will exist at least one other participating entity Ej so that dim(Ei, Ag) ∩ dim(Ej , Ag) 6= 0.
The Agreement Space is, then, the result of eliminating the unnecessary dimensions that are not relevant for the agreement. For example, in Figure 1 the y dimension is not relevant, so the way the entities will deal with y concept is not controlled by the agreement, and the Agreement Space is reduced to the marked 2-dimensional area, that is, the projection over x and z dimensions of the defined ADS.
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.
entity Ei in the agreement Ag is defined as the projection over the dimensions of interest of entity Ei in such Agreement Space. 4
WS-Agreement [
In this proposal, a Counselor Agent (see Section 5) mediates in the agreement process in order to help the participant agents to reach an agreement related to a common vocabulary. The mediation is achieved though a set of services available to all participants that help to find a common Agreement Space, inside which agents can interact being ensured that the terms of the agreement are fulfilled.
This section presents two new interaction protocols that has been defined to deal with the services offered by the Counselor Agent: ADU Definition and Agreement Counselor, that will be addressed by the ADU Interaction Protocol and the Mediated-Agreement Interaction Protocol, respectively. 4.1
This interaction protocol controls the service of the Counselor Agent related to the definition of the Agreement Discourse Universe of a group of entities, that is, the common vocabulary shared by such entities (see Definition 2). This protocol describes a general phase, previous to the agreement itself, that can be used in many other situations in which establish a common vocabulary is needed. Figure 2 shows this protocol, that is composed of the following steps: call for counsellor m j <= n not-understood k <= n - j l = n - j - k refuse agree
n failure-no-match
deadline request not-understood refuse agree
call for agreement p r <= p not-understood s <= p - r t = p - r - s refuse agree failure-proxy t inform t t p 1. An Entity Ei sends a Call For Counselor to all entities offering the service of Counselor indicating an AgreementID. 2. If any Counselor agrees to Ei, then Ei will send a Request for Counselor to one of them, Cj , that will serve as counselor for agreement AgreementID. 3. Counselor Cj sends a Call For Agreement to all entities in the system, indicating an Agreement ID and a deadline to this phase of joining to the agreement. 4. Each entity Ek that wants to participate in the agreement will send to Cj an agree message with his ontology before deadline is met. 5. After deadline, Cj will calculate the ADU using the ontologies received from the entities that will participate in the agreement, communicating them if the ADU is empty that there is a failure, because there is no possibility of agreement.
The ADU Interaction Protocol is only focused on provide a framework to participant agents for exchanging their ontologies (or fragments of them). It does not try to solve the ontology alignment problem, which is out of the scope of this paper. 4.2
After the existence of a common vocabulary is ensured by ADU protocol, the participant entities can negotiate the terms of any agreement. A two-phases protocol is proposed to reach an agreement among a group of entities (agents or organizations) mediated by a counselor. The final goal of this protocol is to construct the Agreement Space by means of the following steps: 1. Defining the context: It will be formed by the dimensions of the Agreement Space, that is, the concepts that will be dealt in the agreement, and that will be part of the ADU (in fact, this context will be a projection of the ADU in the dimensions of the Agreement Space). 2. Defining the agreement terms, that is the different values or intervals for the dimensions defining the context that will define the Agreement Space. This process will be done by applying one by one the constraints suggested by the participants. Moreover, it is regulated by a mediator—the Counselor—which guides the negotiation process to achieve an accord among the participants. Its main task is to check that any additional constraint is consistent with the current constraint set. That is, if they formed a convex hull.
The protocol here presented is described from the Counselor point of view, and, its purpose is to help in the Agreement Space definition. This protocol (see Figure 3a) is divided into two main parts: the first one deals with the definition of the context, and the second one with the definition of the agreement terms (see Figure 3b). 1. Context Definition: An initiator requests the Counselor for an agreement. (a) An Entity Ei sends a Call For Agreement with AgreementID to the Counselor Agent that has previously calculated the ADU, indicating that he wants to begin an agreement with some or all the other entities involved in such ADU. (b) If the Counselor agrees to Ei, then he sends a Call For Context to all the entities associated to the previous ADU, indicating an Agreement ID and a deadline to this phase of joining to the agreement. (c) Each entity Ek that wants to participate in the agreement will send to the Counselor an Agree message with his agreement dimensions (that is, the concepts he is interested in negotiate for the agreement, and that are part of the previous ADU) before deadline is met. 2. Agreement Terms Definition: The former initiator is turned into another participant and the Counselor takes the initiative. (a) (b) cal for agreement not-understood refuse agree
cal for context p r <= p not-understood
p s <= p - r refuse t = p - r - s agree proxied-communicative-act reply-message agreement terms subprotocol
Participant i inform-context p cal -for-terms p
p inform-term [¬consistent] reject (a) The Counselor Informs to all the entities of the dimensions of the agreement (from the general ADU, different concrete agreements could take place, between different or the same entities). (b) The Counselor sends a Call For Terms message to all the participating entities with the proper AgreementID to ask for agreement terms. (c) Each one of the participating entities will send an Inform message to the Counselor for each one of the negotiation terms (in the form of a constraint) that he is interested in. Such messages will be processed by the Counselor to build the AS. (d) For each Inform message, the Counselor will respond either with a Reject message, if the new term is not consistent with the agreement or is redundant, or with an Accept message if the new term is consistent. (e) The process of receiving and analyzing new agreement terms continue till there is no more terms (according to a deadline-based method). (f) The Counselor informs the participating entities either the final agreement terms, or that the agreement has not been possible.
The final result is the definition of the Agreement Space, modeled as a hyperpolyhedron formed by all accepted constraints (agreement terms). During the execution of the agreement, all interactions have to be inside this space as the participants have agreed.
It is not so strange, when trying to reach an agreement to use a mediator to,
not only watch over the fulfillment of the different processes involved in reaching
an agreement, but also to counsel about the final values or intervals of the
agreement due to its global unbiased view of the agreement. So, this figure is
also interesting when trying to automatize the agreements, that is, to carry out
agreements between agents, virtual organizations or other pieces of software.
Different approaches to automatic mediators can be seen in the literature such
as the PERSUADER system [12] or AutoMed [
As it was stated before, after the Agreement Space is defined, the different entities involved in the agreement must fix (possibly through a negotiation process) some concrete values or intervals for the different dimensions comprising the Agreement Space. For such negotiation, each one of these entities will have some intervals of satisfying values for the different dimensions it is interested in. These satisfying intervals may be expressed as constraints for the different dimensions that should be satisfied for the agreement. So, if this first phase of an agreement is seen from a mediator point-of-view, it can be seen as the solution of a Constraint-Satisfaction Problem (CSP), defined by the whole set of constraints of the different entities. Being the Agreement Space n-dimensional, each one of such constraints defines a (n − 1)-dimensional plane. As the Agreement Space is defined by the intersection of all such planes, it can be described how such space is by studying such planes. Therefore, this agreement mediator should be able to detect if an agreement is possible, checking if there exists an Agreement Space as a result of all these constraint planes intersection.
The idea is to define the Agreement Space as the solution space of a CSP and to build an agreement by applying entities’ conditions as constraints in the space (applying the HSA 6= [11] algorithm to build the hyperpolyhedron modeling the CSP that will define the Agreement Space). A solution is reached if all constraints are consistent. Furthermore, if the resulting space is convex then it can be ensured that all interactions are inside the Agreement Space.
As it is an agreement, an Agreement Space (AS) is defined by a set of entities and their context (E, Cx), where the context is composed by variables, their domains an all the constraints. In this way, the AS is defined by extending a common CSP definition. 5.2
The Counselor has the responsibility of helping the participants in the agreement to find the Agreement Space, considering it as a CSP. It is an iterative process that adds new constraints one by one, guaranteeing that the new constraint is consistent with the previous ones. Constraints are inequalities of the form Pin=0 aixi ≤ b, where xi are the variables of the CSP. The set of all constraints defines an hyperplane and which union defines the limits for the valid values for all the variables involved in the agreement. The participants in the agreement will take values inside the resulting hyperpolyhedron.
Using the mediated-agreement protocol defined in Section 4.2, the Counselor obtains the constraints from the participants and creates the Agreement Space using a variant of HSA 6= algorithm. This algorithm is applied inside the Agreement Terms Definition subprotocol (see Figure 3b) each time a new constraint Ci is received from a participant (by means of an Inform message). So the Agreement Space is incrementally constructed from scratch.
If Ci is inconsistent or redundant, the agent that proposed it is informed by a Reject message. The agent can redefine the constraint and submit a new one if necessary.
Consistence and redundancy are checked using the HSA 6= algorithm. Basically, when a new constraint Ci arrives the algorithm checks if each vertex of the current hyperpolyhedron satisfies Ci. If none vertex satisfy Ci then the constraint is inconsistent and it is rejected. That is because the space defined by the constraint does not contain any of the vertex of the hyperpolyhedron. On the other hand, if all vertex satisfy Ci then the constraint is redundant. That is because the complete hyperpolyhedron is included inside the space defined by the constraint. In any other case, the constraint is consistent and it is added to the hyperpolyhedron.
When all constraints are added to the Agreement Space and it is not empty then there is an agreement among all the participants. If the Agreement Space is not empty, then it is ensured that it is convex, so any ’movement’ between two points inside this space is always inside it. Therefore, it is guaranteed that any negotiation process produced inside the agreement terms will never violate the agreement.
The following section presents an example of reaching an agreement using a Counselor Agent, interacting with the above presented interaction protocols, focusing in the Agreement-terms definition subprotocol. 6
Let it be a set of agents interested in taking piano classes. The group is formed by one teacher and two students. They agree to negotiate over three dimensions: the number of classes (n), its duration (d) and its price (p). Initially, participants have their own preferences (modeled as constraints).
– Teacher 1. at least 10 classes: n ≥ 10 2. duration between 60 and 120 min: d ≥ 60 and d ≤ 120 3. at least 20 euros/hour: p ≥ 20 – Student 1 1. no more than 20 classes: n ≤ 20 2. less than 30 euros/hour: p ≤ 30 – Student 2 1. minimum 15 classes: n ≥ 15 2. duration between 45 and 90 min: d ≥ 45 and d ≤ 90
Assuming that agents have some common vocabulary (checked with the ADU protocol) and they defined the above three dimensions as the agreement context, then the Counselor asks them for the terms of the agreement. There is no rule about the order in which agents propose the terms (constraints) nor the order in which they arrive to the Counselor. Depending on it, one constraint can be detected as redundant or just as a refinement of an existing one. But it does not affect to the final Agreement Space.
Agent Mess 1 C inform 2 C call-for-terms 3 T inform 4 C accept 5 C call-for-terms 6 S1 inform 7 C accept 8 C call-for-terms 9 S2 inform 10 C accept
Param Agent Mess n, d ,p 11 C call-for-terms
12 T inform n ≥ 10 13 C accept n ≥ 10 14 C call-for-terms
15 S1 inform p ≤ 30 16 C accept p ≤ 30 17 C call-for-terms
18 S2 inform n ≥ 15 19 C reject n ≥ 15 20 C call-for-terms
Param Agent Mess
21 T inform d ≥ 60 22 C accept d ≥ 60 23 C call-for-terms
24 T inform n ≤ 20 25 C accept n ≤ 20 26 C call-for-terms
27 S2 inform d ≥ 45 28 C accept d ≥ 45, red 29 C inform-done
Param d ≤ 120 d ≤ 120 p ≥ 20 p ≥ 20 d ≤ 90 d ≤ 90
This is a very simple case, in which restriction are defined over one dimension, but it is enough to follow and understand the process of construction of the Agreement Space. Let be C the counselor, T teacher, S1 student 1 and S2 student 2. An example of the process can be followed in Table 1. In the sequence of messages on this table it can be seen how the Counselor communicates to the rest of participants the context of the agreement (message 1). After that, the participants send their own constraints one by one (messages 3, 6, 9, 12, 15, 18, 21, 24 and 27) and the Counselor accepts or rejects them. For example, in message 18, S2 proposes a constraint that is redundant, since one more restrictive has been accepted in 12-13. But restrictions proposed in messages 15 and 27 have been accepted because they refine (they are more restrictive) that the ones accepted in 6-7 and 21-22 respectively. 7
Context Spaces seem to be a valid approach to model agreements and allows to use well known techniques to solve the task of reaching an agreement and controlling its subsequent execution. The agreement is modeled as an object in the Euclidean space.
The problem of defining the space associated to an agreement can be seen as a CSP, since the agreements conditions can be modeled as constraints and the agreement is expressed as a set of restrictions over a set of data. The conjunction of all these restrictions will define an convex hyperpolyhedron delimiting the agreement space, that is, the space where all the computations fulfilling such agreement will be carried out, the context of such computations.
Mediators can be used during the negotiation process to reach an agreement to check that any additional constraint keeps this space convex, along with controlling the feasibility of the agreement. For doing that, mediators can suggest more relaxed or more strict constraints in order to maintain the consistence of the space and the possibility of an agreement.
This paper has presented not only the advantages of using such a Mediator or Counselor in reaching an agreement, but also the way this Counselor works and how to interact with him by means of some interaction protocols specifically designed for agreement reaching processes.
As future work, the dynamic of the agreement is going to be studied, because to guarantee an agreement, besides the existence of the agreement space, the convergence of individual negotiation processes has to be guaranteed to avoid systems that oscillate without ending in a concrete agreement for some initial situations. Association (HP-OVUA), 12th Workshop, Porto, Portugal (FEUP), 10 - 13 July 2005, 2005. 10. A. Padovitz, S. W. Loke, and A. Zaslavsky. Towards a theory of context spaces.
In Workshop on Context Modeling and Reasoning (CoMoRea), in C Das and M Kumar (eds), Proceedings of the Second IEEE Annual Conference on Pervasive Computing and Communications Workshop, Orlando Florida, 14 - 17 March 2004, pages 38–42, USA, 2004. IEEE Computer Society. 11. M. A. Salido, A. Giret, and F. Barber. Constraint satisfaction by means of dynamic polyhedra. In Operational Research Proceedings 2001, pages 405–412. Springer Verlag, 2001. 12. K. P. Sycara. Resolving goal conflicts via negotiation. In Proceedings of AAAI-88, pages 245–250, 1988.