Keywords

1 Introduction

Conflicts resolve techniques are very useful to overcome misunderstanding caused by the differences in the opinions, beliefs, and goals of different parties. Negotiation has been one of the most used techniques [1,2,3]. Further, with the growth of Artificial Intelligence (AI) techniques and their huge success in the last decades, the automation of negotiation where software agents negotiate on behalf of humans was the interest of many researchers [4, 5]. Automated negotiation gives software agents with conflicting positions a way to find a beneficial settlement [6].

From a similar perspective, argumentation is another way to reach an agreement between parties that have opposing positions and cannot agree on one decision or action. Back in the mid of nineties, Multi-Agent Systems (MAS) gained a significant attention from several researchers. The argumentation techniques have been used to facilitate the interaction between autonomous agents of MAS that are able to make their own decisions based on their mental states (e.g. preferences, intentions, goals etc.) [7].

While negotiating and arguing, one can refer to his past experiences unconsciously. Case-based reasoning (CBR) is based on the idea that similar problems have similar solutions. Thus, its integration in a MAS where agents are in conflict will increase the probability of reaching an agreement [8]. Several researchers proposed to combine these disciplines, namely CBR, argumentation and negotiation. In the literature, several works proposed partial combinations such as [9,10,11,12] where argumentation and negotiation have been combined. Moreover, CBR and argumentation have been combined in [8, 13] while other works gathered negotiation and CBR [14, 15]. Thus, numerous research works were dedicated to partial combinations of these disciplines with object to improve the conflict solving process between different parties. For that reason, we believe that the total combination of the three fields would be more beneficial. However, only few works proposed a total combination of the three domains.

In early ninetees, Sycara proposed the PERSUADER system [16] which is a mediator between a company and its trade union. CBR was used to retrieve past cases representing the arguments used in the past in order to make better negotiation scenarios. Moreover, CBR can help the system to negotiate with an unknown agent based on past experiences with similar agents. But, this proposal is highly domain specific and the negotiation is only ensured by the mediator. Soh et al. [17], proposed another framework where a set of agents collaborate in order to track as many targets as possible. Each agent owns a case-base and a CBR manager which ensures the use of past cases to negotiate in new situations. More recently, in [18] a MAS where agents are able to negotiate through argumentation and use CBR to reach conclusions is presented. The system is for e-commerce domain and used to help users to buy products. CBR was used to reduce system’s complexity and hence, users will get the results of the sites selling their desired product more rapidly. However, these frameworks are very domain specific and cannot be easily adapted to other domains. No generic framework has been proposed in the literature that combines CBR, negotiation and argumentation which leads us to the main purpose of this paper which is providing a generic framework for an argumentation-based negotiation using CBR. This work combines the three fields (i.e. negotiation, argumentation and CBR) in a domain independent framework by proposing a generic architecture that defines the basis of the environment and a state machine protocol that specifies the rules of interaction between two argumentative negotiator agents that interact following a set of dialogue games. This framework is called GANC for Generic Argumentation-based Negotiation using CBR.

This paper is organized as follows: Sect. 2 is dedicated to define our new generic argumentation-based negotiation using CBR framework by highlighting its architecture, its main components and the protocol followed by agents in the negotiation process. Section 3 concerns the conducted experiments and the results and Sect. 4 concerns the conclusion of our work and our future perspectives.

2 A New Framework for Argumentation-Based Negotiation Using CBR

This section details our new generic framework for argumentation-based negotiation using CBR (so called GANC for Generic framework for Argumentation-based Negotiation using CBR). Figure 1 illustrates the GANC framework architecture for two agents (A and B).

Fig. 1.
figure 1

The proposed architecture of the GANC framework

Full size image

2.1 GANC Architecture

The GANC architecture is domain-independent and its main components are as follows:

  • Agents: they are self-motivated entities that can enter and leave a dialogue at any time. These argumentative negotiator agents are not only able to interpret and evaluate incoming locutions from the counter parties, but are also able to evaluate the incoming arguments, update their mental states, generate a set of arguments and propose the appropriate one. Each agent has her own preferences. Based on these preferences, she will accept or reject an offer and generates a proposal. Offers will be proposed in a decreasing order from the best offer to the least favorite one. Indeed, a set of rules that govern the movements (e.g. accept, reject) of an agent are defined. In argumentation theory, each agent has a position that represents its mental state regarding a giving issue. Similarly, an agent has a position regarding a negotiation issue. This position includes her preferences in the form of a set of features, the problem and its offer. Agents follow an argumentation-based negotiation protocol detailed in Sect. 2.2.

  • CBR: each argumentative negotiator agent has two CBR: (i) domain CBR that operates over previous negotiation cases that can be used as arguments in future negotiation situations and (ii) argument CBR that operates over past arguments used by agents. Similar cases are generated by comparing the current situation’s premises and values with cases’ premises in the case-base. This similarity is determined using the normalized Euclidean distance between premises. Proposals and arguments are the main knowledge exchanged between agents. The choice of an argument is so important since it can influence the course of the negotiation process. Later on in this paper, the structure of the arguments, their types and the way agents use them are discussed. In this framework, agents negotiate through the exchange of arguments. CBR is used to select the appropriate argument that can be sent in a given situation and as a warehouse that stores all past negotiation and argumentation cases which make agents able to take advantage of their past experiences.

  • Commitment store: it is a particular agent that does not enter in the negotiation process and holds all the information about the negotiation process such as the counter party proposal, the exchanged arguments and all information that concerns the dialogue between the agents. Therefore, an agent queries the commitment store in order to get information about the dialogue (e.g. the offer sent by the opponent).

  • Locutions: agents have the possibility to send their proposals, accept an offer, refuse an offer by withdrawing the dialogue and to attack, agree or reject an argument. The agreement or the reject of an argument triggers the start of a new round where agents switch roles, the opponent becomes the proponent and vice-versa.

2.2 Argumentation-Based Negotiation (ABN) Protocol Used in GANC

In this section, we discuss the protocol followed by agents during their negotiation process. Several protocols were proposed in negotiation and argumentation communities [19,20,21]. In negotiation, one of the most used protocols is alternating offers protocol [20]. In argumentation, the protocol can be defined in an explicit way (e.g. finite state machine) or in an implicit way in the agent’s specification [21]. In the GANC framework, the protocol is presented explicitly in a finite state machine format because it is explicit and easily accessible. Agents will follow the alternating offers protocol and exchange offers in an alternating way. The possible moves that an agent can do are presented in Fig. 2 that depicts the ABN protocol used in GANC.

Exchanged Locutions. Agents use locutions in order to negotiate and interact between each other. As some examples, we can mention:

  • Propose: an agent will enter to the dialogue only if she has an offer to propose to its opponent. With this move an agent will send her proposal to the commitment store that will be checked by the other agent. An agent generates a proposal based on her preferences.

  • Assert: if an agent receives a “why” locution she has to assert her proposal by supporting it with an argument. After asserting, the agent will wait for the other agent’s response that can either be: attack, accept, reject or agree.

  • Attack: Using this locution, an agent can attack the other agent’s supporting argument if she is not convinced or to counter-attack a received attack.

  • Accept: in our framework an agent accepts a proposal in two cases: (i) if the proposal is the agent’s current preferred value. (ii) If the argument respects the agent’s conditions such as the number of similar premises between agent’s premises characterizing her offer and the premises sent by the opponent in his argument and based on the number of the received distinguished premises that exists in her CBR (these premises were once a reason to choose a given offer). As an example, an agent can accept the other agent’s proposal if their positions are characterized by two common premises with the same value. These conditions differ from agent to another based on their flexibility and how much they are open minded. In case if a counter-example argument is received, the agent will immediately accept the offer since this kind of argument has the highest power of convincing. In GANC framework, based on agents’ acceptance conditions we can classify agents into three types: a tolerant agent, a medium strict agent and a very strict agent.

  • Agree: this means that an agent agrees with the opponent’s argument and believes that her offer is not the best. If the opponent agrees on the argument then a new round will start where he will be the proposing agent.

  • Reject: an agent sends this locution if she has no more arguments to present and she still does not accept the counter party’s offer. After this locution a new round will start.

  • Withdraw: an agent can withdraw the dialogue at any time. The cause of a withdraw can be that an agent does not have any proposals or she does not accept the other agent’s proposal neither the argument supporting that offer.

Followed Rules. The dialogue between agents is governed by a set of standard rules as follows:

  • A rejected offer or argument cannot be proposed a second time in the same dialogue.

  • A new round starts only if one of the agents responds by agree or reject and the other agent accepts that and does not withdraw.

  • An agent is free to quit the dialogue: (i) if she can’t generate any positions and still refuses its opponent’s offer, (ii) if she refuses the offer and refuses to negotiate, (iii) if she receives an invitation to negotiate but she has no offers.

  • At each round, only one offer will be discussed and there will be rounds as long as no agreement is reached and the agents still have offers to propose. At each round one agent plays the role of opponent and the other of proponent and then they switch roles in the next round.

  • The negotiation ends if one of the agents withdraws the dialogue, if an agreement is reached or if agents exposed all their offers and still no agreement is reached.

At the end of a dialogue, there are two possible outcomes: an agreement or not. Agents follow an alternating offers protocol in form of a finite state machine inspired from the one in [22, 23]. We modified it in order to make it suitable for a negotiation context.

Followed Protocol. Figure 2 depicts the proposed protocol in a finite state machine that presents a round in the negotiation where only one issue is discussed. Every time one of the agents responds by agree or reject, a new round will be started and agents will be back to the state Enter but with updated beliefs. It will be rounds as long as no agreement is reached and agents still have offers to propose. For the sake of clarity, the withdraw moves were not presented but an agent can withdraw the dialogue at any step.

Fig. 2.
figure 2

Proposed argumentation-based negotiation protocol used in GANC (dotted lines indicate wait states and solid lines are send states).

Full size image

An agent can enter the dialogue only if she has an offer to propose. Thus, agents start by sending their offers and then two different scenarios will happen according to the agent’s role.

  1. 1.

    The agent is a proponent: after proposing, the agent will move to the central state where she will wait for a response from the opponent. If it is an accept, then the negotiation will end with an agreement on the current offer of the proponent but if it is a challenge then the agent has to assert her offer by a support argument. After asserting, the proposing agent will wait for a reply. If the agent’s support argument was attacked, then the two agents will enter in a series of attacks and counter attacks until the opponent accepts the offer or one of them agrees, rejects or has nothing to say about the argument and thus a new round will be started.

  2. 2.

    The agent is an opponent: after proposing; the agent will query the commitment store to get the counter party’s offer. In this stage, the agent can either accept the offer or challenge it by sending a “why” locution. Same thing, when the opponent receives an assert she can accept the offer, agrees or rejects the argument or attack it. In case of attack, agents will argue until one of them agrees or rejects with the other argument or if the opponent accepts the offer.

2.3 How to Use Arguments in GANC?

An argument is an additional information used by agents to backup their proposals and attacks. It is composed of the agent’s promoted value (i.e. offer) and a support set that can be:

  • Premises: a set of features that the agent used to generate this argument.

  • Negotiation cases: a list of old negotiations similar to the current scenario.

  • Distinguishing premises: premises that the other party did not take into consideration and can affect their preferences.

  • Counter example: arguments that contain same premises as the ones presented by the other party but can give another outcome.

Agents choose their argument’s support set based on the type of argument they desire to send. Two types exist in our framework namely:

  • Support argument: is an argument that supports and explains a proposal. More specifically it is the knowledge used to generate an argument such as previous negotiation and argumentation experiences or agent’s premises that defines her proposal.

  • Attack argument: used to attack an incoming argument. It can contain distinguishing premises or counter examples.

Agents choose the type of argument to send based on the last locution they received. In other words, if an agent is asked to assert her proposal then, she will need an explanatory argument to explain her offer and thus, a support argument will be sent. Otherwise, if the agent’s offer or last argument is attacked then she will send a counter attack to defend her position and the offer she proposes.

The argument state changes according to the opponent’s response. An argument can have the state acceptable if the other agent accepts that argument, it can be in the state rejected if it was rejected or undecided if the opponent said nothing about it and couldn’t neither accept it nor reject it. The structure of an argument will be better explained in an illustrative example.

2.4 Illustrative Example

To illustrate the GANC framework, we propose to instantiate it in a simplified example in the tourism domain. In our example, two agents are negotiating over a holiday destination. Each one, agent 1 and agent 2 has three cases in her case base (see Fig. 3). Agent 1 has two preferences, Maldives and Singapore whilst agent 2 prefers Bali and Kuala Lampur. The negotiation starts when agent 1 proposes Maldives as a destination to agent 2. Since Maldives is not the current preferred offer to agent 2 she has to ask “why” in order to get explanations and arguments. Thus, agent 1 explains her choice by sending an “assert” locution explaining that Maldives is characterized by its hot weather and the availability of three stars hotels with all inclusive pension. However, according to agent 2’s case base, the Maldives has hotels with only housing pension. Therefore, she sends an attack containing her argument to agent 1. Hence, agent 1 send a counter example mentioning that according to her experiences, there are hotels with all inclusive pension. Since the counter example is the most convincing argument in our framework and since the only drawback to agent 2 is the pension of the hotel, she accepts the Maldives as a destination. At the end of this negotiation, agent 2 will add a new case to her case-base. The new case is (Maldives; Pension: All inclusive, Nb stars: 3, Weather: hot, Month: august), that contains “Maldives” as a conclusion and four premises. The new case will be used as an argument in future negotiation scenarios.

Fig. 3.
figure 3

Bilateral negotiation over travel destination

Full size image

3 Experimental Study

3.1 Experimental Protocol

In what follows, we explain the experimental protocol by defining the environment of implementation, the data and the experiments that we conducted.

Experiments Environment and Data. All the framework is implemented on the platform Magentix2 [23] using eclipse Luna. Magentix2 is a multi-agent platform that presents argumentative agents that have their own strategies and tactics and interact following a state machine protocol. We modified these agents as well as their strategies and the followed protocol to make their behavior suitable for a negotiation context. Thus, we propose new negotiator argumentative agents based on Magentix2 argumentative agents. For instance, we tested the GANC framework with two agents. In order to implement the framework, we used the Java language. The old argumentation and negotiation experiences (i.e. case bases) are stored in files acceded by the two CBRs.

In order to test the GANC framework, experiments were conducted in the tourism domain where two agents negotiate over a destination. To the best of our knowledge there is no database containing real arguments or real negotiation offers available. Due to this lack of data, we constructed our own database from real data provided by the tourism ministry of Tunisia and collected from many websites such as TrivagoFootnote 1, HolidayWeatherFootnote 2, BandsintownFootnote 3 and eDreamsFootnote 4.

Our database concerns all information that can influence one’s choice of a destination. Therefore, data contains information about available hotels and everything that concerns the accommodation (e.g. rooms’ prices per night). It also contains the price of means of transport whether it is a bus for destinations in Tunisia or plane for international destinations. Other important features that characterize countries in the world such as their safety rank, their health and hygiene rank and in general their global rank are taken into consideration. These ranks are important in the choice of a holiday destination and were collected from The Travel and Tourism Competitiveness Report 2017 published by the World Economic Forum. We also collected information about concerts and festivals planned in a given holiday period in the destination country and information about its general weather. Moreover, data was collected based on few assumptions. We assume that agents negotiate over a holiday in high season time (i.e. June, July, August) and that the plane tickets are for 10 days duration from the \(1^{st}\) to the \(10^{th}\) of each month. Hotels availability and prices are collected for one night in the first weekend of each month for one person.

The final database contains 505 lines about 126 destinations that are characterized by 29 features cited before (e.g. safety rank, plane ticket’s price and the weather). The database is available on lineFootnote 5.

Protocol. Tests are carried on negotiation scenarios that last 3 rounds. At each round an agent plays the role of an opponent and the other of a proponent and at the end of the round they switch roles to negotiate over the next offer.

In order to highlight the importance of CBR as well as the importance of the exchanged arguments we conducted 120 different experiences in 4 different possible scenarios. Firstly, we supposed that agents are tolerant and thus, they accept an offer if one of the premises characterizing this offer is one of the agent’s preferred premises. Let us illustrate this in an example, if we suppose that an agent proposes Djerba for three reasons: hot weather, cheap and holiday period in June and the opponent agent’s premises that characterize her choice are hot weather, a given set of means of transport and a set of restaurants then she will accept Djerba as a destination. In the case of tolerant agents, we made 40 runs. First ten runs are done using 10 cases available in the case-base of agents’ CBR. Second ten runs are done using 50 cases, the third ten runs are done using case-base with 100 cases and the last ten runs are done using case-base with 500 cases.

Same experiments are conducted using medium strict agents that accept an offer only if there are more than 2 similar premises. Same for highly strict agents that only accept an offer if it is characterized by all agent’s preferred premises (i.e. all three premises of each agent are the same).

3.2 Experimental Results

The importance of CBR was highlighted by Conducting these experiments. The first impact was on time that decreases from period nearby 18 s to 10 s. Agents negotiate through the exchange of arguments which make the existence of arguments primary. Therefore in Fig. 4 we can see that in case agents have zero cases in their case base then no agreement is reached. Thus, agents must have arguments at the beginning of a negotiation. The second impact that was highlighted on Fig. 4 is the number of agreements. Agreement is the goal of each agent starting a negotiation and thus, it makes it an important factor to evaluate a negotiation. In the case where agents have only 10 cases in their case-bases, only 10 agreements were reached from 30 negotiation scenarios in each type of agents. The bigger the number of cases is, the higher the probability of reaching an agreement. Negotiation seems to be more successful when the number of cases is more than 100 (see Fig. 4). Thus, negotiation is easier and more beneficial when agents are more experienced.

Fig. 4.
figure 4

Number of agreements

Full size image

Another important feature that influenced the negotiation is the agent type (i.e. tolerant, strict and very strict). In fact, the negotiation process is longer when agents are very strict due to the difficulty of convincing such agent and consequently, the number of agreement decreases.

4 Conclusion

This paper proposes a generic domain-independent framework for argumentation-based negotiation using CBR. GANC is generic thanks to its domain-independent architecture, the structure of the arguments (i.e. attributes- values) and the fact that all domain-dependent information can be instantiated in the domain CBR only by instantiating a set of premises, their values and the outcome. We claim that argumentation presents additional information exchanged by agents that facilitate the negotiation between them and helps to find a settlement. The CBR gives agents the possibility to take advantage of their past experiences and thus, better decisions can be made. Experiments proved that this combination of the three fields (i.e. argumentation, negotiation and CBR) is beneficial and makes the automated negotiation better in terms of time and the reached agreements. Moreover, a benchmark was constructed. It contains information about several travel destinations.

Even though in this paper we focus on bilateral negotiation, we believe, that this work can be the basis for many future works. We plan to extend the GANC framework to support multilateral and multi-issues negotiations. We also plan to take into consideration the uncertainty in such environments and to add the possibility of learning opponent’s tactics and the way they reason as well as the moves that they usually apt to in similar situations using CBR.