Distributed Multi-issue Multi-lateral Negotiation Using a Divide and Rule Approach

Abstract

In this paper, we consider the problem of multi-issue multi-lateral negotiation. We assume that each agent may be interested only in a subset of issues at stake. They nevertheless have to make a collective choice that addresses all issues. We propose a heuristics-based negotiation model where the agents’reasoning mechanisms may be very complex as a result of multiple issues being negotiated. Given this complexity, we propose a distributed negotiation mechanism drawn on divide and rule. The proposed protocol consists of two iterative steps: the partitioning of the agents into groups and the negotiation step where the agents in each group interact without a central controller (no mediator). Our negotiation protocol converges and leads to efficient outcomes, as demonstrated by our empirical results.

1 Introduction

Negotiation complexity significantly grows when self-interested agents must make a choice involving several issues and when each agent may be interested only in a subset of the issues at stake. Previous studies [1, 3,4,5] propose multi-lateral negotiation protocols, but they typically rely on a mediator that facilitates the negotiation by suggesting contracts or by preventing fraud. Those solutions are centralised and suffer from a single point of failure. Additionally, designing a mediator with such skill may be computationally prohibitive. In the alternating affers protocol [2], the agents negotiate without mediator they sequentially take a turn. The first agent submits an offer, the next evaluates it and makes a decision by accepting, counter-offering or walking. However, in a context where agents may have (non) overlapping subsets of issues they are interested in, each agent makes offers which concern its issues of interest and it could happen that the agent who’s turn it is to evaluate an offer may have to evaluate issues it is not interested in. Thus, this may affect the negotiation convergence and the agents’ order turn-taking has a major influence on the negotiation outcome. Our solution aims to overcome these limitations by structuring the process in terms of the multi-agent organisation and agents’ tactics to make offers [6]. In decentralized negotiation settings of the sort we study, agent communication and reasoning may be prohibitively complex. We relax this complexity via careful design of organizational aspects of the multi-agent system, as organisational relationships may have a significant effect on complexity, flexibility and reactivity, and impose computation and communication overheads [7, 8].

We propose a novel negotiation model based on a multi-step approach that fully distributes the negotiation and facilitates the search for agreements. The underlying approach is based on the “divide and rule” approach. It consists of two iterative steps: Firstly, we partition agents into groups based on their overlapping subsets of issues (not the values of the issues) and this is done in a centralized way. We search through this decomposition to gather the agents which share the maximum number of issues. In this way, they can construct partial solutions by focusing on their common issues. Each agent can evaluate an offer from its group’s member. So we explicitly decompose the agents into groups and implicitly the issues, in contrast to existing works which focus only on decomposing the issues into groups [1, 9]. Secondly, after the partitioning, agents in each group negotiate in a fully decentralized way (with no mediator) to find partial solutions over their overlapping issues. The motivation of our approach is to limit the scope of the agents’ interactions and hence to reduce agent reasoning complexity. The agents progressively build a solution by merging their solutions throughout their interactions and form alliances.

2 Negotiation Framework

We focus on self-interested agents that negotiate over multiple issues¹. To illustrate the problem at hand, we consider a scenario where a set of households decide to join a bundled offer to reduce their energy costs. So they must agree upon the energy contract, they will subscribe for. Issues for an energy contract could be energy type, energy provider, contract duration, tariff type, conditions for retracting, and so on. Each of these issues is effectively an attribute of the collective contract. The energy consumers may wish to focus only on a subset of the issues above, depending on their consumption profiles and their needs and preferences.

Let ${\mathcal {A}=\lbrace a_{1},...,a_{n} \rbrace }$ be the set of agents and E the set of issues at stake. Each agent ${a_{i}}$ chooses the attributes it wants to negotiate; we denote these by ${E_{i}}$. Let ${D_{e}^{i}}$ be a subset of values for e which are acceptable for $a_{i}$. Each agent $a_{i}$ assigns a weight ${w_{e}^{i}\in ]0,1]}$ to each attribute ${e \in E_{i}}$ which represents its importance in the negotiation. The value of each attribute’s weight is defined such that ${\sum \limits _{e\in E_{i}}w_{e}^{i}=1}$.

An agent assigns a score to a value of an attribute according to its evaluation criteria. For example, a household may evaluate an energy provider according to its reliability and its service levels. Before the negotiation, $a_{i}$ sets for each attribute $e\in E_{i}$ a range of acceptable score values denoted by ${[ min{V_{e}^{i}}, max{V_{e}^{i}}]}$. So $D_{e}^{i}$ matches to the set of values for e such that the score values belong to this interval. ${ min{V_{e}^{i}}}$, ${max{V_{e}^{i}}}$ are, respectively, the minimal and maximal expected scores agent wants to obtain for e during the negotiation. Thus, ${a_{i}}$ could offer or accept over time every value of attribute e whose the score is between ${[min{V_{e}^{i}}, max{V_{e}^{i}}]}$.

EXAMPLE 1

We consider a set of households which negotiate to decide upon the energy provider (attribute e). Let $\lbrace p_{1}, p_{2}, p_{3},p_{4},p_{5} \rbrace$ be the set of energy providers and (0.9, 0.7, 0.8, 0.3, 0.5) be, respectively, the scores that $a_{i}$ assigns to each energy provider. For example, an agent $a_{i}$ aims to contract with a provider whose the score value is between $min{V_{e}^{i}}=0.5$ and $max{V_{e}^{i}}=0.9$. Its ${D_{e}^{i}=\lbrace p_{1}, p_{2}, p_{3},p_{5} \rbrace }$. Thus, the value that $a_{i}$ offers at each time depends on the score it wants to get for this attribute at this time. The first value $a_{i}$ proposes when the negotiation starts is p1 and the last value (reservation value) $a_{i}$ proposes when the deadline is almost reached is $p_{5}$.

At the beginning of the negotiation process, each agent forms a singleton alliance and defines for each attribute $e\in E_{i}$ a negotiation tactic [6]. A negotiation tactic is a decision function which allows to determine the values of an attribute e to be offered when negotiation progresses. This value can be computed by considering multiple criteria such as time and resource [6]. Here, we focus on a time-dependent tactic. It consists of deciding for each attribute $e\in E_{i}$ an acceptable value in $D_{e}^{i}$ to be offered according to the remaining negotiation time.

3 Negotiation Protocol

Our solution approach draws on hierarchical agglomerative clustering [10] and allows the agents to progressively build an agreement while limiting their reasoning complexity. The proposed protocol is a multi-step process. At each round, it clusters pairs of alliances. Pairing is based on similarity among the alliances over their issues. Specifically, alliances whose subsets of issues of interest overlap are paired in order to allow them to progress the negotiation. Agents in each cluster negotiate in order to build a solution about their common attributes. They form a new alliance when they reach an agreement for each negotiated attribute. The protocol builds incrementally, over multiple steps, the grand alliance (including all or the majority of the agents) that supports a proposal that addresses all issues, i.e complete proposal (Fig. 1). The negotiation terminates with an agreement or a disagreement over the set of issues at stake. In summary, the proposed protocol involves two key steps that are executed iteratively: clustering phase and negotiation phase.

Fig. 1.

6 agents ${a_{1}}$ to ${a_{6}}$ negotiate over the issues ${e_{1}}$ to ${e_{5}}$. ${s_{1}}$ to ${s_{5}}$ are the different rounds.

3.1 Clustering Phase

This phase consists of clustering pairs of alliances. The partitioning is done by the system based on the subsets of issues from the agents. We define similarity functions over overlapping issues which are used to identify candidates for clustering. Each alliance is characterised by the number of agents and the number of attributes it holds. We present two similarity functions named ${Sim_{L}}$ and ${Sim_{L_{+}}}$.

• ${Sim_{L}}$ is based on a simple Jaccard index, named ${Sim_{L}}$. Let ${L_{x},L_{y}}$ be two alliances, ${E_{L_{x}},E_{L_{y}}}$ represent, respectively, their sets of attributes they hold. The similarity function between alliances is defined as follows:

  ${ Sim_{L}= J(E_{L_{x}},E_{L_{y}})=\frac{E_{L_{x}}\cap E_{L_{y}}}{E_{L_{x}}\cup E_{L_{y}}}}.$

• ${{Sim_{L_{+}}}}$ takes into account additional criteria, e.g.., the fact that each alliance aims to get the maximum number of agents via an offer that addresses a maximal number of attributes. We define a gain function gain which gives a real value representing the gain obtained by cluster’s alliances when they merge.

  $${{Sim_{L_{+}}}={Sim_{L}}+gain}\quad {gain(L_{x},L_{y})\,=\,} \dfrac{{\vert E_{L_{x}}\cup E_{L_{y}}\vert }}{{k}}\times \dfrac{{\vert {L_{x}}\cup {L_{y}}\vert }}{{n}}$$

  n, k represent, respectively, the number of agents in the system and the number of all attributes at stake.

Alliances are clustered according to the following rules:

• $R_{1}$: only the alliances that have overlapping attributes are clustered.

• $R_{2}$: when an alliance does not find another with which it forms a cluster, it will not participate in the negotiation at this round. But at the next round, it will be considered to generate new clusters.

These rules facilitate efficient negotiation and help limit the negotiation time.

Fig. 2.

Similarity matrix

EXAMPLE 2

Consider the agents in Fig. 1. Tables in Fig. 2 show, respectively, the set of attributes chosen by each agent (Table 1) and their similarity matrix computed according to $Sim_{L}$ (Table 2) and $Sim_{L+}$ (Table 3). These agents form clusters $g_{1}=\lbrace a_{4},a_{6} \rbrace$, $g_{2}=\lbrace a_{3},a_{5} \rbrace$, $g_{3}=\lbrace a_{1},a_{2} \rbrace$.

3.2 Negotiation Phase

We denote by ${S=\lbrace S_{1},...,S_{Q}\rbrace }$ the set of negotiation rounds. At each ${S_{q}}$, alliances are paired into several clusters in which negotiations take place simultaneously. We denote by ${G_{s_{q}}=\lbrace g_{x} \rbrace }$ the set of clusters at the round ${S_{q}}$. Agents in each cluster $g_{x}$ negotiate to reach a partial agreement over their common issues named ${E_{g_{x}}}$. To make more flexible the negotiation and to facilitate the research of agreements, the proposed protocol allows the agents to have more flexibility about the offers they submit.

Offer Types: An attribute may be negotiated in a cluster holding either all agents or a part of the agents which are interested in this attribute. Thus, for these both cases, we distinguish two offer types. In each cluster, the set of attributes ${E_{g_{x}}}$ is divided into two subsets ${E_{g_{x}}^{f},E_{g_{x}}^{d}}$ which represent, respectively, the attributes for which all of the agents which are interested in this attribute belong to this cluster and the attributes for which a part of these agents belong to this cluster.

• When an attribute is negotiated in a cluster which holds all agents which are interested in this attribute, these latter must find a final solution. This is because this attribute will not be negotiated in future rounds when an agreement is found. We denote by ${\mathcal {O}^{f}}$ a fixed offer which consists of assigning a single value to each attribute in ${E_{g_{x}}^{f}}$.

• When an attribute is negotiated in a cluster which holds a part of the agents which are interested in this attribute, these latter must find a partial solution since this attribute interests other agents outside this cluster. We denote by ${\mathcal {O}^{d}}$ a partial offer which consists of assigning a range of values over the attributes in ${E_{g_{x}}^{d}}$ .

The range of values of attributes supported by different alliances may overlap and this may facilitate agreements among the alliances.

The decomposition of ${E_{g_{x}}}$ into ${E_{g_{x}}^{f}}$ and ${E_{g_{x}}^{d}}$ may be performed by every agent in the cluster since the subset of issues for each agent is a public information. Each agent ${a_{i}}$ knows the set of agents whose subset of issues overlap with theirs. In a cluster, for each attribute in ${E_{g_{x}}}$ an agent may verify if all of the agents with which it shares this attribute are present in the cluster. If so, then there exists no agent outside the cluster which is interested in this attribute. Otherwise, this attribute is susceptible to be negotiated outside the cluster.

Making an Offer: Alliances in a cluster $g_{x}$ exchange offers in a round-robin way. They make offers about the attributes in ${E_{g_{x}}}$. For each attribute e, each alliance must compute either a point value or a range of values to be proposed. For the example in Fig. 1, let $L_{1,2}, L_{3,5}$ be the alliances formed, respectively, by $\lbrace a_{1},a_{2} \rbrace$ and $\lbrace a_{3},a_{5}\rbrace$ during the round $S_{1}$. $E_{L_{1,2}}=\lbrace e_{1},e_{2},e_{3},e_{4}\rbrace$ $E_{L_{3,5}}=\lbrace e_{3},e_{4},e_{5}\rbrace$. $L_{1,2}, L_{3,5}$ are clustered during the round $S_{2}$ and they negotiate over their common attributes $E_{L_{1,2}}\cap E_{L_{3,5}}=\lbrace e_{4},e_{5}\rbrace$. Before the negotiation in the round $S_{2}$ : alliance $\lbrace {a_{1},a_{2}} \rbrace$ has already agreed on a final solution (fixed value) for $e_{1}$ but $\lbrace e_{2},e_{3},e_{4} \rbrace$ have not been negotiated in the previous round. Alliance $\lbrace {a_{3},a_{5}} \rbrace$ has already agreed on partial solutions for $\lbrace e_{3}, e_{5} \rbrace$ and the agents have defined a common negotiation tactic for these attributes. Attribute $e_{4}$ has not been negotiated in the previous round.

• When an alliance holds an attribute not negotiated, this attribute interests only one agent in this alliance. This is because a cluster holds two alliances which become one alliance when they agree on all of their common attributes.

When an alliance submits an offer in a cluster $g_{x}$:

• for each attribute $e\in E_{g_{x}}$ already negotiated, the value or range of values to be offered is computed by using the common negotiation tactic they defined.

• for each attribute $e\in E_{g_{x}}$ not negotiated, the value or range of values is proposed by the agent which holds this attribute. It uses its own negotiation tactic.

Decision-Making: Alliances interact between them by using speech acts: Propose, Accept and Refuse. Each $a_{i}$ uses its utility function $u_{i}$ to evaluate an offer and to make a decision. When an alliance receives an offer, each agent in this alliance evaluates it.

Accepting an Offer: An alliance $L_{k}$ accepts an offer ${O_{L_{r},t}}$ made by an alliance $L_{r}$ at time t, if every agent in $L_{k}$ accepts this offer. An agent accepts an offer if its utility is superior or equal to the utility of its alliance’s offer at time ${t+1}$, ${u_{i}(O_{L_{k},t+1})\le u_{i}(O_{L_{r},t})}$ otherwise the offer is refused.

Merging Alliances: When in a cluster, the pairs of alliances agree on an offer they merge and become a new alliance formed by the agents of this cluster. For each attribute $e\in E_{g_{x}}^{d}$ whose range of values has been negotiated, they define a common negotiation tactic they use in the next round. For each attribute $e\in E_{g_{x}}^{f}$, a final solution has been found and it will not be negotiated in the next round.

4 Negotiation Tactics

In the beginning, each agent tries to reach a maximum score value for each attribute it negotiates. The proposed protocol allows the agents to make concessions. This consists of reducing its maximal expected score values over time in order to facilitate the search of agreements.

A negotiation tactic defined by an agent $a_{i}$ for an attribute e is a function $V_{e}^{i}(t)$ which determines at time t the expected score value $a_{i}$ wants to get at this time.

$${V_{e}^{i}(t)=min{V_{e}^{i}}+(1-} {\alpha _{e}^{i}(t))}{\times [max{V_{e}^{i}}-min{V_{e}^{i}}]}.$$

${\alpha _{e}^{i}(t)}$ is a time-dependent function. [6] describes a range of time-dependent functions which can be defined by varying the strategies to compute ${\alpha _{e}^{i}(t)}$.

${\alpha _{e}^{i}(t)}$ is defined such that:

$$0\le \alpha _{e}^{i}(t)\le 1, \quad \alpha _{e}^{i}(0)=k_{e}^{i},\quad \alpha _{e}^{i}(t_{max}^{i})=1$$

$t_{max}^{i}$ is the deadline at which the reservation value is proposed, $d_{l}$ is the negotiation deadline. ${0\le t \le t_{max}^{i}} \le d_{l}$.

Each $a_{i}$ chooses a constant ${k_{e}^{i} \in [0,1]}$ for each of its attributes. This constant ${k_{e}}^{i}$ determines the first score value the agent wants to get and hence the first value of the attribute e it will propose or accept. ${\alpha _{e}^{i}(t)}$ may be a polynomial or exponential function parameterized by a value ${\beta _{e}^{i} \in \mathcal {R^{+}}}$ which determines the convexity degree of ${V_{e}^{i}}$ curve. Polynomial and exponential functions are significantly different in the way they model concessions according to the value of ${\beta _{e}^{i}}$ [6]. As part of this paper, we work on a range of families of functions with arbitrary values for ${\beta _{e}^{i} \in [0,50]}$. This covers different ways to concede, showing significant differences.

• The case of ${\beta _{e}^{i}<1}$ is denoted the Boulware tactic. It maintains the initially offered value until the time is almost exhausted, where it concedes by proposing the reservation value.

• The case of ${\beta _{e}^{i}>1}$ is denoted Conceder tactic, in which case the agent will offer very quickly its reservation value.

We present below polynomial and exponential functions we consider.

$$ \alpha _{e}^{i}(t)=k_{e}^{i}+(1-k_{e}^{i})(\frac{min(t,t_{max}^{i})}{t_{max}^{i}})^{\frac{1}{\beta _{e}^{i}}}$$

$$ \alpha _{e}^{i}(t)={{\,\mathrm{e}\,}}^{(1-\frac{min(t,t_{max}^{i})}{t_{max}^{i}})^{\beta _{e}^{i}} \ln k_{e}^{i}}$$

In our framework, we propose some methods to compute the ${\beta _{e}^{i}}$ parameter according to the weight of attribute e. Intuitively, a higher weight is associated with lower agent willingness to compromise its initial value; a lower weight indicates the opposite. For each of its issues of interest, an agent holds a negotiation tactic according to the weight it assigns to that issue.

4.1 Methods to Compute $\beta _{e}^{i}$

Let ${\beta _{min},\beta _{max}}$ the domain of $\beta _{e}^{i}$. Here, we set ${\beta _{min}=0,\beta _{max}=50}$.

We present below some ways to compute $\beta _{e}^{i}$ according to the weight of the attribute $w_{e}^{i}$:

• Method A: ${\beta _{e}^{i}= \beta _{min}+(\beta _{max}-\beta _{min})\times (1-w_{e}^{i}), \quad 0 < w_{e}^{i} \le 1}$

• Method B: ${\beta _{e}^{i}= }{\left\{ \begin{array}{lll} {1+(\beta _{max}-1)\times (1-2w_{e}^{i})},&{}{0< w_{e}^{i}\le 0.5} \\ {1+(1-\beta _{min})\times (1-2w_{e}^{i})},&{}{0.5\le w_{e}^{i}\le 1 }\\ \end{array} \right. }$

The difference between strategies A and B is such that in B the range of weight [0, 1] is split into two ranges [0, 0.5], [0.5, 1] and it assigns them, respectively, a family of tactics with ${\beta _{e}^{i}>1}$ and family of tactics with ${\beta _{e}^{i}<1}$. This means that the agent assigns a Boulware tactic [14] to the attributes whose the weight is in [0.5, 1] and a Conceder [15] to the attributes whose the weight is in [0, 0.5].

Fig. 3.

agents $a_{1},a_{2},a_{3},a_{4}$ negotiate over an attribute e. They assign a same weight equal to 0.9 to e but they use different methods and parameters ($k_{e}^{i},k^{i}$) to define their negotiation tactic. This table presents the parameters for each agent.

4.2 Methods to Compute a Range of Values for an Attribute

Making a partial offer consists of proposing for each concerned attribute a range of values to be offered. However, a negotiation tactic produces a single value. Hence, for each attribute e, we define a couple of parameters ${(\beta _{e}^{im},\beta _{e}^{iM})}$ to define a couple of time-depending functions ${\alpha _{e}^{im}(t), \alpha _{e}^{iM}(t)}$ and hence a couple of functions $V_{e}^{im}(t),V_{e}^{iM}(t)$ which allow to compute a range of score values $a_{i}$ wants to get at time t.

$${V_{e}^{im}(t)=min{V_{e}}+(1-} {\alpha _{e}^{im}(t))}{\times [max{V_{e}}-min{V_{e}}]}$$

$${V_{e}^{iM}(t)=min_{v_{e}}+(1-} {\alpha _{e}^{iM}(t))}{\times [max{V_{e}}-min{V_{e}}]}$$

. The values of ${\beta _{e}^{im},\beta _{e}^{iM}}$ for an attribute e are determined according to ${\beta _{e}^{i}}$:

• Method A’: ${\beta _{e}^{im}=\beta _{e}^{i},\quad \beta _{e}^{iM}}{=\beta _{e}^{i}}{+k^{i}(\beta _{max}}{-\beta _{e}^{i}),\quad \beta _{min}}{\le \beta _{e}^{i}}{\le \beta _{max}}$

• Method B’: ${\beta _{e}^{im}=\beta _{e},\quad \beta _{e}^{iM}= }{\left\{ \begin{array}{lll} {\beta _{e}^{i}+k^{i}(1-\beta _{e}^{i}))},&{} {\beta _{e}^{i}\le 1 }\\ {\beta _{e}^{i}+k^{i}(\beta _{max}-\beta _{e}^{i})},&{} {\beta _{e}^{i}\ge 1} \\ \end{array} \right. }$

$k^{i}$ is a constant in ]0, 1] defined by each agent.

$V_{e}^{im}(t)\ge V_{e}^{iM}(t)$ because ${\beta _{e}^{iM}}$ leads to concession more quickly than ${\beta _{e}^{im}}$. Thus the range of values to be offered at time t is the set of attribute’s values such that the score values are between $V_{e}^{iM}$ and $V_{e}^{im}(t)$ (Fig. 3).

Fig. 4.

$a_{1},a_{2}$ use, respectively, methods $A, A'$ and $B,B'$ to compute, respectively, parameters $\beta _{e}^{1}, \beta _{e}^{1m}, \beta _{e}^{1M}$ and $\beta _{e}^{2}, \beta _{e}^{2m}, \beta _{e}^{2M}$ for attribute e. $a_{1}$ will concede faster than $a_{2}$.

Fig. 5.

$a_{3},a_{4}$ use, respectively, methods $A, A'$ and $B,B'$ to compute, respectively, parameters $\beta _{e}^{1}, \beta _{e}^{1m}, \beta _{e}^{1M}$ and $\beta _{e}^{2}, \beta _{e}^{2m}, \beta _{e}^{2M}$ for attribute e. They use, respectively, $k_{e}^{3}=0.5$ and $k_{e}^{4}=0.5$. Thus, they first expected score value is equal to 0.63. $a_{1}$ will concede faster than $a_{2}$.

4.3 Common Tactic Defined by an Alliance

When the alliances in ${g_{x}}$ agree on an offer and form a new alliance ${L_{k}}$, they establish common negotiation tactics to be used at the next round. This is done by computing the average weight across all agents belonging to this alliance. Specifically, $\beta _{e}^{L}$ is computed according to $w_{e}^{L}$ with ${w_{e}^{L}= \frac{\sum \limits _{i\in L}w_{e}^{i}}{2}}$. The couple of parameters ${(\beta _{e}^{Lm},\beta _{e}^{LM})}$ to be used when they must negotiate a partial solution for e is determined according to ${\beta _{e}^{L}}$.

4.4 Negotiation Outcome

At the end of the negotiation, it could happen that several alliances are formed. These alliances may share attributes of which values may be different. To determine the negotiation outcome, only alliances that share no attributes are merged. There may exist several alternatives to merge alliances. The merging process we propose aims to determine the alliances to be merged in order to get an effective and fair solution. A solution is acceptable when it is supported by more than $50\%$ of the agents (i.e. the majority) and holds all of the attributes at stake. In Fig. 1, the solution supported by $\lbrace a_{1},a_{2},a_{3},a_{5},a_{6}\rbrace$ is acceptable. The merging process may generate several acceptable solutions which are compared in order to determine a unique effective solution.

5 Theoretical Analyse

To analyse the complexity of our negotiation mechanism, we focus on evaluating the number of formed clusters during the negotiation process. Each attribute at stake may interest one or more agents. We denote by $n_{e}$ the number of agents which negotiate over the attribute e. To reach a final solution for this attribute, all of the $n_{e}$ agents must meet to exchange in different clusters when the negotiation progresses. Each agent must negotiate with all of the agents with which it shares its attributes. We analysed the number of clusters in which attribute e is negotiated. We consider two situations: the negotiation in both best and worst cases (Fig. 5).

5.1 Negotiation in the Best Case

The best case: whenever the agents in a cluster negotiate, they find an agreement and become one alliance (see Fig. 6).

• In the best case, the number of clusters to be formed to reach a final solution for e is the sum of geometrical sequence’s terms with a common ratio $\frac{1}{2}$ and a first term equal to $\lfloor \frac{1}{2}\times n_{e}\rfloor$.

At round $S_{1}$ of the negotiation, the number of formed clusters is: $U_{S_{1}}= \lfloor \frac{1}{2}\times n_{e}\rfloor$.

$$U_{S_{q}}=\lfloor \frac{1}{2^q} \times n_{e}\rfloor \quad if \quad \frac{1}{2^q} \times n_{e}-\lfloor \frac{1}{2^q} \times n_{e}\rfloor \le 0.5 \quad with \quad 1 \le q \le Q$$

$$U_{S_{q}}= \lceil \frac{1}{2^q} \times n_{e} \rceil \quad if \quad \frac{1}{2^q} \times n_{e}-\lfloor \frac{1}{2^q} \times n_{e}\rfloor > 0.5 \quad with \quad 1 \le q \le Q$$

Q is the number of negotiation rounds. $U_{S_{q}}$ is the number of clusters to be formed at the round $S_{q}$. The expression of $U_{S_{q}}$ allows taking into account the case where the number of alliances to be clustered is an odd number. The total number of clusters to be formed during all of the negotiation rounds is the sum of the Q first terms of the geometrical sequence. Q is such that $U_{S_{Q+1}}=0$.

5.2 Negotiation in the Worst Case

The worst case: whenever the agents in a cluster negotiate no agreement is found. The cluster will be split (see Fig. 6).

• In the worst case, the number of formed clusters is the number of 2-combinations that can be formed from the $n_{e}$. More formally, the number of 2-combinations is equal to the binomial coefficient. $\left( {\begin{array}{c}n_{e}\\ 2\end{array}}\right) =\frac{n_{e}!}{2!(n_{e}-2)!}$.

Fig. 6.

Example of a negotiation between 4 agents over an attribute e.

• For each attribute e, the number of clusters where it is negotiated is limited. This number is between $\sum \limits _{\begin{array}{c} q=1 \end{array}}^{Q} U_{S_{q}}$ and $\frac{n_{e}!}{2!(n_{e}-2)!}$.

In our protocol, several attributes may be negotiated in a cluster.

• When all of the attributes interest all of the agents the number of clusters in which these attributes are negotiated is limited. This number is between $\sum \limits _{\begin{array}{c} q=1 \end{array}}^{Q} U_{S_{q}}$ and $\frac{n_{e}!}{2!(n_{e}-2)!}$.

In each round, the agents in each cluster negotiate over the set of attributes at stake. So the number of clusters to be formed does not depend on the number of attributes but it depends on the number of agents.

• When each agent is interested in a part of the attributes at stake and their subset of attributes are disjoint no cluster will be formed. This case is not interesting because there is no negotiation.

• When each agent is interested in a part of the attributes at stake and the subsets of attributes from these agents overlap, the number of clusters to be formed depends on the degree of the similarity of the agents according to their subsets of attributes.

6 Experimental Results

We have implemented our model in Java/Jade. We considered a set of agents $\mathcal {A}$ which negotiate over multiple attributes . Each agent $a_{i}$ selects randomly its attributes in and randomly assigns a weight to each one. It computes, for each chosen attribute e, the parameters . Each agent selects randomly the criteria that it uses to generate its offers. We tested our protocol with each of these strategies and we analyse their effect on the results of the negotiation. To evaluate the convergence of our protocol we performed several tests by varying negotiation parameters such as the deadline and the strategies used to compute the negotiation tactics.

Fig. 7.

Comparison between our model and the centralized model (all of the agents form one group) according to agreement rate. In our model the agents use with strategies A,A’ and B,B’.

We performed several tests by varying the number of agents and the strategies they use to compute negotiation tactics. We tested our protocol with up to agents. We compared our protocol with a negotiation model where all of the agents form only one group to negotiate. We ran the protocol several times and computed the average of the obtained convergence rates for each execution. In these tests, the number of issues at stake was not varied. The graphs in Fig. 7 show the convergence rate obtained for each pair of strategies and used to compute the negotiation tactics. The empirical results in Fig. 4 show that agents concede more quickly when they use than when are used. The graph in Fig. 7 proves that when the agents concede, this facilitates the convergence of the negotiation. We observe that our protocol converges faster when strategies are used. Figure 7 shows also the convergence rate obtained when a centralized model is used (where all of the agents form one group to negotiate) by varying the number of agents. Our protocol allows the agents to reach more agreements when the number of agents grows. The results show that our protocol allows the agents to reach more agreements than the centralized mechanism as the number of agents and issues grow. We also observe that when the ratio between the number of agents and the number issues grows the number of agreements reached is lower (Fig. 8).

Fig. 8.

The rate of agreement reached by varying number of agents and issues. Text in grey and bold represent, respectively, the best rate of agreement and the worst rate of agreement. This table shows the rate of agreement reached by agents after three negotiation rounds. Columns to represent, respectively, the results for agents, agents and agents while varying the number of issues from to .

7 Conclusion

This paper presented a multi-lateral negotiation model over multiple issues. Our approach allows the agents to progressively build a collective solution addressing all of the issues at stake. We present various negotiation tactics that enable the agents to determine the offers to be proposed and to make concessions. In our empirical analysis, we tested the influence of the negotiation tactics on the negotiation outcome. We have additionally evaluated the convergence of the negotiation under various settings and have demonstrated promising convergence rates.