Argument-based Multi-Issue Negotiation

1 Introduction

Automated negotiation offers a promising solution for addressing real-life conflicts with improved efficiency (e.g., [Luo et al., 2024]). The goal of a negotiation dialogue is to enable interacting agents to resolve conflicts and arrive at a mutually acceptable agreement. These conflicts revolve around the object of negotiation (e.g., a product such as a car), which may be defined by a single issue, such as price (singleissue negotiations), or by multiple issues, such as price, color, brand, etc. (multi-issue negotiations).

Over the past twenty-five years, computational argumentation has been widely applied to model negotiation dialogues, particularly in the context of single-issue negotiations (see, e.g., [Rahwan et al., 2003; Dimopoulos and Moraitis, 2014] for a survey).

In argumentation-based negotiation (ABN), agents choose offers likely to be accepted and exchange arguments supporting them, based on their theories (e.g., [Amgoud et al., 2007; Amgoud and Kaci, 2006; Kakas and Moraitis, 2006; Dung et al., 2008; Parsons et al., 1998; Hadidi et al., 2010;

Casali et al., 2016]), on their opponent's profile (e.g., [Hadidi et al., 2012; Pilotti et al. et al., 2012]), or both as in [Dimopoulos et al., 2019; Dimopoulos et al., 2021], where an agent first uses its theory to choose the best offer and then uses its incomplete theory about its opponent to find supporting arguments.

Opponent modeling is crucial for negotiation (see e.g. [Baarslag et al., 2016b]) as it enhances the capacity to achieve win-win agreements, especially in cooperative settings.

Learning an opponent's profile involves understanding its acceptance and bidding strategies, deadlines, and preferences. Most proposed works use learning techniques (e.g. [Baarslag et al., 2016a]) better suited for game-theoretic (or utility-based) negotiations. Several methods exist for learning the opponent's preference profile, categorized as Bayesian filters (e.g. [Buffett and Spencer, 2005; Buffett and Spencer, 2007]), perceptron models (e.g. [Zafari and NassiriMofakham, 2016; Pocola, 2022]), and frequency models (e.g. [van Galen Last, 2012; van Krimpen et al., 2013; Tunali et al., 2017; Hosokawa and Fujita, 2020; Pocola, 2022]).

In argumentation-based negotiations two recent works [Dimopoulos et al., 2019; Dimopoulos et al., 2021] propose a different approach to represent the uncertain knowledge an agent has on its opponent by using the Control Argumentation Frameworks (CAFs) from [Dimopoulos et al., 2018].

Utility-based negotiation approaches [Zhan et al., 2024] are well-suited for multi-issue negotiations as they allow for trade-offs, increasing the ability to reach an agreement because the importance of the issues is generally not the same between the negotiating agents. However, they lack information exchange, leading agents to refuse offers they could have accepted if they had information justifying them.

Argumentation-based negotiation (ABN) approaches [Rahwan et al., 2003; Dimopoulos and Moraitis, 2014] overcome the drawback of not allowing agents to justify offers by enabling them to exchange arguments and counterarguments, potentially convincing opponents to accept offers. However, finding a trade-off between multiple issues in multi-issue negotiations is challenging. This is because arguments supporting different issues may express compelling reasons for proposed values, making it difficult to find the best compromise using only qualitative information. Consequently, there is currently no argumentative approach for multi-issue negotiations based solely on arguments for the choice of offers (i.e. the choice of the values of an issue).

This work advances automated negotiation by combining the advantages of previous approaches. It uses a utilitybased part based on frequency models to learn the opponent's profile regarding issues weights and values utilities, seeking trade-offs to increase compromises and win-win situations. This part considers both the proponent and opponent's profiles. It also offers an argumentation part based on [Dimopoulos et al., 2019; Dimopoulos et al., 2021] to represent the opponent's uncertain profile in relation to the practical arguments supporting the values of the issues and the epistemic arguments encoding its beliefs. It also follows this work by choosing the arguments supporting the offer calculated by the utility-based part in the opponent's theory, which has been proven to increase the number of agreements.

However, this argumentation part is used differently from the way it is used in those works and more generally in the other traditional approaches. Indeed, as mentioned above, in traditional approaches, arguments are used by the agents to choose the offers by using their own theories, those of the opponents or both, but also to defend the arguments which support these offers against the arguments which attack them. In our approach, the choice of offers (i.e. the values of the different issues to be negotiated) is handled by the utility-based part. Arguments serve to guarantee that the chosen offers are consistent with the beliefs of the agents, which may encode different profiles, ethical behaviors, social or legal norms, etc., while serving to support the offers and to convince the opponent (as in traditional approaches) in case an inconsistency is detected. This is done by ensuring that the supporting arguments whose role in our approach is to justify the values of the issues (and not to choose them), are acceptable arguments in the theories of negotiating agents.

2 FrequencyModels for Multi-Issue Negotiations

Among the different approaches mentioned above concerning opponent learning, we decided in this work to use a frequency model. Indeed, as we work on negotiations which are not executed several times, using the perceptron models (requiring training examples) is not suitable. Frequency and Bayesian models are two commonly used methods, but we decided to go with a frequency method. However, our approach is modular and someone else could integrate and use a Bayesian model.

Frequency models [van Galen Last, 2012; van Krimpen et al., 2013; Tunali et al., 2017; Hosokawa and Fujita, 2020; Pocola, 2022] allow the agent to learn both the weight of the issues and the utility of the values based on the frequency of their opponent's bids. It relies on the hypothesis that an agent will make its best bids in the beginning of the negotiation and will make concessions over its least preferred issues first. The idea is that an agent will change first the value of the less preferred issue [van Krimpen et al., 2013]. So, the weight of the issues that have the same value from one offer to the next will be increased by a coefficient ϵ, while the weight of the issues for which the value changes will be decreased, such that the sum of the weights of the issues is still equal to 1.

Following the same principle, if an agent picks the same value for an issue many times, this value has a high utility. This utility is computed using a function based on the frequency with which the value has been proposed by the opponent. A widely adopted function for computing the utility of values, as outlined in [Tunali et al., 2017], is defined as follows:

where O1→t represents the set of offers made by the opponent up to time t and δi(j, o) equals 1 if value j appears in offer o, and 0 otherwise. γ is an exponential filter applied to moderate the growth of unbalanced values when the opponent repeatedly sends the same offer.

3 Background on Abstract Argumentation

We briefly recall basics of abstract argumentation [Dung, 1995]. A (finite) abstract Argumentation Framework (AF) is a directed graph ⟨A, R⟩ with A the set of arguments and R ⊆ A × A the attack relation. Standard reasoning with AFs is based on extensions, i.e. sets of collectively acceptable arguments. Here, we focus on stable extensions, i.e. sets of arguments S ⊆ A s.t. ∀a, b ∈ S, (a, b) ̸∈ R, and ∀b ∈ A\S, ∃a ∈ S s.t. (a, b) ∈ R. We write st(⟨A,R⟩) for the set of stable extensions of the AF ⟨A, R⟩. Our approach could be adapted for other semantics in the literature; see e.g. [Dung, 1995; Baroni et al., 2011] for more details on these semantics.

Our approach relies on Control Argumentation Frameworks (CAFs) [Dimopoulos et al., 2018], which generalize AFs by integrating several kinds of uncertainties in the framework (about the existence of an argument, the existence of an attack, or the direction of an attack), and by adding a set of control arguments and attacks allowing an agent to influence the acceptability of some target arguments, whatever the actual state of the uncertain parts of the framework. More details are provided in the supplementary material. 1

4 Negotiation Framework

4.1 Negotiating Agent

We study bilateral agent negotiation over objects characterized by several issues. We formally define the constructs of this negotiation.

Definition 1 (Negotiation object). A negotiation object x is a finite set I(x) of issues (or attributes) characterizing x. Each issue i(x) ∈ I(x) takes values in a finite domain Vi(x) = {vi1 , . . . , vim}.

Notice that for two issues i(x) ̸= j(x) the value of mmay differ. If there is no risk of ambiguity about the negotiation object, we simply write i and Vi instead of i(x) and Vi(x).

1 The supplementary material is available here: https://hal. science/hal-05064307.

Example 1. We consider a negotiation between a car seller and a buyer, with the issues I(car) = {col , pr, del}, corresponding respectively to the color, the price and the delivery date of the car. The values domains of the issues are Vcol = {blue, red, green}, Vpr = {11000, 10500, 10000} (in $), and Vdel = {1, . . . , 5} (in months).

In [Amgoud et al., 2008], Aag = Aag p ∪Aag e is the set of arguments used in the negotiation by agent ag, where Aag p is the set of practical arguments that support the offers (modeling practical reasoning for making decisions) and Aag e is the set of epistemic arguments that represent the agent's beliefs (modeling epistemic reasoning about the agents' beliefs regarding the world and other agents). In our context, the arguments in Aag p support the values of the issues. Each value can be supported by several arguments. Formally, Aag p = ⋃i∈I(x) Aag p,i , where Aag p,i is the set of practical arguments associated with the issue i. Each Aag p,i = ⋃mk=1 Aag p,vik , where Aag p,vik is the set of practical arguments supporting the value vik in Vi of the issue i. The sets of arguments supporting two different values are disjoint. Formally, ∀vik ̸= vi l , Aag p,vik ⋂ Aag p,vi l = ∅.

We assume that agents have preferences over the possible values of the issues.

Definition 2 (Preferences on an issue's value domain). Let a negotiation object x, i an issue and Vi its value domain. We define a weak (preference) order [Fishburn, 1968] for an agent ag, ⪰iag on Vi s.t :

Each value is also associated with a utility.

Definition 3 (Utility of a value). Given i an issue, Vi its domain and ⪰iag the weak order on Vi. The utility function uag i : Vi → [0, 1] s.t. ∀i ∈ I(x), ∀vik ∈ Vi, uag i (vik ) ∈ [0, 1], i.e. uag i maps the values to their utilities. The utilities must be consistent with the preferences, i.e. uag i (vik ) ≥ uag i (vi l ) iff vik ⪰iag vi l .

For defining the utility of an offer (for an agent), we use (as usually in the literature) a Linear Additive Utility function, as we consider there is no interdependence between the issues.

Definition 4 (Utility of an offer). Let I(x) the set of issues, Wag = {wag i | i ∈ I(x)} the set of weights of the issues, 0 ≤ wag i ≤ 1, ∑i∈I(x) wag i = 1, and uag i the values' utility function. Then the utility of the offer o is defined as:

Details on how to adapt to our multi-issue setting the definition of the agents argumentation theories originally proposed by [Dimopoulos et al., 2021] for single-issue negotiation are provided in the supplementary material.

We now define the theories and profiles of the agents. Consider two agents α and β negotiating over the object x with the issues I(x). Their value domains Vi (with i ∈ I(x)) are the same for both agents, but each agent may assign different weights to the issues, different utilities to the values of the issues, may have different practical arguments supporting the values and different epistemic arguments. Each agent has an initial profile composed of its own issues' weights, the preferences and utilities for each value of each issue and its personal theory on the one hand; and its beliefs about the opponent's profile (i.e. weights, preferences and utilities) before the beginning of the negotiation and about its argumentation theory on the other hand. Formally, the profile Prα of an agent α is:

Definition 5 (Agents' profiles). Let α, β be two agents.

The profile of α is Prα := ⟨I(x), V, uα,Wα, u?β , W ? β , T α,CAF α,β ⟩, where I(x), V = {Vi | i ∈ I(x)} are the issues and their domains, uα,Wα are the personal utilities and weights of α, u?β ,W ? β are the utilities and weights that α believes β has, T α is α's argumentation theory, CAF α,β is the argumentation theory α believes β has.

By symmetry, the profile of β is Prβ := ⟨I(x), V, uβ , Wβ , u?α, W ?α, T β , CAF β,α⟩.

4.2 Opponent Profile Modeling

In order to model the opponent's profile, we use two methods. First, we learn the opponent's weights and utilities, using a frequency model [van Krimpen et al., 2013; Tunali et al., 2017]. We define a function updateProfile computing the new profile of the opponent. This function increases the weight of the issues for which the value remained the same from one offer to the next by a coefficient ϵ [van Krimpen et al., 2013]. To update the utilities of the values, we use formula 1 (Section 2) [Tunali et al., 2017]. The updated profile is used to choose the next offer to send to the opponent. Then, we learn the opponent argumentation theory by using the Control Argumentation Frameworks (CAFs) [Dimopoulos et al., 2018] like in [Dimopoulos et al., 2019; Dimopoulos et al., 2021]. Actually, the CAF is updated when agents exchange practical arguments supporting their offers along with epistemic and control arguments defending them.

4.3 Utility Concessions

The agent uses a utility concession profile [Baarslag et al., 2015] which follows a time dependent formula to compute the utility Utarget of the offers it can propose or accept at time t. Here, the time corresponds to the steps in the negotiation (i.e. the number of offers sent by the agent). For keeping the time t in [0, 1], we set t = step ÷maximumSteps. The formula is the following :

with Umin and e parameters depending on the chosen profile.

4.4 Utility-based Values Selection

In this section we explain how agent α selects for each issue the value it will send to agent β at a step t.

An offer is represented as o = ⟨σ, S,R⟩, where σ = {⟨i, vik , θi ⟩ | i ∈ I(x)} is a set where each issue in the negotiation is assigned a value along with a practical argument supporting that value, S is an extension that contains all the arguments θi appearing in σ and R is the set of attacks defending the arguments in S.

At the beginning of the negotiation, we compute the set Ωα containing all the possible sets of pairs ω = {⟨i, vik ⟩ | i ∈

I(x)}, with vik ∈ Vi s.t. each issue is assigned exactly one value from its domain. At each step t, we compute the set ΩU α target ⊆ Ωα such that ∀ωl ∈ ΩU α target , U α(ωl) (calculated with the formula from definition 4, see [Coehoorn and Jennings, 2004]) equals the utility target U α target (t) (see formula 2, and [Hosokawa and Fujita, 2020]). More formally:

As in [Coehoorn and Jennings, 2004], agent α wants to choose the offer it thinks is best for agent β. In order to do so, agent α computes the utility U α,β (ωl) of each ωl ∈ ΩU α target (see definition 4), based on agent α's current beliefs over agent β weights and utilities. This is done with the function compute omega set (U α target (t), Ωα) which returns the set ω ∈ ΩU α target that has the best utility for β (according to α's beliefs), i.e. ω = argmaxΩUα target U α,β . When t > 1, before computing the new U α target , the function returns the sets ωl ∈ Ωα that were previously returned (i.e. have a higher utility than the new utility target) but the arguments supporting the offers were not acceptable in the current state of the agents' argumentation theories (see Section 4.5). However, through the exchange of arguments during the negotiation process (see Sections 4.6, 4.7 and 4.8), these previously not acceptable arguments may now be considered acceptable, enabling an offer to be sent when it was previously not feasible. This ensures that an offer, which could lead to an agreement from a utilitarian perspective, is disregarded only if all its supporting arguments remain not acceptable throughout the entire negotiation process.

4.5 Practical Arguments Selection

In this section we discuss Algorithm 1, which describes how α selects the practical arguments θi that support the values in ω and allow to complete the pairs ⟨i, vik ⟩ into triplets ⟨i, vik , θi ⟩ in σ. The key idea behind this algorithm is as follows: an agent begins by checking its own theory to see if an offer, selected based on utility, is supported by an acceptable argument. Next, it examines the uncertain argumentation theory it holds about its opponent to identify whether the offer is supported by an acceptable argument or if it can introduce into the negotiation control arguments to make the supporting argument acceptable when it initially is not. More particularly, first, agent α needs to check if there is a set of arguments Φ = {ϕi1 , ..., ϕin }, that is credulously accepted in its theory T α. In other words, it needs to check if the set ω that represents a utilitarian point of view is in adequacy with its beliefs that can represent ethical, social or legal points of view. This combination of views is necessary when negotiations concern not only economical transactions but also resolution of political or geostrategic conflicts. Since there can be several arguments supporting each value, we use a function comp phi(ω, testedPhi) (line 1) that returns each time a different combination of arguments ϕi ∈ Aαp,vik , such that there is exactly one argument ϕi supporting each value vik in ω. When such a set Φ is computed by comp phi(ω, testedPhi), it is stored in the set testedPhi in order to prevent this function from recalculating it (lines 2 and 30). Then we call a function credulously accepted(Φ, T α) (line 4) that returns a Boolean true if all practical arguments ϕi ∈ Φ are together in at least one extension, and false otherwise. We compute new combinations of arguments Φ using comp phi(ω, testedPhi) (line 29) until we find a set Φ that is credulously accepted in T α or until all the combinations have been tested unsuccessfully (i.e. comp phi(ω, testedPhi) returns ∅)). If there is a set Φ credulously accepted in T α, it means that ω is in adequacy with agent α's beliefs.

In order to convince agent β that the set ω is the best one, and since agents do not necessarily have the same arguments in their personal theories, agent α needs to find in CAF α,β a set of practical arguments Θ = {θi1 , ..., θin } supporting the values in ω, which are credulously accepted in CAF α,β . CAF α,β represents agent α's current knowledge of agent β's beliefs. Similarly as in T α, there can be several practical arguments in CAF α,β that support the same value. The function comp theta(ω, testedTheta) (line 5) returns each time a new combination of arguments in the set Θ, such that θi ∈ Aα,β p,vik and there is exactly one argument θi supporting each value vik in ω. As with the sets Φ, each time a set Θ is computed it is stored in testedTheta (lines 6, 13, 17 and 26) so that we prevent its recalculation. Then, we check if Θ is credulously accepted in Aα,β F ∪ Aα,β U . The function credulously accepted(Θ,Aα,β F ∪Aα,β U ) (line 8) returns true if there is at least one extension in each completion (see the supplementary material for more information on completions) that contains all arguments θi ∈ Θ, false otherwise. We compute a new set Θ (line 12) until we find one that is credulously accepted in Aα,β F ∪ Aα,β U or until all the combinations have been tested unsuccessfully (i.e. comp theta(ω, testedTheta) returns ∅). If such a set Θ is found, Algorithm 1 returns the offer ⟨σ,∅,∅⟩, where σ = {⟨i, vik , θi ⟩ | i ∈ I(x)}, with ⟨i, vik ⟩ ∈ ω, and θi ∈ Θ. The function comp sigma (ω,Θ) (lines 9 and 22) computes the set σ based on the set ω of couples ⟨i, vik ⟩ and the set Θ. If no combination Θ is credulously accepted in Aα,β F ∪ Aα,β U , we search for a configuration of CAF α,β , using control arguments, where a set Θ is credulously accepted. This means there is at least one extension in each completion that includes all arguments in Θ, achieved using the function comp contr conf (ω,Θ,CAF α,β ) (line 19). This function returns an extension S such that Θ ⊆ S (if it exists), and ∅ otherwise. We continue computing a new set Θ (line 25) until the function comp contr conf (ω, Θ, CAF α,β ) returns an extension S or no new sets remain. If comp contr conf (ω,Θ,CAF α,β ) returns an extension S, we compute the set of attacks R (line 21) that defends the arguments in S. Then, Algorithm 1 returns the offer ⟨σ, S, R⟩.

If no set Φ is credulously accepted in T α, it means the set ω is not in adequacy with agent α's beliefs and Algorithm 1 returns ⟨∅,∅,∅⟩. Similarly, if there is no set Θ credulously accepted in Aα,β F ∪Aα,β U or CAF α,β , then the set ω is not in adequacy with agent α's knowledge of agent β's beliefs and Algorithm 1 returns ⟨∅, ∅, ∅⟩.

Algorithm1 choose practical arguments(ω,T α,CAF α,β )

1: Φ← comp phi(ω, testedPhi) 2: testedPhi ← {Φ} 3: while Φ ̸= ∅ do 4: if credulously accepted(Φ, T α) = true then 5: Θ← comp theta(ω, testedTheta) 6: testedT heta ← {Θ} 7: while Θ ̸= ∅ do 8: if credulously accepted(Θ,Aα,β F ∪ Aα,β U ) = true then 9: σ ← comp sigma(ω, Θ) 10: return ⟨σ,∅,∅⟩ 11: end if 12: Θ ← comp theta(ω, testedTheta) 13: testedT heta ← testedT heta ∪ {Θ} 14: end while 15: testedT heta ← ∅ 16: Θ← comp theta(ω, testedTheta) 17: testedT heta ← {Θ} 18: while Θ ̸= ∅ do 19: S ← comp contr conf (Θ, CAF α,β ) 20: if S ̸= ∅ then 21: R ← {(a, b)|a ∈ S, b ∈ Aα,β F ∪Aα,β U } 22: σ ← comp sigma(ω, Θ) 23: return ⟨σ, S,R⟩ 24: end if 25: Θ ← comp theta(ω, testedTheta) 26: testedT heta ← testedT heta ∪ {Θ} 27: end while 28: end if 29: Φ← comp phi(ω, testedPhi) 30: testedP hi ← testedP hi ∪ {Φ} 31: end while 32: return ⟨∅,∅,∅⟩

4.6 The Biding Strategy

In this section we discuss Algorithm 2, describing agent α's biding strategy. The key idea behind it is as follows: an agent seeks to learn its opponent's profile to propose a utility-based offer that is likely to be accepted. It then applies Algorithm 1 to identify acceptable arguments supporting this offer, iterating the process as long as it can find offers with utility greater than its reservation value, when previously selected offers cannot be supported by acceptable arguments in the theories of both agents. More particularly, first, agent α updates its opponent's profile by using the frequency models from Section 2 (line 1). Then it computes the target utility U α target (t) at step t. Once this is done, it calls the function compute omega set(U α target (t),Ωα) (formula 3) to choose the best set ω at this step. While no offer has been chosen, o(α, β) = ⟨∅,∅,∅⟩ and compute omega set(U α target (t),Ωα) does not return ∅, it calls Algorithm 1 (line 8) which returns an offer o(α, β) = ⟨σ, S, R⟩ if there is a set of practical arguments supporting the values in ω credulously accepted in T α and a set of practical arguments supporting the values in ω credulously accepted in CAF α,β . Otherwise, it returns ⟨∅,∅,∅⟩. In this case (line 9), we remove ω from Ωα (line 10) and choose a new ω for this step t (line 11). If Algorithm 1 returns ⟨∅,∅,∅⟩ for all the sets ω at step t, we compute U α target for the next step t (line 15). If U α target > reservationValue, we stay in the loop. Once we leave the loop, if o(α, β) = ⟨∅,∅,∅⟩, then the agent does not have any new offers to send to its opponent. If the opponent's last message was no offer it means the opponent does not have new offers either, and agent α quits the negotiation (line 20). Otherwise, the agent sends no offer (line 18); if an offer is set, it is sent to agent β.

Algorithm 2 makeBid(reservationValue, profile α,β , Ωα, step, message(β, α), T α, CAF α,β )

1: call updateProfile(profile α,β ) 2: t ← step 3: compute U α target (t) 4: o(α, β) ← ⟨∅,∅,∅⟩ 5: while o(α, β) = ⟨∅,∅,∅⟩ and U α target (t) ≥ reservationValue do 6: ω ← compute omega set(U α target (t), Ωα) 7: while o(α, β) = ⟨∅,∅,∅⟩ and ω ̸= ∅ do 8: o(α, β) ← chose pract arg(ω, T α,CAF α,β ) 9: if o(α, β) = ⟨∅, ∅, ∅⟩ then 10: Ωα ← Ωα \ {ω} 11: ω ← compute omega set(U α target (t), Ωα) 12: end if 13: end while 14: t ← t + 1 15: compute U α target (t) 16: end while 17: if o(α, β) = ⟨∅,∅,∅⟩ and message(β, α) ̸= no offer then 18: message(α, β) ← no offer 19: else if o(α, β) = ⟨∅,∅,∅⟩ then 20: message(α, β) ← quit 21: else 22: message(α, β) ← propose(o(α, β),∅,∅) 23: end if 24: send(message(α, β))

4.7 The Acceptance Strategy

In this section we describe the acceptance strategy of the agents. The key idea behind this algorithm is as follows: the agent evaluates whether it can accept the proposed offer after updating its argumentation theory with the information provided alongside the offer. If it cannot, it communicates the reasons for its inability to accept. More particularly, when agent α receives an offer o(β, α) if the extension S is not null it updates its own theory T α and CAF α,β by integrating the arguments in S and the attacks in R to them (lines 3-6).

For updating the theories T α and CAF α,β we use the operator ⊕ defined in [Dimopoulos et al., 2019; Dimopoulos et al., 2021] as follows: given three sets A1, A2, A3, (A1, A2)⊕ A3 is the pair (A′1 ,A′2 ) such that A′1 = A1 \ (A1 ∩A3) and A′2 = A2 ∪(A1 ∩A3). This operator is used in Algorithms 3.

Then, agent α accepts an offer (line 17) if the offer's utility U α(o(β, α)) is above its current U α target (t), and the supporting arguments in the offer are credulously accepted in T α.

If U α(o(β, α) < U α target agent α sends a reject message (line 9). If U α(o(β, α) > U α target , agent α calls a function get pract arg(σ) that extracts the set Φ of practical arguments supporting the values of the offer in its theory T α. Then, it checks if Φ is credulously accepted in T α. If it is not the case, agent α computes the set of arguments Q, and the set of attacks Reasons explaining this rejection and sends the rejection message (lines 12-15). If it rejects the offer, it makes a counteroffer by calling Algorithm 2.

Algorithm 3 accept offer(U α target (t),o(β, α)),T α,CAF α,β )

1: ⟨σ, S,R⟩ = o(β, α) 2: if S ̸= ∅ then 3: T α = ⟨Aα ∪S,→α ∪R⟩ 4: (Aα,β U ,Aα,β F ) = (Aα,β U ,Aα,β F ) ⊕S 5: (--⇢α,β,→α,β) = (--⇢α,β,→α,β) ⊕R 6: (⇄α,β,→α,β) = (⇄α,β,→α,β) ⊕R 7: end if 8: if U α(o(β, α)) < U α target (t) then 9: message(α, β) ← reject(o(β, α),∅,∅) 10: else 11: Φ← get pract arg(σ) 12: if not credulously accepted(Φ, T α) then 13: Compute Q ⊆ ξ where ξ is an extension and Q is the set of arguments from which each ϕj ∈ Φ are reachable 14: Reasons←{(r, ϕj)|(r, ϕj) ∈→α, r ∈ Q, ϕj ∈ Φ} 15: message(α, β) ← reject(o(β, α),Q,Reasons) 16: else 17: message(α, β) ← accept(o(β, α),∅,∅) 18: end if 19: end if 20: send(message(α, β)) 21: if (message(α, β) ← reject(o(β, α),Q,Reasons) then 22: call makeBid(reservationV alue, profile α,β , Ωα, step, message(β, α), T α, CAF α,β ) 23: end if

4.8 The Negotiation Protocol

This section discusses the overall negotiation protocol (Algorithm 4). This algorithm enables observing how an agent's theory is updated after receiving a reject message. While the negotiation is ongoing, agents α and β exchange messages that can either be an offer, the absence of an offer, the rejection of an offer, the acceptance of an offer or the agent informing its opponent that it quits the negotiation. If the opponent message is a rejection and the set of arguments Q explaining the rejection in the theory is not ∅, the agent updates its theories T α and CAF α,β (lines 10-13). Then the agent waits for its opponent to make a new bid. If the message is an acceptance or if its opponent quits (the opponent no longer wishes to negotiate) the negotiation ends. If the message is an offer, then the agent checks if it can accept the offer by calling Algorithm 3. If agent β did not have an offer, agent α calls Algorithm 2 to find its next offer to send to agent β. Algorithm 4 describes this protocol for agent α. A comprehensive example illustrating the execution of the protocol is provided in the supplementary material.

Algorithm 4 negotiationProtocol(reservationV alue, profile α,β , Ωα, step, message(β, α), T α, CAF α,β )

• 1: if agent goes first then

2: makeBid(reservationV alue, profile α,β , Ωα, step, message(β, α), T α, CAF α,β ) 3: end if 4: negotiation ← true 5: while negotiation do 6: get message(β, α) 7: switchmessage(β, α) do 8: case reject(o(α, β), Q, Reasons): 9: if Q ̸= ∅ then 10: T α = ⟨Aα ∪ Q, →α ∪Reasons⟩ 11: (Aα,β U ,Aα,β F ) = (Aα,β U ,Aα,β F ) ⊕Q 12: (--⇢α,β , →α,β ) = (--⇢α,β , →α,β )⊕Reasons 13: (⇄α,β , →α,β ) = (⇄α,β , →α,β ) ⊕ Reasons 14: end if 15: get message(β, α) 16: case accept(o(α, β), ∅, ∅): 17: negotiation ← false 18: case quit: 19: negotiation ← false 20: case propose(o(β, α), ∅, ∅): 21: accept offer(U α target (t) ,o(β, α), T α, CAF α,β ) 22: case no offer: 23: makeBid(reservationV alue, profile α,β , Ωα, step, message(β, α), T α, CAF α,β ) 24: end switch 25: end while

5 Experimental Results

Our negotiation framework was implemented in Java using the Jade platform (https://jade.tilab.com/). The acceptability of arguments in CAFs was computed with the solver taeydennae [Niskanen et al., 2020b; Niskanen et al., 2020a].

Our experiments include 100 multi-issue negotiations with 2 issues and 100 negotiations with 3 issues, with the number of values for each issue included between min = 3 and max = 5. More details on the benchmark generation are given in the supplementary material.

Our results are summarized in Figure 1. We first compare the percentage of agreements between our argument-based multi-issue negotiation protocol and a multi-issue negotiation protocol without argumentation. The negotiations without argumentation were run on the genius platform [Lin et al., 2014] using the Atlas3 [Mori and Ito, 2017] party (i.e. agent model) for both agents. We selected this agent model because our framework currently employs the same utility target formula. However, since our framework is modular, any utility target formula can be implemented, allowing other agents to be used for negotiations without argumentation. As we can see, our protocol (red bars) has a percentage of agreement of 67% for 2 issues and 64% for three issues, whereas the multi-issue negotiation protocol without argumentation (blue bars) has an overall percentage of agreements of 94% for 2 issues and 100% for 3 issues. However, simply comparing the overall percentage of agreements is insufficient for real world situations. To assess the added value of our protocol, it is also essential to evaluate the percentage of agreements that align with the agents' beliefs (i.e., their argumentation theories) for the negotiation protocol without argumentation. By using arguments to verify that offers acceptable to both agents from a utility perspective also align with their beliefs (which may represent societal, ethical or legal principles, among other principles), our protocol ensures the exclusion of offers that violate these principles and would likely be rejected in reallife situations. In contrast, negotiations conducted using the multi-issue negotiation protocol without argumentation relied solely on the utility of the offers to reach agreements. This explains the difference in the number of agreements (for 2 and 3 issues) between the two negotiation protocols, with the protocol without argumentation being favored when arguments are not taken into account. When considering the arguments for verifying compliance with beliefs, the negotiation protocol without arguments (represented by blue striped bars) shows a significant drop in the percentage of consistent agreements, reaching only 40% for two issues and 29% for three issues. This occurs because the values of the issues in the other agreements (i.e. that are lost) are supported by arguments that are not acceptable in the agents' theories (i.e. they conflict with their beliefs). The difference in the percentages of agreements reached between our protocol and the protocol without argumentation-this time favoring our protocol when considering the arguments supporting the offers-arises from a fundamental distinction. In the latter, if a supporting argument for an offer is not accepted in the agents' theories, the agreement on that offer-reached purely based on utilities-is disregarded, as no argumentation protocol is available to resolve such conflicts. In contrast, our protocol allows for the possibility of exchanging arguments, enabling initially rejected supporting arguments to potentially become accepted in the agents' theories, thus facilitating agreement. Therefore, we show that our approach is better suited for handling multi-issue negotiations in real-world settings.

6 Discussion and FutureWork

In this paper, we presented a novel hybrid approach that combines the advantages of the two main traditional approaches, namely utility-based and argumentation-based approaches, enabling effective adaptation of argumentationbased approaches in multi-issue negotiations. Our hybrid approach leverages traditional (single-issue) argumentation approaches (e.g. [Dimopoulos et al., 2019]), because it uses the most effective techniques (i.e., frequency models) in the literature to seek trade-offs across multiple issues while accounting for both the proponent's and the opponent's profiles. This allows for an increase in the number of agreements, similar to traditional utility-based negotiations. At the same time, our approach offers a significant advantage over traditional utility-based multi-issue negotiations [Zhan et al., 2024]. By incorporating argumentation, it enables an agent to explain the rationale behind each offer and persuade its opponent that the offer not only satisfies utilitarian expectations but also aligns with its profile, ethical principles, legal requirements and societal norms, among other principles. This capability is particularly critical for addressing automated negotiations, not only in business contexts but also in more complex domains such as political or geostrategic negotiations. The way in which the argumentation is used is a major difference with the work proposed in [Xue-jie et al., 2013] which is, to our knowledge, the only one close to our approach in the sense that it uses utilities to represent the preferences of agents and arguments to support the offers. Indeed this work uses argumentation in a traditional way (i.e. only to support offers like the practical arguments of our work). Furthermore, this work uses a simple mechanism to calculate the utilities of offers based exclusively on the information exchanged between the agents (i.e. without possibility of learning the profile of the opponent) and considering that the agents will reveal their utilities when a conflict is detected, which is an unrealistic assumption in many real-world applications. Regarding computational aspects, our work relies on well-known techniques, like checking the credulous acceptability of a set of arguments or the controllability of a CAF, which are respectively NP-complete [Dvor´ak and Dunne, 2017] and ΣP3 -complete [Niskanen et al., 2020a] for the stable semantics.

To conclude, we highlight ideas for future research. A first one consists in studying the impact of using other models for learning the opponents utilities (e.g. Bayesian filters [Buffett and Spencer, 2005; Buffett and Spencer, 2007]). Another interesting track consists in using other forms of controllability [Mailly, 2020; Gaignier et al., 2021], notably in presence of probabilities, that could allow agents to find agreements in situations where no offer is acceptable with respect to all the completions but may be acceptable with respect to the most probable ones, or when negotiation are subject to time constraints. Finally, a promising direction for future work is the creation of an NLP-powered platform that allows users to define agents' utilities, preferences and argumentation theories using natural language.

Acknowledgments

The second author is funded by the French National Research Agency under grants ANR-22-CE23-0005 (AGGREEY) and ANR-22-CPJ1-0061-01 (AIDAL).