Assessing communication strategies in argumentation-based negotiation agents equipped with belief revision 1

Abstract

The importance of negotiation has increased in the last years as a relevant interaction to solve conflicts in multi-agent systems. Although there are many different scenarios, a typical negotiating situation involves two cooperative agents that cannot reach their goals by themselves because they do not have some resources needed to reach such goals. Therefore, a way to improve their mutual benefit is to start a negotiation dialogue, taking into account that they might have incomplete or incorrect beliefs about the other agent’s goals and resources. The exchange of arguments during the negotiation gives them information that makes it possible to update their beliefs and consequently they can offer proposals which are closer for reaching a deal. In order to formalize their proposals in a negotiation setting, the agents must be able to generate, select and evaluate arguments associated with such offers, updating their mental state accordingly. We situate our work on this kind of scenarios with two argumentation-based negotiation agents equipped with belief revision operations in the generation and interpretation of arguments. It has been proved that those agents that take advantage of belief revision during the negotiation achieve an overall better performance. Because the belief revision process depends on the information the agents exchange in their utterances, in this paper we focus on different communication strategies the agents may implement and the impact that they have in the negotiation process. For this purpose, we present a negotiation protocol where the messages are extended to include a critique to the last proposal received and a counterproposal. Also, we define proposals that may be more or less informative containing different justifications. An intentional agent architecture is proposed and following this model different kind of negotiating agents are created using diverse communication strategies. To assess the impact these strategies have in the negotiation process some simulations are conducted, analyzing the results obtained.

1. Introduction

In systems composed of multiple autonomous agents, negotiation has proven to be a relevant form of interaction that enables two or more agents to arrive at a mutual agreement regarding some belief, goal or plan [17]. A typical scenario for negotiation involves two agents who have the need to collaborate for mutual benefit. Even though there is no agreed approach to characterizing all negotiation frameworks, it has been argued [17] that automated negotiation research can be considered to deal with three broad topics: Negotiation Protocols (the set of rules that govern the interaction); Negotiation Objects (the range of issues over which agreement must be reached) and the characterization of an Agents’ Decision Making Model (which accounts for the decision making apparatus the participants employ to act in line with the negotiation protocol in order to achieve their objectives).

Moreover, different approaches can be used to model negotiation in a multiagent (MAS) setting. In particular, three different kinds of approaches are usually distinguished: those which are game-theoretic [28], those which are heuristic-based [13], and finally those based on argumentation (argumentation-based negotiation or ABN for short). In this work we focus on the argumentation-based negotiation approach [4,10,20,25,26,31] that combines in a sound way several relevant aspects associated with representing the agents’ knowledge, assessing the strength and trust of their claims, tracing the exchanges of utterances in a negotiation dialogue, etc. (see e.g. [2,5]). In particular, ABN allows the negotiating agents not only to exchange offers but also reasons that support these offers in order to mutually influence their preference relation on the set of offers, and consequently the outcome of the dialogue. Moreover, as the agents that negotiate usually have incomplete beliefs about the others, the exchange of arguments gives them information that makes it possible to update their beliefs.

As [26] exposed, in order to formalize their offers in a negotiation setting ABN agents must be able to generate, select, interpret and evaluate arguments associated with such offers, updating their mental state accordingly. Also, they proposed the following set of principal components for the ABN architecture. The locution interpretation component parses incoming messages. These locutions usually contain a proposal, or an acceptance or rejection message of a previous proposal. The proposal evaluation and generation component makes a decision about whether to accept, reject or generate a counterproposal, or even terminate the negotiation. The locution generation component sends the response to the relevant party. The argument interpretation component updates the agent’s mental state accordingly. Finally, the argument generation mechanism is responsible for deciding what response to actually send to the counterpart and what (if any) arguments should accompany the response.

Our research is based on an ABN model which involves two cooperative agents. We will assume that each agent is benevolent (he will always try to do what is asked for if he is able to do so) and truthful (i.e., he will not knowingly communicate false information). Besides, we will assume that both agents cannot reach their respective goals by themselves, so that they have to ask for help from one another. The agents can thus exchange different resources, including the knowledge associated with possible plans to reach their goals. The resulting negotiation dialogue is composed of an exchange of proposals, where every proposal adopts the form of an argument whose claim is a possible exchange (which are the resources the agent is asking for and what he is willing to offer in return). As the agents initially may have incomplete or incorrect beliefs about the other agent’s goals and resources, during the negotiation process they update their beliefs and consequently, their mental state, according to the arguments exchanged. Thus, in the context of the ABN framework previously described, we will follow the belief revision approach for both argument interpretation and argument generation proposed in [24], where we analyzed the impact of including belief revision for improving the overall negotiation process.

Besides the importance an agent must give to the incoming information through the received messages in a negotiation process, we want to explore the relevance of the information an agent communicates to his counterpart. In order to do this, in this work we extend the original negotiation model proposed in [24] allowing the agents to exchange more informative messages. An agent’s illocutions may now also include a critique (in addition to a proposal), resulting in a more complex argument that can support the proposal exchange (justifying the demand, the offer or both). As a consequence, different kinds of agent may be defined using different communication strategies. These strategies will help the agents determine what information to include in their utterances: an agent may be more or less communicative, giving an explanation of why he is not willing to accept a proposal (i.e., a critique) or explaining the reason of the proposed solution. Different simulations are conducted to show the impact that these communication strategies have in the negotiation process. Information transfer efficiency is assessed in terms of the overall usefulness, quantity of information disclosed and negotiation duration.

Motivational example. For the rest of this article, we will work on a slightly modified version of the well-known Home Improvement Agents Problem ( $\mathit{HIA}$ ) as a motivational example [20]. We will assume that ${\mathit{Ag}}_1$ and ${\mathit{Ag}}_2$ are truthful and benevolent agents. Agent ${\mathit{Ag}}_1$ has as a goal hanging a picture, and it has a screw and a hammer. Also, he knows how a hammer and a nail can be used to hang a picture and how a screw and a screwdriver can be used to hang mirrors. ${\mathit{Ag}}_1$ believes that ${\mathit{Ag}}_2$ has a nail and a screwdriver (a correct, but incomplete belief) and he believes that ${\mathit{Ag}}_2$ knows how to repair a desk using a screw and a screwdriver (incorrect belief). Finally ${\mathit{Ag}}_1$ believes that ${\mathit{Ag}}_2$ ’s goal is to repair a desk (incorrect belief). On the other hand, Agent ${\mathit{Ag}}_2$ has as goal to hang a mirror, and it has a nail, a screwdriver and the knowledge of how to hang a mirror using a hammer and a nail. Also, he believes that ${\mathit{Ag}}_1$ has a screw and the knowledge of how to hang a picture using a screw and a screwdriver (incorrect beliefs). Neither ${\mathit{Ag}}_1$ nor ${\mathit{Ag}}_2$ can reach their goals on the basis of their knowledge and resources. Consequently, they need to perform some exchanges in order to do so.

Our proposal aims at modelling how such exchanges can be determined by combining belief revision and communication strategies in an argumentation-based negotiation approach. In particular, our proposal relies on the characterization of belief revision operations to model the agent’s argument generation, where claims are part of the resources to be exchanged.

The remainder of this paper is structured as follows: in Section 2 we define the negotiation objects and protocol and in Section 3 the agent architecture is modeled. Then, in Section 4 we formalize the agent’s utterances and its components, also we define the notions of solutions and deal. In Section 5 we show how we equipped these negotiating agents with belief revision operators in the principal ABN functions: argument generation and interpretation. We also discuss some theoretical properties of our approach. In Section 5.6 we show how the $\mathit{HIA}$ problem can be solved in the context of our proposal. Then, in Section 6, we present the simulations of three types of agents in diverse negotiation scenarios where different advantages and salient features of agents using belief revision can be assessed. Section 7 discusses related work, and finally in Section 8 we discuss the main conclusions obtained and outline some future research topics.

2. Negotiation objects and protocol

In our negotiation scenario two agents will negotiate resources trying to reach a deal towards their goals. The agents will alternate moves and in each one, an agent will make a proposal to his counterpart together with some justification to the proposed exchange. In our approach, from the second move onwards the agents can add to their messages a critique to the last proposal received.

In order to characterize the negotiation elements, we consider a propositional language $\mathcal{L}$ , in which the following subsets are distinguished:

• ${\mathit{Objects}}_{\mathcal{L}}$ : a set of atoms representing objects which are the resources an agent may have (e.g., $\mathit{nail}$ , $\mathit{hammer}$ ).

• ${\mathit{Goal}}_{\mathcal{L}}$ : a set of atoms representing goals (e.g., $\mathit{hangMir}$ represents the goal of hanging a mirror). This set is disjoint from the set of objects (i.e. ${\mathit{Objects}}_{\mathcal{L}}\cap {\mathit{Goal}}_{\mathcal{L}}=\varnothing$ ).

• ${\mathit{Plans}}_{\mathcal{L}}$ : a set of propositional formulae encoding plans, which may involve objects for achieving a goal (e.g., $\mathit{nail}\wedge \mathit{hammer}\to \mathit{hangPict}$ ). Formally, a plan ${\mathit{p}}_{\mathit{i}}$ is defined as ${\mathit{p}}_{\mathit{i}}={\mathit{o}}_1\wedge \cdots \wedge {\mathit{o}}_{\mathit{n}}\to \mathit{g}$ where ${\mathit{o}}_{\mathit{j}}\in {\mathit{Objects}}_{\mathcal{L}}$ , $\mathit{j}=1\mathrm{,}\mathit{n}$ and $\mathit{g}\in {\mathit{Goal}}_{\mathcal{L}}$ .

In our approach, as in several areas of computer science, the term resources is considered in a broad sense and can represent anything that is needed to achieve something (e.g., memory, programs, commodities, services, time, money, etc.). Particularly, in this work the set of resources, noted by ${\mathit{Resource}}_{\mathcal{L}}$ , will include plans for achieving goals, i.e. ${\mathit{Resource}}_{\mathcal{L}}={\mathit{Objects}}_{\mathcal{L}}\cup {\mathit{Plans}}_{\mathcal{L}}$ . The plans represent the agent’s knowledge of how to use objects to reach a particular goal. Consequently, a plan will be considered as special kind of resource that the agent can share with others without consuming it. We assume that an agent can have infinite copies of each plan he knows. Given a set $\mathit{X}\subset {\mathit{Resource}}_{\mathcal{L}}$ , we will write ${\mathit{X}}^{\downarrow \mathit{o}}$ and ${\mathit{X}}^{\downarrow \mathit{p}}$ to distinguish the subset of objects and the subset of plans in X, respectively. Formally, ${\mathit{X}}^{\downarrow \mathit{o}}{=}_{\mathrm{def}}\mathit{X}\cap {\mathit{Objects}}_{\mathcal{L}}$ and ${\mathit{X}}^{\downarrow \mathit{p}}{=}_{\mathrm{def}}\mathit{X}\cap {\mathit{Plans}}_{\mathcal{L}}$ .

Using this language, the agents will exchange messages during the negotiation. A dialogue between two agents will be defined as a finite sequence of utterances where the first one is a proposal (which account for arguments in favor of some particular exchange). Then, alternative messages by each of the agents involved in the dialogue will be composed of a possible critique followed by a proposal. The dialogue ends with $\mathit{accept}$ (i.e., successful negotiation, there is a deal) or $\mathit{withdraw}$ (i.e., the negotiation failed, no deal is possible). The syntactic formalization of utterance and its components is presented in Fig. 2. Next, we define the negotiation dialogue.

Definition 2.1 (Negotiation dialogue).

A dialogue between agents ${\mathit{Ag}}_{\mathit{i}}$ and ${\mathit{Ag}}_{\mathit{j}}$ is a finite sequence of utterances $[{\mathit{u}}_1\mathrm{,}\dots \mathrm{,}{\mathit{u}}_{\mathit{n}-1}\mathrm{,}{\mathit{u}}_{\mathit{n}}]$ where ${\mathit{u}}_1$ is a proposal, for $1\mathrm{<}\mathit{r}\mathrm{<}\mathit{n}$ , ${\mathit{u}}_{\mathit{r}}=\mathrm{(}\mathit{critique}\mathrm{,}\mathit{proposal}\mathrm{)}$ and ${\mathit{u}}_{\mathit{n}}\in \{\mathit{accept}\mathrm{,}\mathit{withdraw}\}$ , such that: (1) there are no repeated utterances, i.e., ${\mathit{u}}_{\mathit{s}}\ne {\mathit{u}}_{\mathit{t}}$ , with $\mathit{t}\mathrm{,}\mathit{s}\mathrm{<}\mathit{n}$ ; (2) utterance ${\mathit{u}}_{\mathit{k}}$ with $\mathit{k}\mathrm{>}1$ is performed by Agent ${\mathit{Ag}}_{\mathit{i}}$ only if utterance ${\mathit{u}}_{\mathit{k}-1}$ is performed by Agent ${\mathit{Ag}}_{\mathit{j}}$ (i.e., agents alternate moves). A dialogue will be initiated by ${\mathit{Ag}}_{\mathit{i}}$ iff ${\mathit{u}}_1$ is performed by ${\mathit{Ag}}_{\mathit{i}}$ .

The contents of proposals and critiques will be defined in Section 4. Note that dialogues can be warranted to be finite, as there is a finite set of possible combinations of proposals and utterance repetition is not allowed. We can see that the dialogue between agents ${\mathit{Ag}}_{\mathit{i}}$ and ${\mathit{Ag}}_{\mathit{j}}$ will be started by one of the agents with a proposal computed by his Decision Making Apparatus (see next Definition 3.4) using the $\mathit{Init}$ function, followed by a pair (critique, counter-proposal) by the other agent computed by $\mathit{Answer}$ , and so on. Without loss of generality we assume the agent ${\mathit{Ag}}_{\mathit{i}}$ is the one who starts the negotiation dialogue. Figure 1 represents the negotiation dialogue flow initiated by ${\mathit{Ag}}_{\mathit{i}}$ as a finite-state machine.

Fig. 1.

Negotiation dialogue flow initiated by ${\mathit{Ag}}_{\mathit{i}}$ .

3. Agent architecture

We model the negotiating agents as intentional ones, following the general architecture presented in [24], but making different improvements in the agents’ decision making apparatus to generate, evaluate and interpret more complex utterances. Each agent will have in his mental state, knowledge about his resources (objects and plans) and goals, as well as beliefs on the other agent’s resources and goals. In a more dynamic agent model a planner may be included with the purpose of generating plans in real time according to the agent’s goals (see for example [19]). In our approach, the plans are preconfigured as agent’s believes and then, the agent selects one of them to reach his current goal. The knowledge and beliefs an agent has about his context are represented using the language $\mathcal{L}$ , previously defined. From the information available in such a mental state, he will decide if he accepts a received proposal or which pair (critique, proposal) he can offer the other agent in order to reach an agreement. Otherwise he will withdraw from the negotiation.

Definition 3.1 (Agent mental state).

Let two agents ${\mathit{Ag}}_{\mathit{i}}$ , ${\mathit{Ag}}_{\mathit{j}}$ be involved in a negotiation. The mental state ( $\mathit{MS}$ ) of an Agent ${\mathit{Ag}}_{\mathit{i}}$ is a tuple ${\mathit{MS}}_{\mathit{i}}=⟨{\mathit{R}}_{\mathit{i}}\mathrm{,}{\mathit{G}}_{\mathit{i}}\mathrm{,}{\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}\mathrm{,}{\mathit{B}}_{\mathit{i}}{\mathit{G}}_{\mathit{j}}\mathrm{,}{\mathit{H}}_{\mathit{i}}⟩$ , where: ${\mathit{R}}_{\mathit{i}}\mathrm{,}{\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}\subset {\mathit{Resource}}_{\mathcal{L}}$ ; ${\mathit{G}}_{\mathit{i}}\mathrm{,}{\mathit{B}}_{\mathit{i}}{\mathit{G}}_{\mathit{j}}\subset {\mathit{Goal}}_{\mathcal{L}}$ and ${\mathit{H}}_{\mathit{i}}$ is the history of the negotiation.2

²

In what follows, we will refer to ${\mathit{Ag}}_{\mathit{i}}$ as a generic agent, and ${\mathit{Ag}}_{\mathit{j}}$ the counterpart agent.

Thus, the mental state of ${\mathit{Ag}}_{\mathit{i}}$ includes a set of available resources ( ${\mathit{R}}_{\mathit{i}}$ ) the agent is willing to negotiate, a set of goals to achieve ( ${\mathit{G}}_{\mathit{i}}$ ),3

³

Notice that in the case of having ${\mathit{G}}_{\mathit{i}}$ more than one goal, the agent will want to achieve all of them and consequently, we will follow a conjunctive approach of the set.

as well as belief sets about which resources are available for the opponent agent ${\mathit{Ag}}_{\mathit{j}}$ ( ${\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}$ ), and which goals he believes the agent ${\mathit{Ag}}_{\mathit{j}}$ has ( ${\mathit{B}}_{\mathit{i}}{\mathit{G}}_{\mathit{j}}$ ). Its mental state includes as well the history of the dialogue (see Definition 2.1) with ${\mathit{Ag}}_{\mathit{j}}$ .

Example 3.2.

Consider the Motivational Example ( $\mathit{HIA}$ problem) given in Section 1. In the beginning of the negotiation process, ${\mathit{Ag}}_1$ ’s mental state can be represented as ${\mathit{MS}}_1=⟨{\mathit{R}}_1\mathrm{,}{\mathit{G}}_1\mathrm{,}{\mathit{B}}_1{\mathit{R}}_2\mathrm{,}{\mathit{B}}_1{\mathit{G}}_2\mathrm{,}{\mathit{H}}_1⟩$ where: $$\begin{array}{ll}\hfill & {\mathit{R}}_1=\{\mathit{screw}\mathrm{,}\mathit{hammer}\mathrm{,}\mathit{screw}\wedge \mathit{screwDriver}\to \mathit{hangMir}\mathrm{,}\mathit{hammer}\wedge \mathit{nail}\to \mathit{hangPict}\}\mathrm{,}\\ \hfill & {\mathit{G}}_1=\{\mathit{hangPict}\}\mathrm{,}\\ \hfill & {\mathit{B}}_1{\mathit{R}}_2=\{\mathit{nail}\mathrm{,}\mathit{screwDriver}\mathrm{,}\mathit{screw}\wedge \mathit{screwDriver}\to \mathit{repairDesk}\}\mathrm{,}\\ \hfill & {\mathit{B}}_1{\mathit{G}}_2=\{\mathit{repairDesk}\}\mathrm{,}\\ \hfill & {\mathit{H}}_1=[·].\end{array}$$

In our negotiation scenario, the agents may have missing and incorrect beliefs about each other. From a global viewpoint we want to characterize the sets that account for the agent’s correct, incorrect and missing beliefs with respect to his counterpart’s resources. Formally:

Definition 3.3 (Missing, correct and incorrect beliefs).

Let ${\mathit{Ag}}_{\mathit{i}}$ , ${\mathit{Ag}}_{\mathit{j}}$ be two agents. We will write ${\mathit{M}}_{\mathit{i}}$ to denote the set of resources that ${\mathit{Ag}}_{\mathit{i}}$ does not know that ${\mathit{Ag}}_{\mathit{j}}$ has, ${\mathit{T}}_{\mathit{i}}$ to denote the set of resources that ${\mathit{Ag}}_{\mathit{i}}$ believes that ${\mathit{Ag}}_{\mathit{j}}$ has and this is actually the case, i.e., such beliefs are correct and ${\mathit{F}}_{\mathit{i}}$ to denote the set of resources that ${\mathit{Ag}}_{\mathit{i}}$ believes that ${\mathit{Ag}}_{\mathit{j}}$ has and this is actually not the case, i.e., such beliefs are incorrect. Formally: ${\mathit{M}}_{\mathit{i}}=\overline{{\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}}\cap {\mathit{Resource}}_{\mathit{j}}$ , ${\mathit{T}}_{\mathit{i}}={\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}\cap {\mathit{Resource}}_{\mathit{j}}$ , and ${\mathit{F}}_{\mathit{i}}={\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}\cap \overline{{\mathit{Resource}}_{\mathit{j}}}$ .

The decision making apparatus the agents employ to act in order to achieve their objectives depends on their mental states (see Definition 3.1). This apparatus will be in charge of computing those messages the agent will send to the other agent.

As the first dialogue move associated with the initial utterance is a particular one, we will single it out by using an initialization function $\mathit{Init}$ . Further messages are computed by another function $\mathit{Answer}$ . Formally:

Definition 3.4 (Decision making apparatus).

The decision making apparatus of an Agent ${\mathit{Ag}}_{\mathit{i}}$ is a pair ${\mathit{DM}}_{\mathit{i}}=⟨{\mathit{Init}}_{\mathit{i}}\mathrm{,}{\mathit{Answer}}_{\mathit{i}}⟩$ , where

${\mathit{Init}}_{\mathit{i}}:{\mathit{MS}}_{\mathit{i}}\to {\mathit{MS}}_{\mathit{i}}\times \mathit{Utterance}$ ;

${\mathit{Answer}}_{\mathit{i}}:{\mathit{MS}}_{\mathit{i}}\times \mathit{Utterance}\to {\mathit{MS}}_{\mathit{i}}\times \mathit{Utterance}$ .

At this stage we purposely leave unspecified the actual definitions of ${\mathit{Init}}_{\mathit{i}}$ and ${\mathit{Answer}}_{\mathit{i}}$ , later on in Section 5 we will provide their specification through high-level algorithms. Thus, in our approach an ABN agent model will be composed of his mental state and his decision making apparatus. Formally:

Definition 3.5 (Agent model).

An agent ${\mathit{Ag}}_{\mathit{i}}$ is a tuple $⟨{\mathit{MS}}_{\mathit{i}}\mathrm{,}{\mathit{DM}}_{\mathit{i}}⟩$ , where ${\mathit{MS}}_{\mathit{i}}$ is its mental state and ${\mathit{DM}}_{\mathit{i}}$ its decision making apparatus.

4. The agent’s utterances

Based on their mental states, the agents use their decision apparatus to generate illocutions that contain proposals towards reaching their goals. In our approach, after the first move a message may also contain a critique to the last received proposal. Besides, a proposal is an argument that includes what the agent wants to receive (Y) and what the agent is willing to give in return (X), together with a possible justification ( $\mathcal{J}$ ) explaining why an agent needs what he is asking for ( ${\mathit{S}}_{\mathit{Y}}$ ) or the beliefs supporting his offer ( ${\mathit{S}}_{\mathit{X}}$ ). In turn, both justifications may be empty or a pair composed of a set of resources and a set of goals. The syntax for utterances and their components (i.e., proposal, solution, justification and critique) are shown in Fig. 2.

Fig. 2.

Syntax for the agents’ utterances.

The well formed proposals, according to the defined syntax (see Fig. 2) may be more or less informative, with the following intended meaning:

• Proposal with no explanation ( ${\mathit{S}}_{\mathit{X}}={\mathit{S}}_{\mathit{Y}}=\varnothing$ ): $$\begin{array}{c}\mathit{\text{I propose that you provide me }}\mathit{Y}\mathit{\text{in exchange for }}\mathit{X}.\end{array}$$

• Proposals with partial justification (explaining the demand ${\mathit{S}}_{\mathit{Y}}\ne \varnothing$ , or the offer ${\mathit{S}}_{\mathit{X}}\ne \varnothing$ ): $$\begin{array}{ll}\hfill & \mathit{\text{I propose that you provide me }}\mathit{Y}\mathit{\text{in exchange for }}\mathit{X}\mathrm{,}\mathit{\text{because if I use }}{\mathit{E}}_{\mathit{Y}}\mathit{\text{then I can achieve }}\mathit{G}.\\ \hfill & \begin{array}{cc}\hfill & \mathit{\text{I propose that you provide me }}\mathit{Y}\mathit{\text{in exchange for }}\mathit{X}\mathrm{,}\mathit{\text{because I believe that if you use }}{\mathit{E}}_{\mathit{X}}\mathit{\text{then}}\hfill \\ \hfill & \mathit{\text{you can achieve }}{\mathit{G}}^{\prime }.\hfill \end{array}\end{array}$$

• Proposals with complete explanation ( ${\mathit{S}}_{\mathit{X}}\ne \varnothing$ and ${\mathit{S}}_{\mathit{Y}}\ne \varnothing$ ): $$\begin{array}{ll}\hfill & \mathit{\text{I propose that you provide me }}\mathit{Y}\mathit{\text{because with }}{\mathit{E}}_{\mathit{Y}}\mathrm{,}\mathit{\text{I can achieve }}\mathit{G};\mathit{\text{in exchange}}\\ \hfill & \mathit{\text{I offer you }}\mathit{X}\mathrm{,}\mathit{\text{because I believe if you use }}{\mathit{E}}_{\mathit{X}}\mathit{\text{you can reach }}{\mathit{G}}^{\prime }.\end{array}$$

Note that an agent’s proposal can be thought of as an argument4

⁴

A full account of argumentation theory and its applications in multiagent systems and belief revision is outside the scope of this article. For further references and insights the reader is referred to [12].

whose claim or solution is associated with a possible exchange of resources ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}$ , where Y represents what the agent needs to achieve his goals and X the resources he offers in exchange together with its support, i.e., the reasons given for requesting and offering resources. The following definition formalizes this concept.

Definition 4.1 (Proposal).

Let ${\mathit{Ag}}_{\mathit{i}}$ be an agent with mental state ${\mathit{MS}}_{\mathit{i}}=⟨{\mathit{R}}_{\mathit{i}}\mathrm{,}{\mathit{G}}_{\mathit{i}}\mathrm{,}{\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}\mathrm{,}{\mathit{B}}_{\mathit{i}}{\mathit{G}}_{\mathit{j}}\mathrm{,}{\mathit{H}}_{\mathit{i}}⟩$ . A proposal performed by ${\mathit{Ag}}_{\mathit{i}}$ , ${\mathit{proposal}}_{\mathit{i}}$ , is a well formed proposal (i.e., defined in Fig. 2) namely, is an argument $⟨\mathcal{J}\mathrm{,}{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}⟩$ , where ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}$ corresponds to the claim or solution of the argument, and $\mathcal{J}=⟨{\mathit{S}}_{\mathit{X}}\mathrm{,}{\mathit{S}}_{\mathit{Y}}⟩$ provides the support associated with the claim. ${\mathit{S}}_{\mathit{Y}}=\mathrm{(}{\mathit{E}}_{\mathit{Y}}\mathrm{,}\mathit{G}\mathrm{)}$ justifies what the agent demands or is the empty set, and ${\mathit{S}}_{\mathit{X}}=\mathrm{(}{\mathit{E}}_{\mathit{X}}\mathrm{,}{\mathit{G}}^{\prime }\mathrm{)}$ what he is offering as exchange or is possibly empty, and the following conditions hold:

$\mathit{X}\mathrm{,}{\mathit{E}}_{\mathit{Y}}\subset {\mathit{R}}_{\mathit{i}}$ ; $\mathit{G}\subset {\mathit{G}}_{\mathit{i}}$ ;

$\mathit{Y}\mathrm{,}{\mathit{E}}_{\mathit{X}}\subset {\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}$ ; ${\mathit{G}}^{\prime }\subset {\mathit{B}}_{\mathit{i}}{\mathit{G}}_{\mathit{j}}$ ;

$\mathit{Y}\cup {\mathit{E}}_{\mathit{Y}}⊢\mathit{G}$ ;

$\mathit{X}\cup {\mathit{E}}_{\mathit{X}}⊢{\mathit{G}}^{\prime }$ ;

${\mathit{E}}_{\mathit{Y}}⊬\mathit{G}$ ;

${\mathit{E}}_{\mathit{X}}⊬{\mathit{G}}^{\prime }$ ;

${\mathit{X}}^{\downarrow \mathit{o}}\cap \mathrm{(}\mathit{Y}\cup {\mathit{E}}_{\mathit{Y}}\mathrm{)}=\varnothing$ ;

${\mathit{Y}}^{\downarrow \mathit{o}}\cap \mathrm{(}\mathit{X}\cup {\mathit{E}}_{\mathit{X}}\mathrm{)}=\varnothing$ .

Notice that (3) state that ${\mathit{E}}_{\mathit{Y}}$ and Y are needed for the agent to reach the goal G; (5) means the agent can not reach the goal using only ${\mathit{E}}_{\mathit{Y}}$ and (7) states that no object of X is needed by the agent to reach G – as it suffices to use $\mathit{Y}\cup {\mathit{E}}_{\mathit{Y}}$ to reach G, as stated in condition (3). In a similar way, (4), (6) and (8) represent the agent’s beliefs respect to what he is offering: (4) expresses he believes that his counterpart needs ${\mathit{E}}_{\mathit{X}}$ and X to reach the goal ${\mathit{G}}^{\prime }$ (i.e., what he believes is his opponent’s goal); (6) means he believes the other agent can not reach his goal using only ${\mathit{E}}_{\mathit{X}}$ and (8) states that no object of Y is needed by the agent to reach ${\mathit{G}}^{\prime }$ .5

⁵

We write $\mathit{X}⊢\mathit{G}$ whenever $\mathit{G}\subseteq \mathit{Cn}\mathrm{(}\mathit{X}\mathrm{)}$ , where $\mathit{Cn}$ is a logical consequence operator.

Also, notice that both explanations may be empty allowing the agent to decide which support to communicate his counterpart.

The set of all the proposals an agent can generate is called $\mathit{Proposal}$ .

Example 4.2 (Example 3.2 continued).

Suppose that in this scenario ${\mathit{Ag}}_1$ begins the negotiation process by offering ${\mathit{Ag}}_2$ the following proposal ${\mathit{p}}_1$ :

I propose that you provide me with a nail in exchange for a screw, because if I use a hammer and the knowledge about how to hang a picture using a nail and a hammer, then I can hang a picture. In exchange I offer you a screw because if you use your screwdriver and the knowledge about how to repair a desk with these resources, you can do it.

Then this proposal is denoted by ${\mathit{p}}_1=⟨\mathrm{(}{\mathit{S}}_{\mathit{X}}\mathrm{,}{\mathit{S}}_{\mathit{Y}}\mathrm{)}\mathrm{,}{[[\{\mathit{screw}\}\mathrm{,}\{\mathit{nail}\}]]}_1⟩$ where the justifications associated with the solution are: $$\begin{array}{ll}\hfill & {\mathit{S}}_{\mathit{X}}=\mathrm{(}\{\mathit{screwDriver}\mathrm{,}\mathit{screw}\wedge \mathit{screwDriver}\to \mathit{repairDesk}\}\mathrm{,}\{\mathit{repairDesk}\}\mathrm{)}\text{and}\\ \hfill & {\mathit{S}}_{\mathit{Y}}=\mathrm{(}\{\mathit{hammer}\mathrm{,}\mathit{nail}\wedge \mathit{hammer}\to \mathit{hangPict}\}\mathrm{,}\{\mathit{hangPict}\}\mathrm{)}.\end{array}$$

In the first move the agent that starts the negotiation can only make a proposal to his counterpart, but in the following utterances the agents can reply with a critique to the received proposal, together with a counterproposal. The critiques may have different meanings and are defined as follows.

Definition 4.3 (Critique).

Let a proposal $⟨\mathcal{J}\mathrm{,}{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}⟩$ where: $\mathcal{J}=⟨\mathrm{(}{\mathit{E}}_{\mathit{X}}\mathrm{,}{\mathit{G}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{E}}_{\mathit{Y}}\mathrm{,}\mathit{G}\mathrm{)}⟩$ offered by ${\mathit{Ag}}_{\mathit{i}}$ to ${\mathit{Ag}}_{\mathit{j}}$ , we define a critique ${\mathit{C}}_{\mathit{j}}$ expressed by agent ${\mathit{Ag}}_{\mathit{j}}$ as $⟨{\mathit{C}}_1\mathrm{,}{\mathit{C}}_2\mathrm{,}{\mathit{C}}_3⟩$ following the given syntax in Fig. 2, where the following conditions hold:

${\mathit{C}}_1:{\mathit{C}}_1\subset \mathit{Y}$ and ${\mathit{C}}_1\cap {\mathit{R}}_{\mathit{j}}=\varnothing$ representing that the agent lacks the required objects ${\mathit{C}}_1$ .

${\mathit{C}}_2:{\mathit{C}}_2\subset {\mathit{E}}_{\mathit{X}}$ and ${\mathit{C}}_2\cap {\mathit{R}}_{\mathit{j}}=\varnothing$ expressing that the agent does not have the resources ${\mathit{C}}_2$ of the believed support ${\mathit{E}}_{\mathit{X}}$ .

${\mathit{C}}_3:{\mathit{C}}_3\subseteq {\mathit{G}}^{\prime }$ and ${\mathit{C}}_3\cap {\mathit{G}}_{\mathit{j}}=\varnothing$ communicating that ${\mathit{C}}_3$ is not a subset of the agent’s goals.

Notice that the critique ${\mathit{C}}_1$ is oriented towards the original request (Y). On the other hand, ${\mathit{C}}_2$ and ${\mathit{C}}_3$ are critiques to the offer (X) due to incorrect beliefs that the proposing agent has. Besides, notice that the different components of a critique may be empty and then, the agent must decide which kind of critique he will include in his answer to his counterpart.

We also remark that in a argumentation setting a critique can be considered an attack to the last received proposal. In our approach we only consider one level attacks because there is no place for critiques to critiques (i.e. the agents are truthful and know with certainty which resources and objectives they have). 6

⁶

These kind of chained attacks can be introduced using a Defeasible Logic Programming framework (see for example [23]). A full account of such attacks is outside the scope of this article.

Example 4.4.

Following with Example 4.2, ${\mathit{Ag}}_2$ can answer ${\mathit{Ag}}_1$ with respect to the received proposal ${\mathit{p}}_1$ with some of the following critiques:

${\mathit{C}}_1$ : I do not have the requested $\mathit{nail}$ .

${\mathit{C}}_2$ : I do not have the knowledge of how to repair a desk with a screw and a screwdriver (i.e., $\mathit{screw}\wedge \mathit{screwDriver}\to \mathit{repairDesk}$ ).

${\mathit{C}}_3$ : My goal is not repair a desk.

4.1. Proposal evaluation: Solutions and deals

As previously mentioned, we assume agents ${\mathit{Ag}}_{\mathit{i}}$ and ${\mathit{Ag}}_{\mathit{j}}$ cannot reach their goals on their own, and therefore the problem each agent faces is to find a suitable exchange of resources in the space of possible exchanges ( $\mathcal{P}\mathrm{(}{\mathit{R}}_{\mathit{i}}\mathrm{)}\times \mathcal{P}\mathrm{(}{\mathit{R}}_{\mathit{j}}\mathrm{)}$ ) in order to reach his own goal. In this setting, a proposal can be thought of as an argument $⟨\mathcal{J}\mathrm{,}{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}⟩$ supporting an exchange of resources. By definition, the pair of resources ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}$ provides a solution to reach ${\mathit{Ag}}_{\mathit{i}}$ ’s goal. We define the function ⊙ that assigns to each proposal $⟨\mathcal{J}\mathrm{,}{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}⟩$ its associated solution.7

⁷

The function ⊙ corresponds to the second component projection.

Following [26], we assume that in our approach agents have an objective consideration when they evaluate proposals (i.e., they consider a proposal as a tentative proof to reach their goals, and they verify it by examining the validity of its underlying assumptions, such as resource availability). Since each agent is aware of his own resources and goals, he can determine first, in a selfish way, which are the exchanges that provide a solution for his problem. This is formalized in the following definition.

Definition 4.5 (Solution).

Let ${\mathit{Ag}}_{\mathit{i}}$ be an agent involved in a negotiation, where its mental state is ${\mathit{MS}}_{\mathit{i}}=⟨{\mathit{R}}_{\mathit{i}}\mathrm{,}{\mathit{G}}_{\mathit{i}}\mathrm{,}{\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}\mathrm{,}{\mathit{B}}_{\mathit{i}}{\mathit{G}}_{\mathit{j}}\mathrm{,}{\mathit{H}}_{\mathit{i}}⟩$ . A solution for ${\mathit{Ag}}_{\mathit{i}}$ is any pair ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}$ , $\mathit{X}\mathrm{,}\mathit{Y}\subseteq {\mathit{Resource}}_{\mathcal{L}}$ such that:

$\mathit{X}\subseteq {\mathit{R}}_{\mathit{i}}$ ;

$\mathrm{(}{\mathit{R}}_{\mathit{i}}-{\mathit{X}}^{\downarrow \mathit{o}}\mathrm{)}\cup \mathit{Y}⊢{\mathit{G}}_{\mathit{i}}$ .

We will denote by ${\mathcal{S}}_{\mathit{i}}$ the set of all possible solutions for ${\mathit{Ag}}_{\mathit{i}}$ .

Note that X stands for those resources that ${\mathit{Ag}}_{\mathit{i}}$ is willing to give to ${\mathit{Ag}}_{\mathit{j}}$ , whereas Y is the set of resources that are given to ${\mathit{Ag}}_{\mathit{i}}$ to achieve his goal. In a similar way ${\mathcal{S}}_{\mathit{j}}$ is defined. A deal for ${\mathit{Ag}}_{\mathit{i}}$ and ${\mathit{Ag}}_{\mathit{j}}$ will be a solution which is applicable for both of them, being formally defined as follows.

Definition 4.6 (Deal).

We will say that ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}$ where $\mathit{X}\mathrm{,}\mathit{Y}\subseteq {\mathit{Resource}}_{\mathcal{L}}$ , is a deal for ${\mathit{Ag}}_{\mathit{i}}$ and ${\mathit{Ag}}_{\mathit{j}}$ iff ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}\in {\mathcal{S}}_{\mathit{i}}\wedge {[[\mathit{Y}\mathrm{,}\mathit{X}]]}_{\mathit{j}}\in {\mathcal{S}}_{\mathit{j}}$ . We will denote with $\mathcal{D}$ the set of all deals between ${\mathit{Ag}}_{\mathit{i}}$ and ${\mathit{Ag}}_{\mathit{j}}$ .

From the definitions presented before, the agents’ evaluation process can be defined in a simple way as follows: if $\mathit{prop}=⟨\mathcal{J}\mathrm{,}{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}⟩$ is an ${\mathit{Ag}}_{\mathit{i}}$ proposal, then $\mathit{prop}$ will be accepted by ${\mathit{Ag}}_{\mathit{j}}$ if ${[[\mathit{Y}\mathrm{,}\mathit{X}]]}_{\mathit{j}}\in {\mathcal{S}}_{\mathit{j}}$ . Notice that a proposal $\mathit{prop}$ will be accepted only if it is a deal.

On the other hand, the agent has beliefs about his counterpart resources and goals that he can use to make exchange proposals. Then, in his proposal he can offer resources that he believes are useful for his opponent and thus, closer to reach a deal. We formalize these ideas as follows.

Definition 4.7 (Belief of solution).

Let ${\mathit{Ag}}_{\mathit{i}}$ and ${\mathit{Ag}}_{\mathit{j}}$ be two agents and $\mathit{X}\mathrm{,}\mathit{Y}\subseteq {\mathit{Resource}}_{\mathcal{L}}$ , we will say that ${\mathit{Ag}}_{\mathit{i}}$ believes ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}$ is a solution for ${\mathit{Ag}}_{\mathit{j}}$ whenever:

$\mathit{Y}\subseteq {\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}$ ;

$\mathrm{(}{\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}-{\mathit{Y}}^{\downarrow \mathit{o}}\mathrm{)}\cup \mathit{X}⊢{\mathit{B}}_{\mathit{i}}{\mathit{G}}_{\mathit{j}}$ .

We will define ${\mathcal{B}}_{\mathit{i}}{\mathcal{S}}_{\mathit{j}}=\{{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}\mid {\mathit{Ag}}_{\mathit{i}}\mathit{\text{believes }}{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}\text{ is a }\mathit{\text{solution}}\text{ for }{\mathit{Ag}}_{\mathit{j}}\}$ .

Definition 4.8 (Belief of deal).

Let ${\mathit{Ag}}_{\mathit{i}}$ and ${\mathit{Ag}}_{\mathit{j}}$ be two agents, we will say that ${\mathit{Ag}}_{\mathit{i}}$ believes ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}$ is a deal iff:

$\mathit{X}\subseteq {\mathit{R}}_{\mathit{i}}$ ;

$\mathrm{(}{\mathit{R}}_{\mathit{i}}-{\mathit{X}}^{\downarrow \mathit{o}}\mathrm{)}\cup \mathit{Y}⊢{\mathit{G}}_{\mathit{i}}$ ;

$\mathit{Y}\subseteq {\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}$ ;

$\mathrm{(}{\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}-{\mathit{Y}}^{\downarrow \mathit{o}}\mathrm{)}\cup \mathit{X}⊢{\mathit{B}}_{\mathit{i}}{\mathit{G}}_{\mathit{j}}$ .

We will define ${\mathcal{B}}_{\mathit{i}}\mathcal{D}=\{{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{}\mid {\mathit{Ag}}_{\mathit{i}}\mathit{\text{believes }}{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}\text{ is a }\mathit{\text{deal}}\}$ .

Notice that ${\mathit{Ag}}_{\mathit{i}}$ believes ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}$ is a deal iff it is a solution for him and he believes that is a solution for his counterpart.

From Definitions 4.7 and 4.8 the following propositions hold:8

⁸

All the propositions and their proofs were formalized in Coq and are available at http://web.cifasis-conicet.gov.ar/~pilotti/Automated_Agent_Negotiation.v.

Proposition 4.9.

${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}\in {\mathcal{S}}_{\mathit{i}}$ and ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}\in {\mathcal{B}}_{\mathit{i}}{\mathcal{S}}_{\mathit{j}}\iff {[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}\in {\mathcal{B}}_{\mathit{i}}\mathcal{D}$ .

Proposition 4.10.

${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}\in {\mathcal{B}}_{\mathit{i}}\mathcal{D}$ and ${[[\mathit{Y}\mathrm{,}\mathit{X}]]}_{\mathit{j}}\in {\mathcal{S}}_{\mathit{j}}\Rightarrow {[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}\in \mathcal{D}$ .

Proposition 4.11.

${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}\in {\mathcal{B}}_{\mathit{i}}\mathcal{D}$ and ${[[\mathit{Y}\mathrm{,}\mathit{X}]]}_{\mathit{j}}\in {\mathcal{B}}_{\mathit{j}}\mathcal{D}\Rightarrow {[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}\in \mathcal{D}$ .

Proposition 4.9 states that if a pair ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}$ is a solution for ${\mathit{Ag}}_{\mathit{i}}$ and he believes that it is also a solution for ${\mathit{Ag}}_{\mathit{j}}$ , then ${\mathit{Ag}}_{\mathit{i}}$ believes that ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}$ is a deal, and the reciprocal also holds. Similarly, Proposition 4.10 asserts that if the agent ${\mathit{Ag}}_{\mathit{i}}$ believes that ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}$ is a deal and ${[[\mathit{Y}\mathrm{,}\mathit{X}]]}_{\mathit{j}}$ is also a solution for ${\mathit{Ag}}_{\mathit{j}}$ , then ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}$ is a deal. Finally, Proposition 4.11 states that if ${\mathit{Ag}}_{\mathit{i}}$ believes that ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}$ is a deal and ${\mathit{Ag}}_{\mathit{j}}$ believes that ${[[\mathit{Y}\mathrm{,}\mathit{X}]]}_{\mathit{j}}$ is a deal, then it holds that ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}$ is a deal.

Figure 3 shows the set of solutions and beliefs of solutions from the viewpoint of ${\mathit{Ag}}_{\mathit{i}}$ . The dotted line represents the set ${\mathcal{S}}_{\mathit{j}}$ of solutions of ${\mathit{Ag}}_{\mathit{j}}$ that the agent does not know with total precision. Because of this, ${\mathit{Ag}}_{\mathit{i}}$ cannot be sure of making a proposal $\mathit{prop}$ such that $\odot \mathrm{(}\mathit{prop}\mathrm{)}\in \mathcal{D}$ . So, in order to entice agent ${\mathit{Ag}}_{\mathit{j}}$ to accept some proposed agreement, ${\mathit{Ag}}_{\mathit{i}}$ must choose a proposal $\mathit{prop}$ such that he believes that its associated solution is a deal, i.e. $\odot \mathrm{(}\mathit{prop}\mathrm{)}\in {\mathcal{B}}_{\mathit{i}}\mathcal{D}$ . The closer the belief set ${\mathcal{B}}_{\mathit{i}}{\mathcal{S}}_{\mathit{j}}$ is to ${\mathcal{S}}_{\mathit{j}}$ , the closer will be ${\mathcal{B}}_{\mathit{i}}\mathcal{D}$ to $\mathcal{D}$ .

Fig. 3.

Solutions’ space from ${\mathit{Ag}}_{\mathit{i}}$ viewpoint.

5. Agents equipped with belief revision

In this section, following the approach presented in [24] we implement belief revision in ABN agents to improve two important issues in the negotiation: the proposal generation and proposal interpretation. All the information contained in an incoming proposal is used by an agent to revise his beliefs about his counterpart and then, by having more accurate beliefs, the agent can make proposals that are more likely to be accepted. The authors showed in [24] that the negotiating agents that implement complete belief revision in these processes (i.e., proposal interpretation and generation) led the negotiation to have better results. In our current work we have improved this agent model equipped with belief revision to be capable of generating and interpreting more complex utterances and we focus our research on the impact that different communication strategies has in the negotiation process. In order to make our analysis self-contained, we will summarize some notions of the belief change theory that we apply in our agent model.

5.1. Belief revision operators

Classic belief change operations introduced in the AGM model [1] are known as expansions, contractions and revisions. An expansion incorporates a new belief without warranting the consistency of the resulting epistemic state. A contraction eliminates a belief α from the epistemic state as well as all those beliefs that make the inference of α possible. Finally, a revision incorporates a new belief α to the epistemic state warranting a consistent result, assuming that α itself is consistent.

As discussed before, in our setting we assume that the agents have their own beliefs about the other agent’s resources and goals. It must be noted that the sets of resources and objectives do not change during the negotiation. Only if a deal succeeds at the end of the negotiation process, the actual exchange of resources will take place and consequently the sets X and Y will be changed. In order to model such a negotiation process in terms of belief revision we will use the notion of Choice Kernel Set and Multiple Kernel contraction [14,16]. These notions will be useful for providing a practical approach to belief revision in our context. We provide below a brief review of the formal definitions involved.

Definition 5.1 (Choice Kernel Set, from [14]).

Let $\mathcal{L}$ be a logical language, R and G finite subsets of $\mathcal{L}$ and $\mathit{C}\mathit{n}$ a consequence operator. Then $\mathit{R}\perp \perp \mathit{G}$ is the set of all $\mathit{X}\subseteq \mathit{R}$ such that:

$\mathit{G}\subseteq \mathit{C}\mathit{n}\mathrm{(}\mathit{X}\mathrm{)}$ ;

If $\mathit{Y}\subset \mathit{X}$ then $\mathit{G}⊈\mathit{C}\mathit{n}\mathrm{(}\mathit{Y}\mathrm{)}$ .

The set $\mathit{R}\perp \perp \mathit{G}$ is called Choice Kernel Set, and its elements are called G-Kernels of R.

Informally, a Choice Kernel Set is a minimal belief subset of the epistemic state from which G can be deduced. An element in R contributes to make R imply G if and only if it is an element of some G-Kernels of R. Therefore, removing at least one element of each G-kernel of R, it is no longer possible to derive G. The function that selects sentences to be removed will be called an incision function since it makes an incision into every G-kernel.

Definition 5.2 (Incision function, from [14]).

A function σ is an incision function for R, iff satisfies for all G:

$\mathit{\sigma }\mathrm{(}\mathit{R}\perp \perp \mathit{G}\mathrm{)}\subseteq \bigcup \mathrm{(}\mathit{R}\perp \perp \mathit{G}\mathrm{)}$ ;

$\varnothing \ne \mathit{X}\in \mathit{R}\perp \perp \mathit{G}\Rightarrow \mathit{X}\cap \mathit{\sigma }\mathrm{(}\mathit{R}\perp \perp \mathit{G}\mathrm{)}\ne \varnothing$ .

The multiple choice contraction operator allows to remove the elements selected by an incision function. Formally:

Definition 5.3 (Multiple Kernel contraction, from [14]).

Let σ be an incision function for R and G finite subset of $\mathcal{L}$ . The multiple kernel contraction ≈ for R is defined as: $\mathit{R}\approx \mathit{G}=\mathit{R}-\mathit{\sigma }\mathrm{(}\mathit{R}\perp \perp \mathit{G}\mathrm{)}$ .

Next, a revision operator is expressed using two sub-operations: first a contraction and then an expansion (i.e., adding G to the resulting set).

Definition 5.4 (Revision operator, from [16]).

Let ≈ be a multiple kernel contraction. Given a finite set of sentences R, we define for any finite set G the revision operator ∗: $\mathit{R}\ast \mathit{G}=\mathrm{(}\mathit{R}\approx \neg \mathit{G}\mathrm{)}\cup \mathit{G}$ , where $\neg \mathit{G}{=}_{\mathrm{def}}\{\neg {\mathit{g}}_{\mathit{i}}:{\mathit{g}}_{\mathit{i}}\in \mathit{G}\}$ .

Contracting by the finite set $\neg \mathit{G}$ is equivalent to contract by the set formed by the negations of the elements in G.

5.2. Argument generation

The beliefs a particular agent has about the other agent’s resources and goals are significant for proposal generation during negotiation, as they can help reaching a deal. From this information, an agent can infer which proposals he believes are more suitable for the other and consequently, more likely to be accepted. These notions were formalized through the definitions of solutions and belief of solutions (Definitions 4.5 and 4.8). To generate the arguments an agent can give to his counterpart, we define the function $\mathsf{Gen}$ that was firstly introduced in [24] but for our negotiation model we implement it with some necessary adaptations. This function allows to compute the proposals that are solution to ${\mathit{Ag}}_{\mathit{i}}$ (i.e., $\odot \mathrm{(}\mathit{prop}\mathrm{)}\in {\mathcal{S}}_{\mathit{i}}$ ) and to compute proposals that are potential solutions for ${\mathit{Ag}}_{\mathit{j}}$ (i.e., $\odot \mathrm{(}\mathit{prop}\mathrm{)}\in {\mathcal{B}}_{\mathit{i}}{\mathcal{S}}_{\mathit{j}}$ ). The $\mathsf{Gen}$ function is specified using belief revision operations and some properties that follow from its specification are given.

Definition 5.5 ( $\mathsf{Gen}$ ).

Let $\mathit{R}\mathrm{,}{\mathit{R}}^{\prime }\subset {\mathit{Resource}}_{\mathcal{L}}$ and $\mathit{G}\subset {\mathit{Goal}}_{\mathcal{L}}$ , we define a function $\mathsf{Gen}$ as follows: $$\begin{array}{ll}\hfill \mathsf{Gen}\mathrm{(}\mathit{R}\mathrm{,}{\mathit{R}}^{\prime }\mathrm{,}\mathit{G}\mathrm{,}\mathit{i}\mathrm{)}{=}_{\mathrm{def}}& \{⟨\mathrm{(}{\mathit{E}}_{\mathit{Y}}\mathrm{,}\mathit{G}\mathrm{)}\mathrm{,}{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}⟩:\mathit{Y}\cap \mathit{R}=\varnothing \mathrm{,}{\mathit{E}}_{\mathit{Y}}\subseteq \mathit{R}\mathrm{,}\\ \hfill & \mathrm{(}{\mathit{E}}_{\mathit{Y}}\cup \mathit{Y}\mathrm{)}\in \mathrm{(}\mathit{R}\cup {\mathit{R}}^{\prime }\cup \mathit{Y}\mathrm{)}\perp \perp \mathit{G}\mathrm{,}\mathit{X}\subseteq \mathit{R}-{\mathit{E}}_{\mathit{Y}}\}.\end{array}$$

The $\mathsf{Gen}$ function receives two sets of resources (R and ${\mathit{R}}^{\prime }$ ) and a set of goals (G).9

⁹

Note that X has to belong to R as the agent cannot give away something he does not have. However, the definition is broad enough to allow that Y stands for anything that allows an agent to reach his goal.

As an outcome it generates a set of proposals ${\mathit{prop}}_{\mathit{Y}}=⟨\mathrm{(}{\mathit{E}}_{\mathit{Y}}\mathrm{,}\mathit{G}\mathrm{)}\mathrm{,}{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}⟩$ justifying only what the agent ${\mathit{Ag}}_{\mathit{i}}$ demands (i.e., ${\mathit{S}}_{\mathit{Y}}\ne \varnothing$ and ${\mathit{S}}_{\mathit{X}}=\varnothing$ ) where Y and the first set of resources (R) are disjoint sets, but ${\mathit{E}}_{\mathit{Y}}$ is a subset of R. The union of Y and ${\mathit{E}}_{\mathit{Y}}$ is a minimal set from which G can be deduced. The set X corresponds to the unused resources of R to achieve G.

If the $\mathsf{Gen}$ function is executed with adequate arguments, representing ${\mathit{Ag}}_{\mathit{i}}$ ’s beliefs with respect to his counterpart’s resources and goals, then we can get another set of proposals, which are the believed solutions of his opponent and include a justification of what the agent is offering (X). Namely, $\mathsf{Gen}\mathrm{(}{\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}\mathrm{,}{\mathit{R}}_{\mathit{i}}\mathrm{,}{\mathit{B}}_{\mathit{i}}{\mathit{G}}_{\mathit{j}}\mathrm{,}\mathit{j}\mathrm{)}$ generates a set of proposals ${\mathit{prop}}_{\mathit{X}}=⟨\mathrm{(}{\mathit{E}}_{\mathit{X}}\mathrm{,}{\mathit{G}}^{\prime }\mathrm{)}\mathrm{,}{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}⟩$ .

Proposition 5.6.

Given an agent ${\mathit{Ag}}_{\mathit{i}}$ , where his mental state is $$\begin{array}{c}{\mathit{MS}}_{\mathit{i}}=⟨{\mathit{R}}_{\mathit{i}}\mathrm{,}{\mathit{G}}_{\mathit{i}}\mathrm{,}{\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}\mathrm{,}{\mathit{B}}_{\mathit{i}}{\mathit{G}}_{\mathit{j}}\mathrm{,}{\mathit{H}}_{\mathit{i}}⟩\end{array}$$ then the following holds:

If ${\mathit{prop}}_{\mathit{Y}}\in \mathsf{Gen}\mathrm{(}{\mathit{R}}_{\mathit{i}}\mathrm{,}{\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}\mathrm{,}{\mathit{G}}_{\mathit{i}}\mathrm{,}\mathit{i}\mathrm{)}$ then ${\mathit{prop}}_{\mathit{Y}}\in \mathit{Proposal}$ and $\odot \mathrm{(}{\mathit{prop}}_{\mathit{Y}}\mathrm{)}\in {\mathcal{S}}_{\mathit{i}}$ ;

If ${\mathit{prop}}_{\mathit{X}}\in \mathsf{Gen}\mathrm{(}{\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}\mathrm{,}{\mathit{R}}_{\mathit{i}}\mathrm{,}{\mathit{B}}_{\mathit{i}}{\mathit{G}}_{\mathit{j}}\mathrm{,}\mathit{j}\mathrm{)}$ then ${\mathit{prop}}_{\mathit{X}}\in \mathit{Proposal}$ and $\odot \mathrm{(}{\mathit{prop}}_{\mathit{X}}\mathrm{)}\in {\mathcal{B}}_{\mathit{i}}{\mathcal{S}}_{\mathit{j}}$ .

Condition (1) establishes that the $\mathsf{Gen}$ function computes all the minimal proposals that are solutions for ${\mathit{Ag}}_{\mathit{i}}$ from his point of view, namely, using as parameters his resources ( ${\mathit{R}}_{\mathit{i}}$ ), his belief about the other agent’s resources ( ${\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}$ ) and his goal ( ${\mathit{G}}_{\mathit{i}}$ ). These proposals have the justification of what the agent demands. On the other hand, in (2) the $\mathsf{Gen}$ function computes the proposals that ${\mathit{Ag}}_{\mathit{i}}$ thinks that are solutions for ${\mathit{Ag}}_{\mathit{j}}$ , i.e., using as parameters his beliefs about the other agent’s resources ( ${\mathit{B}}_{\mathit{i}}{\mathit{R}}_{\mathit{j}}$ ), his own resources ( ${\mathit{R}}_{\mathit{i}}$ ) and his belief about the other agent’s goal ( ${\mathit{B}}_{\mathit{i}}{\mathit{G}}_{\mathit{j}}$ ). In this case, the function returns the justification of what the agent is offering. In summary, Proposition 5.6 shows that the possible proposals that can be generated via an implementation of $\mathsf{Gen}$ are potential solutions for the negotiation problem between the agents involved. To compute the proposal with a complete justification the agents proceed to properly combine the information obtained in ${\mathit{prop}}_{\mathit{X}}$ and ${\mathit{prop}}_{\mathit{Y}}$ which have a common solution $\odot \mathrm{(}\mathit{prop}\mathrm{)}$ . This process is implemented through high-level algorithms (see Section 5.5).

From the set of possible proposals obtained by the $\mathsf{Gen}$ function, the agent must select one exchange to configure the argument he will communicate to the other agent in his utterance. He must also decide which justification to include and whether to make a critique or not to the last proposal received.

5.3. Utterance selection: Argument and critique

In our approach, after the first illocution the agent’s utterances may be conformed by a critique and a proposal: $\mathrm{(}\mathit{Critique}\mathrm{,}\mathit{Proposal}\mathrm{)}$ . The critique and proposal communicated by ${\mathit{Ag}}_{\mathit{i}}$ are respectively defined by $\mathit{C}={⟨{\mathit{C}}_1\mathrm{,}{\mathit{C}}_2\mathrm{,}{\mathit{C}}_3⟩}_{\mathit{i}}$ and $⟨\mathcal{J}\mathrm{,}{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}⟩$ . The utterance selection mechanism of the negotiating agents will be in charge of the following actions: (i) with respect to the argument or proposal, to select – from a given set of possible exchanges (i.e., pairs ${[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}$ ) that an agent may send to its counterpart, the one which is the more appropriate from his point of view and to decide whether to include a justification (i.e., ${\mathit{S}}_{\mathit{X}}$ or ${\mathit{S}}_{\mathit{Y}}$ ) in the argument $\mathcal{J}$ and (ii) if it is convenient for him to make a critique and if so, which one to choose (i.e., ${\mathit{C}}_1$ , ${\mathit{C}}_2$ or ${\mathit{C}}_3$ ).

Argument selection. Different selection mechanisms may be defined for each negotiating agent; an overview of some relevant approaches can be seen in [26]. Reference [30] introduce a negotiation model based on an information-based measure (to represent the information gain) and utility-based function (to represent the utility gain). The negotiation strategies are based on two primitive concepts: intimacy (degree of closeness) and balance (degree of fairness). Arguments are selected in order to obtain a successful deal and to reach a target intimacy level.

In our approach, inspired by [30] we propose an agent selection mechanism based on an Information function $\mathit{I}:\mathit{H}\times \mathit{Proposal}\to \mathbb{R}$ (where H stands for the history of the negotiation, see Definition 3.1) and an Utility function $\mathit{U}:\mathit{Proposal}\to \mathbb{R}$ . Diverse selection mechanisms can be defined combining these functions to represent different agent behaviors. According to the agent personality and the social relation he has with his counterpart, the function combining I and U may be defined in a suitable way. For example, we can propose a possible selection function as follows: agents should select the proposal $\mathit{prop}\in \mathit{Proposal}$ that maximizes a weighted sum ${\mathit{\lambda }}_{\mathit{U}}\mathit{U}\mathrm{(}\mathit{prop}\mathrm{)}+{\mathit{\lambda }}_{\mathit{I}}\mathit{I}\mathrm{(}\mathit{prop}\mathrm{)}$ and in case of having more than one maximum, the proposal will randomly be chosen between them. For simplicity we can suppose that both agents use the same utility and information functions, but each agent may consider different weights, which stand for different kinds of agents (some possible alternatives are shown in our running example in Section 5.6).

The Utility function for ${\mathit{Ag}}_{\mathit{i}}$ (respectively for ${\mathit{Ag}}_{\mathit{j}}$ ) with respect to $\mathit{prop}=⟨\mathrm{(}{\mathit{S}}_{\mathit{X}}\mathrm{,}{\mathit{S}}_{\mathit{Y}}\mathrm{)}\mathrm{,}{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}⟩$ may be defined as the difference of the cost of the resources offered to be exchanged, and defined as follows: $$\begin{array}{c}{\mathit{U}}_{\mathit{i}}\mathrm{(}\mathit{prop}\mathrm{)}={\displaystyle \sum }_{\mathit{r}\in \mathit{Y}}\mathit{Cost}\mathrm{(}\mathit{r}\mathrm{)}-{\displaystyle \sum }_{\mathit{r}\in \mathit{X}}\mathit{Cost}\mathrm{(}\mathit{r}\mathrm{)}\end{array}$$ and the agents’ Information function is defined as: $$\begin{array}{ll}\hfill {\mathit{I}}_{\mathit{i}}\mathrm{(}\mathit{H}\mathrm{,}\mathit{prop}\mathrm{)}=& {\displaystyle \sum }_{\mathit{r}\in \mathit{Y}}{\mathbf{1}}_{\mathrm{get}}\mathrm{(}\mathit{H}\mathrm{,}\mathit{r}\mathrm{)}+{\displaystyle \sum }_{\mathit{r}\in \mathit{X}}{\mathbf{1}}_{\mathrm{give}}\mathrm{(}\mathit{H}\mathrm{,}\mathit{r}\mathrm{)}+{\displaystyle \sum }_{\mathit{r}\in {\mathit{E}}_{\mathit{Y}}}{\mathbf{1}}_{\mathrm{own}}\mathrm{(}\mathit{H}\mathrm{,}\mathit{r}\mathrm{)}+{\displaystyle \sum }_{\mathit{r}\in \mathit{G}}{\mathbf{1}}_{\mathrm{goal}}\mathrm{(}\mathit{H}\mathrm{,}\mathit{r}\mathrm{)}\mathrm{,}\end{array}$$ where ${\mathbf{1}}_{\mathrm{get}}\mathrm{(}\mathit{H}\mathrm{,}\mathit{r}\mathrm{)}$ returns 1 if for all $⟨⟨\mathrm{(}{\mathit{E}}_{\mathit{Y}}\mathrm{,}\mathit{G}\mathrm{)}\mathrm{(}{\mathit{E}}_{\mathit{X}}\mathrm{,}{\mathit{G}}^{\prime }\mathrm{)}⟩\mathrm{,}{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}⟩\in \mathit{H}$ , $\mathit{r}\notin \mathit{Y}$ . In a similar way ${\mathbf{1}}_{\mathrm{give}}\mathrm{,}{\mathbf{1}}_{\mathrm{own}}$ and ${\mathbf{1}}_{\mathrm{goal}}$ are defined. The intuition is that given a dialogue H a proposal $\mathit{prop}$ is more informative if its elements were not stated in previous locutions.

Critique selection. After receiving a proposal in an incoming utterance, an agent can make, in the next move, different kinds of critiques. For example if the agent ${\mathit{Ag}}_{\mathit{j}}$ receives from ${\mathit{Ag}}_{\mathit{i}}$ the proposal $\mathit{prop}=⟨\mathrm{(}{\mathit{S}}_{\mathit{X}}\mathrm{,}{\mathit{S}}_{\mathit{Y}}\mathrm{)}\mathrm{,}{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}⟩$ , ${\mathit{Ag}}_{\mathit{j}}$ can always select critique ${\mathit{C}}_1$ if the appropriate conditions hold, but he can only select ${\mathit{C}}_2$ and ${\mathit{C}}_3$ if the justification ${\mathit{S}}_{\mathit{X}}$ was given in the last argument proposed by ${\mathit{Ag}}_{\mathit{i}}$ (i.e., ${\mathit{S}}_{\mathit{X}}\ne \varnothing$ ).

Different types of agents may be defined considering diverse critical strategies. For instance, more critical agents will communicate all the possible critiques whereas more reserved ones may communicates only some of them, or none. We show the performance of different kinds of agents using diverse critique strategies in the simulations we have conducted (see Section 6).

5.4. Utterance interpretation

When an agent receives an incoming utterance, an interpretation mechanism must be invoked in order to update the agent’s mental state accordingly. As an utterance is composed of a proposal and a possible critique. i.e., ${\mathit{u}}_{\mathit{r}}=⟨\mathit{critique}\mathrm{,}\mathit{proposal}⟩$ , the agent can take advantage of both parts of the received message to update his beliefs.

Argument interpretation. In our framework, the proposal interpretation is based on the following intuition: since agents are truthful, benevolent and aware of their own resources, when an agent ${\mathit{Ag}}_{\mathit{j}}$ receives a proposal $\mathit{prop}=⟨⟨\mathrm{(}{\mathit{E}}_{\mathit{X}}\mathrm{,}{\mathit{G}}^{\prime }\mathrm{)}\mathrm{(}{\mathit{E}}_{\mathit{Y}}\mathrm{,}\mathit{G}\mathrm{)}⟩\mathrm{,}{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}⟩$ from ${\mathit{Ag}}_{\mathit{i}}$ , then ${\mathit{Ag}}_{\mathit{j}}$ can infer the following information:

If ${\mathit{Ag}}_{\mathit{i}}$ asks for Y, then ${\mathit{Ag}}_{\mathit{j}}$ believes ${\mathit{Ag}}_{\mathit{i}}$ does not have Y as resource.

If ${\mathit{Ag}}_{\mathit{i}}$ uses ${\mathit{E}}_{\mathit{Y}}$ , then ${\mathit{Ag}}_{\mathit{j}}$ believes ${\mathit{Ag}}_{\mathit{i}}$ has ${\mathit{E}}_{\mathit{Y}}$ as a resource.

If ${\mathit{Ag}}_{\mathit{i}}$ offers X, then ${\mathit{Ag}}_{\mathit{j}}$ believes ${\mathit{Ag}}_{\mathit{i}}$ has X as resource.

If ${\mathit{Ag}}_{\mathit{i}}$ wants to reach G, then ${\mathit{Ag}}_{\mathit{j}}$ believes ${\mathit{Ag}}_{\mathit{i}}$ has G as Goal.

Then, the agents will change their beliefs according to the intuitions presented before, using belief revision operations. Let $\mathit{contract}$ and $\mathit{revise}$ be implementations of the operators ≈ and ∗ respectively (see Definitions 5.3 and 5.4), and $\mathit{prop}=⟨⟨\mathrm{(}{\mathit{E}}_{\mathit{X}}\mathrm{,}{\mathit{G}}^{\prime }\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{E}}_{\mathit{Y}}\mathrm{,}\mathit{G}\mathrm{)}⟩\mathrm{,}{[[\mathit{X}\mathrm{,}\mathit{Y}]]}_{\mathit{i}}⟩$ an ${\mathit{Ag}}_{\mathit{i}}$ proposal received by ${\mathit{Ag}}_{\mathit{j}}$ . The following steps, which can be seen as variable assignments, implement the agent’s interpretation process:

1. ${\mathit{B}}_{\mathit{j}}{\mathit{R}}_{\mathit{i}}\leftarrow \mathit{contract}\mathrm{(}{\mathit{B}}_{\mathit{j}}{\mathit{R}}_{\mathit{i}}\mathrm{,}\mathit{Y}\mathrm{)}$ .

2. ${\mathit{B}}_{\mathit{j}}{\mathit{R}}_{\mathit{i}}\leftarrow \mathit{revise}\mathrm{(}{\mathit{B}}_{\mathit{j}}{\mathit{R}}_{\mathit{i}}\mathrm{,}{\mathit{E}}_{\mathit{Y}}\mathrm{)}$ .

3. ${\mathit{B}}_{\mathit{j}}{\mathit{R}}_{\mathit{i}}\leftarrow \mathit{revise}\mathrm{(}{\mathit{B}}_{\mathit{j}}{\mathit{R}}_{\mathit{i}}\mathrm{,}\mathit{X}\mathrm{)}$ .

4. ${\mathit{B}}_{\mathit{j}}{\mathit{G}}_{\mathit{i}}\leftarrow \mathit{revise}\mathrm{(}{\mathit{B}}_{\mathit{j}}{\mathit{G}}_{\mathit{i}}\mathrm{,}\mathit{G}\mathrm{)}$ .

Notice that in our approach the agent mental state does not represent the beliefs about his counterpart beliefs (e.g., ${\mathit{B}}_{\mathit{i}}{\mathit{B}}_{\mathit{j}}\mathit{\beta }$ ). Thus, an agent cannot use the support of what his counterpart is offering ${\mathit{E}}_{\mathit{X}}$ to make a revision of this kind of beliefs.

Critique interpretation. When an agent ${\mathit{Ag}}_{\mathit{j}}$ receives a critique from ${\mathit{Ag}}_{\mathit{i}}$ to his last proposal: $\mathit{C}={⟨{\mathit{C}}_1\mathrm{,}{\mathit{C}}_2\mathrm{,}{\mathit{C}}_3⟩}_{\mathit{i}}$ , then ${\mathit{Ag}}_{\mathit{j}}$ can infer the following information:

1. If ${\mathit{C}}_1\ne \varnothing$ and ${\mathit{C}}_1\cap {\mathit{R}}_{\mathit{i}}=\varnothing$ then, ${\mathit{Ag}}_{\mathit{j}}$ believes ${\mathit{Ag}}_{\mathit{i}}$ does not have ${\mathit{C}}_1$ resources.

2. If ${\mathit{C}}_2\ne \varnothing$ and ${\mathit{C}}_2\cap {\mathit{R}}_{\mathit{i}}=\varnothing$ then, ${\mathit{Ag}}_{\mathit{j}}$ believes ${\mathit{Ag}}_{\mathit{i}}$ does not have ${\mathit{C}}_2$ resources.

3. If ${\mathit{C}}_3\ne \varnothing$ and ${\mathit{C}}_3\cap {\mathit{G}}^{\prime }=\varnothing$ then, ${\mathit{Ag}}_{\mathit{j}}$ believes that ${\mathit{C}}_3$ is not part of ${\mathit{Ag}}_{\mathit{i}}$ ’s goals.

Using belief revision operations, ${\mathit{Ag}}_{\mathit{j}}$ will change his beliefs according to the information received in the critiques. In this case only the $\mathit{contract}$ operator is needed and the agent’s interpretation is as follows:

1. ${\mathit{B}}_{\mathit{j}}{\mathit{R}}_{\mathit{i}}\leftarrow \mathit{contract}\mathrm{(}{\mathit{B}}_{\mathit{j}}{\mathit{R}}_{\mathit{i}}\mathrm{,}{\mathit{C}}_1\mathrm{)}$ .

2. ${\mathit{B}}_{\mathit{j}}{\mathit{R}}_{\mathit{i}}\leftarrow \mathit{contract}\mathrm{(}{\mathit{B}}_{\mathit{j}}{\mathit{R}}_{\mathit{i}}\mathrm{,}{\mathit{C}}_2\mathrm{)}$ .

3. ${\mathit{B}}_{\mathit{j}}{\mathit{G}}_{\mathit{i}}\leftarrow \mathit{contract}\mathrm{(}{\mathit{B}}_{\mathit{j}}{\mathit{G}}_{\mathit{i}}\mathrm{,}{\mathit{C}}_3\mathrm{)}$ .

In this way, an agent that takes full advantage of the utterance interpretation process can make that the computation of the belief set ${\mathcal{B}}_{\mathit{i}}{\mathcal{S}}_{\mathit{j}}$ may be closer to ${\mathcal{S}}_{\mathit{j}}$ and consequently, the resulting set of possible deals ${\mathcal{B}}_{\mathit{i}}\mathcal{D}$ may be closer to $\mathcal{D}$ as well (as illustrated in Fig. 3).

5.5. The agent’s decision model

We have implemented the agent’s decision making apparatus (defined in Section 3) by using two algorithms $\mathit{Init}$ and $\mathit{Answer}$ . The algorithm $\mathit{Init}$ is in charge of starting the negotiation. First, it selects a proposal (including a justification) that the agent ${\mathit{Ag}}_{\mathit{i}}$ believes is a deal ( ${\mathcal{B}}_{\mathit{i}}\mathcal{D}$ ) which it has not been proposed before. If such a proposal does not exist, it tries to send a proposal associated with his own solutions ( ${\mathcal{S}}_{\mathit{i}}$ ). If this fails, the agent sends a withdraw message. On its turn, $\mathit{Answer}$ receives a proposal and a possible critique. Firstly, the agent’s beliefs are revised and it checks if the associated solution of the proposal is a solution to the agent’s problem, and in that case the proposal is accepted. If that is not the case, a critique selection mechanism is computed and $\mathit{Init}$ is invoked to generate a new proposal. High-level algorithms for ${\mathit{Init}}_{\mathit{i}}$ and ${\mathit{Answer}}_{\mathit{i}}$ are given next.

Algorithm 1

Init

Algorithm 2

Answer

Algorithm 1 : In line 1, the function $\mathsf{Gen}$ (i.e., a suitable implementation of the $\mathsf{Gen}$ function specified in Definition 5.5) is used to compute the set of proposals ${\mathit{propSet}}_{\mathit{Y}}$ such that their associated solutions belong to ${\mathcal{S}}_{\mathit{i}}$ (see Proposition 5.6). Similarly, in line 2, $\mathsf{Gen}$ is used to compute the set of proposals ${\mathit{propSet}}_{\mathit{X}}$ that the agent believes their associated solutions belong to ${\mathcal{B}}_{\mathit{i}}{\mathcal{S}}_{\mathit{j}}$ (see Proposition 5.6). In line 3, the set ${\mathit{propSet}}_{\mathit{X}\mathit{Y}}$ is computed combining the proposals of ${\mathit{propSet}}_{\mathit{X}}$ and ${\mathit{propSet}}_{\mathit{Y}}$ such that their associated solutions are the same and then, are potential deals. In line 4, those proposals that have been offered before are discarded. The $\mathit{select}$ function chooses one proposal out of the set $\mathit{propSet}$ of possible candidate proposals. Finally, the selected $\mathit{prop}$ is added to H.

Algorithm 2 : In line 1, the history H is updated, Then, in lines 2–8, the agent updates his mental state following the steps of utterance interpretation presented in Section 5.4. In lines 9–10 the set ${\mathit{propSet}}_{\mathit{Y}}$ is computed and the agent checks if the associated solution of received proposal ( $\mathit{prop}$ ) is a solution for him. Then, in line 13 the critique is generated. Finally, in line 14, for generating a counter-proposal the same lines of code as the ones in $\mathit{Init}$ are to be executed (as $\mathit{Init}$ generates proposals). Therefore, for the sake of simplicity and in order to avoid repeating code, a call to $\mathit{Init}$ is used.

The proposed argumentation-based negotiation framework for two agents equipped with belief revision has been implemented using logic programming following the algorithms presented above. Based on such algorithms, concrete negotiating agents can be specified by instantiating their mental state and setting the selection function in charge to choose the proposal to negotiate and the communication strategy, responsible for deciding the justification and the critique to expose.

5.6. Running example: The $\mathit{HIA}$ problem revisited

We consider the modified version of the Home Improvement Agents example [20] presented in Section 1, as a case study of our approach. We will assume that ${\mathit{Ag}}_1$ and ${\mathit{Ag}}_2$ are two collaborative agents that negotiate for mutual benefit. In the proposed scenario, ${\mathit{Ag}}_1$ has the following initial mental state: $$\begin{array}{ll}\hfill & {\mathit{R}}_1=\{\mathit{screw}\mathrm{,}\mathit{hammer}\mathrm{,}\mathit{screw}\wedge \mathit{screwDriver}\to \mathit{hangMir}\mathrm{,}\mathit{hammer}\wedge \mathit{nail}\to \mathit{hangPict}\}\mathrm{,}\\ \hfill & {\mathit{G}}_1=\{\mathit{hangPict}\}\mathrm{,}\\ \hfill & {\mathit{B}}_1{\mathit{R}}_2=\{\mathit{nail}\mathrm{,}\mathit{screwDriver}\mathrm{,}\mathit{screw}\wedge \mathit{screwDriver}\to \mathit{repairDesk}\}\mathrm{,}\\ \hfill & {\mathit{B}}_1{\mathit{G}}_2=\{\mathit{repairDesk}\}\mathrm{,}\\ \hfill & {\mathit{H}}_1=[·]\end{array}$$ and ${\mathit{Ag}}_2$ has as initial mental state: $$\begin{array}{ll}\hfill & {\mathit{R}}_2=\{\mathit{nail}\mathrm{,}\mathit{screwDriver}\mathrm{,}\mathit{hammer}\wedge \mathit{nail}\to \mathit{hangMir}\}\mathrm{,}\\ \hfill & {\mathit{G}}_2=\{\mathit{hangMir}\}\mathrm{,}\\ \hfill & {\mathit{B}}_2{\mathit{R}}_1=\{\mathit{screw}\mathrm{,}\mathit{screw}\wedge \mathit{screwDriver}\to \mathit{hangPict}\}\mathrm{,}\\ \hfill & {\mathit{B}}_2{\mathit{G}}_1=\{·\}\mathrm{,}\\ \hfill & {\mathit{H}}_2=[·].\end{array}$$ In this example, we consider that the agents select the proposal $\mathit{prop}\in \mathit{Proposal}$ that maximizes a weighted sum defined in Section 5.3: ${\mathit{\lambda }}_{\mathit{U}}\mathit{U}\mathrm{(}\mathit{prop}\mathrm{)}+{\mathit{\lambda }}_{\mathit{I}}\mathit{I}\mathrm{(}\mathit{prop}\mathrm{)}$ .

For ${\mathit{Ag}}_1$ the weights are: ${\mathit{\lambda }}_{\mathit{U}}=0.25$ , ${\mathit{\lambda }}_{\mathit{I}}=2$ , prioritizing the proposals that are more informative and for ${\mathit{Ag}}_2$ : ${\mathit{\lambda }}_{\mathit{U}}=2$ , ${\mathit{\lambda }}_{\mathit{I}}=0.25$ , preferring those proposals that have higher utility function. We also assume that the different resources they negotiate have the same costs for them: $$\begin{array}{ll}\hfill \mathit{Cost}=& \{\mathrm{(}\mathit{hangMir}\mathrm{,}10\mathrm{)}\mathrm{,}\mathrm{(}\mathit{hangPict}\mathrm{,}10\mathrm{)}\mathrm{,}\mathrm{(}\mathit{repairDesk}\mathrm{,}10\mathrm{)}\mathrm{,}\mathrm{(}\mathit{nail}\mathrm{,}2\mathrm{)}\mathrm{,}\mathrm{(}\mathit{screw}\mathrm{,}2\mathrm{)}\mathrm{,}\mathrm{(}\mathit{hammer}\mathrm{,}4\mathrm{)}\mathrm{,}\\ \hfill & \mathrm{(}\mathit{screwDriver}\mathrm{,}4\mathrm{)}\mathrm{,}\mathrm{(}\mathit{screw}\wedge \mathit{screwDriver}\to \mathit{repairDesk}\mathrm{,}8\mathrm{)}\mathrm{,}\\ \hfill & \mathrm{(}\mathit{screw}\wedge \mathit{screwDriver}\to \mathit{hangMir}\mathrm{,}8\mathrm{)}\mathrm{,}\mathrm{(}\mathit{hammer}\wedge \mathit{nail}\to \mathit{hangPict}\mathrm{,}8\mathrm{)}\mathrm{,}\\ \hfill & \mathrm{(}\mathit{screw}\wedge \mathit{screwDriver}\to \mathit{hangPict}\mathrm{,}8\mathrm{)}\}.\end{array}$$

Both agents are equipped with full belief revision. Regarding the communication strategy, they give complete justifications and include all the possible critiques ( ${\mathit{C}}_1$ , ${\mathit{C}}_2$ or ${\mathit{C}}_3$ ) in their utterances. The whole dialogue obtained in the negotiation program for this scenario is the following:

Proposal: I propose you provide me $[\mathit{nail}]$ because with $[\mathit{hammer}\mathrm{,}\mathit{nail}\wedge \mathit{hammer}=\mathrm{>}\mathit{hangPict}]$ I can achieve $[\mathit{hangPict}]$ in exchange I offer you $[\mathit{screw}]$ because I Believe if you use $[\mathit{screwDriver}\mathrm{,}\mathit{screwDriver}\wedge \mathit{screw}=\mathrm{>}\mathit{repairDesk}]$ you can achieve $[\mathit{repairDesk}]$

Critique: I do not have $[\mathit{screwDriver}\wedge \mathit{screw}=\mathrm{>}\mathit{repairDesk}]$ and my goal is not $[\mathit{repairDesk}]$

Proposal: I propose you provide me $[\mathit{hammer}]$ because with $[\mathit{nail}\mathrm{,}\mathit{nail}\wedge \mathit{hammer}=\mathrm{>}\mathit{hangMir}]$ I can achieve $[\mathit{hangMir}]$ in exchange I offer you $[\mathit{screwDriver}]$ because I Believe if you use $[\mathit{screw}\mathrm{,}\mathit{screwDriver}\wedge \mathit{screw}=\mathrm{>}\mathit{hangPict}]$ you can achieve $[\mathit{hangPict}]$

Critique: I do not have $[\mathit{screwDriver}\wedge \mathit{screw}=\mathrm{>}\mathit{hangPict}]$

Proposal: I propose you provide me $[\mathit{hangPict}]$ because with $[]$ I can achieve $[\mathit{hangPict}]$ in exchange I offer you $[\mathit{screw}\mathrm{,}\mathit{screwDriver}\wedge \mathit{screw}=\mathrm{>}\mathit{hangMir}]$ because I Believe if you use $[\mathit{screwDriver}]$ you can achieve $[\mathit{hangMir}]$

Critique: I do not have the requested $[\mathit{hangPict}]$

Proposal: I propose you provide me $[\mathit{screw}\mathrm{,}\mathit{screwDriver}\wedge \mathit{screw}=\mathrm{>}\mathit{hangMir}]$ because with $[\mathit{screwDriver}]$ I can achieve $[\mathit{hangMir}]$ in exchange I offer you $[\mathit{nail}]$ because I Believe if you use $[\mathit{hammer}\mathrm{,}\mathit{nail}\wedge \mathit{hammer}=\mathrm{>}\mathit{hangPict}]$ you can achieve $[\mathit{hangPict}]$

Proposal: Accept

6. Simulations to assess different communication strategies

Simulations of bilateral negotiation were carried out considering different scenarios, to assess the benefits of using different communication strategies in agents equipped with full belief revision, i.e., agents using all the information received in the last message to update their mental state.

Generating the scenarios. All the simulation we have conducted are based on 100 randomly generated negotiation scenarios. The process for generating a scenario is based on randomly selecting the goals for each agent ${\mathit{G}}_1\mathrm{,}{\mathit{G}}_2\in {\mathit{Goal}}_{\mathcal{L}}$ , generating then three disjoint sets of resources $\mathit{F}\mathrm{,}\mathit{S}\mathrm{,}\mathit{T}\subset {\mathit{Resource}}_{\mathcal{L}}$ such that $\mathit{F}⊢{\mathit{G}}_1$ , $\mathit{S}⊢{\mathit{G}}_2$ and $\mathit{T}⊢{\mathit{G}}_1\wedge {\mathit{G}}_2$ . Then, the mental state for ${\mathit{Ag}}_1$ and ${\mathit{Ag}}_2$ was defined as ${\mathit{MS}}_1=⟨{\mathit{R}}_1\mathrm{,}{\mathit{G}}_1\mathrm{,}{\mathit{B}}_1{\mathit{R}}_2\mathrm{,}{\mathit{B}}_1{\mathit{G}}_2\mathrm{,}{\mathit{H}}_1⟩$ and ${\mathit{MS}}_2=⟨{\mathit{R}}_2\mathrm{,}{\mathit{G}}_2\mathrm{,}{\mathit{B}}_2{\mathit{R}}_1\mathrm{,}{\mathit{B}}_2{\mathit{G}}_1\mathrm{,}{\mathit{H}}_2⟩$ such that:

1. ${\mathit{R}}_1={\mathit{F}}_1\cup {\mathit{S}}_1\cup {\mathit{T}}_1$ , ${\mathit{R}}_2={\mathit{F}}_2\cup {\mathit{S}}_2\cup {\mathit{T}}_2$ , where ${\mathit{F}}_1\mathrm{,}{\mathit{F}}_2$ (resp. ${\mathit{S}}_1$ , ${\mathit{S}}_2$ , and ${\mathit{T}}_1$ , ${\mathit{T}}_2$ ) are partitions of F (resp. S and T).

2. ${\mathit{B}}_1{\mathit{R}}_2\subset {\mathit{R}}_2\cup {\mathit{R}}_1$ , ${\mathit{B}}_2{\mathit{R}}_1\subset {\mathit{R}}_1\cup {\mathit{R}}_2$ .

3. ${\mathit{B}}_1{\mathit{G}}_2={\mathit{G}}_1$ , ${\mathit{B}}_2{\mathit{G}}_1={\mathit{G}}_2$ .

4. ${\mathit{H}}_1={\mathit{H}}_2=⟨·⟩$ .

We can see that $\mathit{F}={\mathit{F}}_1\cup {\mathit{F}}_2$ is a solution for ${\mathit{Ag}}_1$ , $\mathit{S}={\mathit{S}}_1\cup {\mathit{S}}_2$ is a solution for ${\mathit{Ag}}_2$ , and $\mathit{T}={\mathit{T}}_1\cup {\mathit{T}}_2$ can be a solution for both agents. With this allocation of resources and agent’s beliefs, we ensure that initially each agent cannot achieve his own goal by himself and both agents have incomplete and incorrect beliefs about their counterpart.

Simulations were run using two negotiating agents of the same type in 100 different negotiating scenarios. In all cases both agents used the selection function described in Section 5.3, i.e., the agents select the proposal $\mathit{prop}\in \mathit{Proposal}$ that maximizes a weighted sum ${\mathit{\lambda }}_{\mathit{U}}\mathit{U}\mathrm{(}\mathit{prop}\mathrm{)}+{\mathit{\lambda }}_{\mathit{I}}\mathit{I}\mathrm{(}\mathit{prop}\mathrm{)}$ , using a balanced approach that equally weighs the informativeness of the proposal and its associated utility, i.e., ${\mathit{\lambda }}_{\mathit{U}}={\mathit{\lambda }}_{\mathit{I}}=0.5$ . Besides, in all the negotiations it was assumed that ${\mathit{Ag}}_1$ starts the negotiation dialogue.

In each simulation we analyzed (i) whether there was an agreement in the negotiation (i.e., it finished with $\mathit{accept}$ or $\mathit{withdraw}$ ) and (ii) the length of the negotiation process (i.e. the number of iterations). Besides, we were interested in evaluating the evolution of the agent’s beliefs with respect to his initial mental state. In order to do this, we analyzed two ratios: for each scenario we evaluated the decrease of the agent’s missing and incorrect beliefs (see Definition 3.3). We computed the ratio of these two kinds of beliefs an agent has at the end of negotiation with respect to the initial ones he had, as follows: $$\begin{array}{c}\mathrm{\left(}\right|{\mathit{M}}^{\mathrm{end}}|+|{\mathit{F}}^{\mathrm{end}}\left|\mathrm{\right)}\mathrm{/}\mathrm{\left(}\right|{\mathit{M}}^{\mathrm{init}}|+|{\mathit{F}}^{\mathrm{init}}\left|\mathrm{\right)}.\end{array}$$ Besides, for each case we compute how the correct beliefs increase during the negotiation process. This is computed as: $$\begin{array}{c}\left|{\mathit{T}}^{\mathrm{end}}\right|\mathrm{/}\left|{\mathit{T}}^{\mathrm{init}}\right|.\end{array}$$

6.1. Agents that communicate different justifications

After creating these negotiation scenarios, three different types of agents were distinguished based on whether the communicated proposals are more or less informative (detailed in Section 4). In each case their Decision Making Apparatus was adapted to generate the required argument composition.

1. NJ Agents: these agents do not include any justification in their proposals ( ${\mathit{S}}_{\mathit{X}}={\mathit{S}}_{\mathit{Y}}=\varnothing$ ).

2. PJ Agents: these agents give a partial explanation to their proposal, justifying what they are demanding ( ${\mathit{S}}_{\mathit{Y}}\ne \varnothing$ ).

3. CJ Agents: agents that communicates the complete explanation of their proposals, justifying the offer and the demand ( ${\mathit{S}}_{\mathit{X}}\ne \varnothing$ and ${\mathit{S}}_{\mathit{Y}}\ne \varnothing$ ).

Note that these different types of agents (NJ, PJ, CJ) share the same underlying structure and the only difference among them is associated with the arguments they give in their utterances. If more information is provided in their messages, the use of belief revision to update their mental states can be increased. Nevertheless, the role of the belief revision process during the negotiation of PJ Agents and CJ Agents will be the same. This is because the only difference between these kind of agents is that CJ agents add the support of what they are offering ( ${\mathit{S}}_{\mathit{X}}$ ) in their messages and these beliefs can not be used to revise the agents’ mental state in our approach, that is because the agent’s mental state is not represented in the agent’s beliefs about his counterpart’s beliefs. Thus, in this first stage of simulations, to assess the importance of the different explanations an agent can give in the proposals, without including a critique, we run negotiations using only NJ and PJ Agents, as CJ Agents will behave the same than the PJ ones.

6.1.1. Simulations using NJ and PJ agents

The output of negotiations using NJ and PJ Agents on the 100 negotiation scenarios are shown in Fig. 4. We can observe that NJ Agents reached an agreement in 93% of the negotiations, whereas in the simulations using PJ Agents we obtained a slightly higher percentage, $96\mathrm{\%}$ of the cases.

Fig. 4.

Output of Negotiations with: (a) NJ Agents and (b) PJ Agents.

Concerning the reduction of missing and incorrect beliefs for ${\mathit{Ag}}_1$ about his counterpart, NJ Agents have had an average slightly lower (57.05%) than the one for PJ Agents (60.65%). The average of increase for correct beliefs is 178.89% for NJ Agents and 176.48% for PJ Agents (i.e., percentages which are very similar).

These simulations allow to assess the impact of communicating more informed proposals allowing to implement deeper belief revision on the negotiating agents. On the one hand, PJ Agents reached agreements in more cases (96%) than NJ Agents, which do not give explanations (the percentage increased $3\mathrm{\%}$ ). On the other hand, as expected the negotiation length tends to be shorter in those agents that communicates more explanations and take advantage of belief revision (as the average number of iterations decreased from 18.67 NJ Agents to 15.93 for PJ Agents). In these preliminar results, PJ Agents have achieved agreements in slightly more negotiation cases and faster than NJ Agents. However, they end the negotiation having on the average slightly more missing and incorrect beliefs and less correct beliefs than the NJ Agents. Intuitively, PJ Agents are able to reach an agreement under more incomplete or incorrect beliefs. Further experimentation may be conducted to analyzed the characteristic of the negotiation cases where the inclusion of justifications in the utterances the agents exchange, have more impact.

Notice that this was the first stage of our empirical analysis and from the results obtained for PJ Agents (i.e. the same apply for CJ agents), we can use agents with full justification to assess different communication strategies including different critiques.

6.2. Agents that communicate different critiques

In this stage we want to analyze the impact that the introduction of critiques in the agent’s utterances has in the negotiation process. For these simulations we use the agents that communicate proposals with complete explanations (i.e., CJ Agents), because the utterances of these type of agents can be answered with different types of critiques (i.e., ${\mathit{C}}_1$ , ${\mathit{C}}_2$ or ${\mathit{C}}_3$ ). We propose three types of CJ agents, using different strategies of critique selection:

1. PC1 Agents: these agents communicate the first critique possible, considering a list of priorities, for this case we consider the following orders ${\mathit{C}}_1$ – ${\mathit{C}}_2$ – ${\mathit{C}}_3$ .

2. PC2 Agents: for these agents the list of priorities is: ${\mathit{C}}_3$ – ${\mathit{C}}_1$ – ${\mathit{C}}_2$ .

3. FC Agents: this type of agents exposes all the critiques that are possible.

Notice that PC1 and PC2 Agents communicate only one critique in each utterance whereas FC Agents can expose at most three critiques in each message. The outputs of the simulations realized with the PC2 and FC Agents are shown in Fig. 5.

Fig. 5.

Output of Negotiations with: (a) PC2 Agents and (b) FC Agents.

Table 1 summarizes the results obtained with all the simulations run using different types of agents. Note that 100% agreements are reached in all the simulation with agents that introduce critiques in their utterances, in contrast with the results obtained with the agents that justify the proposals but without critiques (NJ and PJ Agents), where less agreements were reached. Regarding the duration of the negotiation, all the agents using strategies that involve critiques (i.e., PC1, PC2 and FC) have lower average number of iterations than the agents which do not include critiques. Among them, those agents that implement a full critique (i.e., FC Agents) and then communicate more information obtain a much lower average. The results obtained by the simulations with PC1 and PC2 Agents are very similar. We emphasize that the FC Agents reached agreements increasing the correct beliefs about their counterpart (resulting an average of 185.71% final beliefs with respect to initial ones, see Fig. 6(b)) but still maintaining incorrect and missing beliefs about them (obtained an average of 59.56% shown in Fig. 6(a)). Similarly results on the belief sets occurred with the other types of critiquing agents.

Table 1

Simulation’s results

Strategy	Deals	Average iterations	Missing and wrong Bel.	Correct Bel.
PC1	100	13.75	54.86	185.85
PC2	100	13.40	59.55	173.05
FC	100	8.57	59.56	185.71

Fig. 6.

FC Agents: (a) Reduction of missing and incorrect beliefs; (b) Acquired knowledge.

Finally, we can observe that there is a considerable difference in the negotiation results (i.e., considering the number of deals reached and average of iterations) between agents that incorporate critiques in their utterance. This is because these types of agents can strengthen the belief revision process, but without communicating all the knowledge they have.

7. Discussion. Related work

In this paper we have proposed an argumentation-based negotiation model for two collaborative agents equipped with full belief revision and we focussed on the relevance of the information the agents communicate to their counterpart in the negotiation dialogue. In order to do this, in this work we have extended the argumentation-based negotiation model we proposed in [24]. The focus was on the belief revision applied by the agents and how they took advantage of the incoming information through the received messages. In this paper we have improved the negotiation protocol allowing the agents to exchange more informative messages. Firstly, the agent’s illocutions may now also include a critique (in addition to a proposal) and the agent’s decision mechanism must decide which kind of critique to communicate in each move. Besides a more complex argument can support the proposal exchange (justifying the demand, the offer or both). As a consequence, different kinds of agent may be defined using different communication strategies. In our approach we use a logic-based argumentation framework, where arguments are associated with proposals that allow agents to achieve agreements, and attacks correspond to critiques that defeat proposals (in terms of resource availability and possible conflicts in achieving goals). It must be noticed, however, that in our framework agents cannot introduce critiques about critiques (as it would be the case with arguments defeating arguments in most argumentation frameworks). We contend that in many negotiation scenarios it might be difficult to identify a critique about a critique (being advisable to persuade rather than to deepen the confrontation).

Research focused on providing a suitable model for capturing different negotiation strategies in agent dialogues was previously presented in [22]. In that case the study was made on a different negotiation scenario, defining the so-called double knapsack negotiation problem along with a sequential negotiation protocol, providing different concession information strategies. The inclusion of critiques in the agents’ dialogues have been also explored in the context of recommendation systems and showed improvements in the recommendations obtained [9].

In contrast with the original argumentative framework to solve the $\mathit{HIA}$ problem in [20], our negotiation model allows the agents to gain and revise their beliefs as the dialogue takes place. Consequently, in our approach an agent does not need to have initial (or correct) beliefs about the other agent involved in the negotiation also the utterances the agents exchange are more complex and informative. In [21] a similar scenario is analyzed, but agents are aware of all the agents’ resources and the agents’ plans (or their knowledge about plans) are not consider negotiable. We think that our proposal is more flexible in this respect, as plans are also negotiation objects in our formalization. There have been previous approaches integrating belief revision and negotiation. In [34] and [33] a formal characterization of negotiation from a belief revision perspective are given, but no implementation issues are considered.

Argument-based negotiation has been quite an active area in the last years. In [11] an excellent survey of recent advances in argument-based negotiation is presented. They discuss these contributions in the context of the argument-based reasoning mechanisms the agents use for negotiating, the protocols the agents use for conveying arguments and offers and, the strategies that determine their choices at each step of the negotiation. In the context of this article, a relevant approach to argumentation-based negotiation can be seen in [3] where the proposed framework makes it possible to study the outcomes of the negotiation process. In contrast with this approach, our proposal rely on the characterization of belief revision operations to model the agent’s arguments generation, which their claims are the resources to be exchanged. Formal models of belief change can be very helpful in providing suitable frameworks for rational agents [6], in which the information from inter-agent dialogues can be better exploited. In [18] the authors present a computational model implemented in an experimental dialogue system (DS). Communication in a natural language between two participants A and B is considered, where A has a communicative goal that his/her partner B will make a decision to perform an action D. Agent A argues the usefulness, pleasantness, etc. of D (including its consequences), in order to guide B’s reasoning in a desirable direction. In contrast with our approach, the whole negotiation process is based on natural language, distinguishing persuasion from information seeking dialogues, rather on applying belief revision on a knowledgebase expressed in a logical language. In [7] the authors propose a model and an algorithm for analyzing tendencies in group decision-making in argument-based negotiation. In contrast with our model, the authors do not rely on belief revision mechanisms for decision making. The proposed model allows the agent to redefine his objectives to maximize both his and group satisfaction. In contrast, our approach is focused on a 2-agent dialogue (proponent and opponent), and does not consider the notion of group decision-making.

Additionally, it must be noted that in our proposal we assume that agents are benevolent. This approach can also be found in several other frameworks as e.g., [20]. In addition, in our work, agents are assumed to be truthful. Recent research has led to consider other situations such as negotiation among dishonest agents [29], which is an interesting scenario for future work.

8. Conclusions. Future work

In this article we have assessed the relevance of the exchanging information in an argumentation-based negotiation model for two collaborative agents that may have incomplete and possibly incorrect beliefs about their opponents. To take advantage of the incoming information the agents are equipped with belief revision operators to interpret the received utterances and to generate new proposals.

We have extended the original argumentation-based negotiation model proposed in [24] allowing the agents to exchange more complex and informative messages. An agent’s illocutions may now also include a critique (in addition to a proposal), resulting in a more complete argument that can support the proposal exchange (justifying the demand, the offer or both). As a consequence, different kinds of agents may be defined using different communication strategies. These strategies will help the agents determine what information to include in their utterances: an agent may be more or less communicative, giving an explanation of why he is not willing to accept a proposal (i.e., a critique) or explaining the reason of the proposed solution.

When agents want to achieve their goals, they engage in a benevolent dialogue exchanging proposals together with possible critiques. During the negotiation, the agents continuously update their mental states to generate new proposals, more likely to be accepted. As a running example, a revised version of the $\mathit{HIA}$ was solved by our negotiation program showing how the proposed negotiation model can be used to solve this kind of cooperative problem under incomplete and incorrect beliefs, and illustrating the role information communication has in the negotiation dialogue.

We have carried out an empirical analysis of our proposal, assessing the impact of considering agents with different communication strategies during the negotiation process. From this analysis we can conclude that the introduction of more informative illocutions have impact on the overall negotiation process. We obtained the 100% of agreements in all the strategies that introduce critiques, showing that better informed illocutions have impact on the success of the negotiation. Notice that in all the strategies studied, the agents reach these results without knowing all the correct information and maintaining some incorrect beliefs about their counterpart.

Part of our future work is focused on assessing the different communication strategies from the point of view of the quality of the results of the negotiation (e.g., using some utility measure associated with the agreed exchange). We are also interested in extending the proposed model to an n-party scenario, where different agents can get involved in dialogues. Clearly, such scenario would involve additional aspects which deserve further analysis (e.g. satisfaction in group decision making, as discussed in [7]), which are outside the scope of this article.

Furthermore, we want also to identify different kinds of negotiation problems for which a particular type of agent (i.e., using a specific communication strategy) are to be preferred, considering the trade-off between negotiation results and computational complexity. Also, we want to evaluate the role of the information exchange and belief revision in other kinds of negotiating agents (e.g., dishonest, less collaborative, etc.) and different scenarios.

In order to fully instantiate flexible agents in real domains a more complex agent architecture would be needed, expanding the one presented in this article. Such a model would include a Planner enabling agents to plan dynamically and under real-time constraints (e.g. following [19]), using as well a richer and more expressive representation of the agent’s beliefs. Such beliefs may include grades, i.e. a quantification of uncertainty [8] or different multi-level opponent models [27]. Also, the representation of higher level beliefs (i.e. beliefs about other agents beliefs) may be included using for instance, dynamic epistemic logic [32], which allows to specify the static and dynamic aspects of multi-agent systems. All these features would increase the expressive power of the language of negotiation.

Another interesting topic for future research is the integration our approach with of so-called agent-planning program [15], which suitably mixes automated planning with agent-oriented programming. Agent planning programs are finite-state programs, possibly containing loops, whose atomic instructions consist of a guard, a maintenance goal, and an achievement goal, which act as precondition-invariance-postcondition assertions in program specification. In this setting, argumentation and belief revision could be also integrated for capturing different decision making capabilities.

We think that deepening the integration of communication strategies and belief revision in the context of ABN agents is a very promising area for future research, paving the way for the deployment of intelligent software systems for solving real-world problems.