Coalition Formation with Multiple Alternatives of Interdependent Tasks

Abstract

In this paper, we consider the problem of coalition formation in multi-agent systems that exhibit externalities. We consider multiple self-interested agents each of which has a goal it needs to achieve. Each agent may have several alternative sets of dependent tasks leading it to achieve its goal. Execution of tasks may be more beneficial when done by a group of agents and not by a single agent. In fact, to achieve their goals, the agents need to form sequential interdependent coalitions to perform their tasks within an alternative. However, tasks dependencies lead to coalitions dependencies. To account for the effects of each coalition on the rest of the possible coalitions, the agents need to form all needed coalitions at once. This problem, denoted here as a One-shot Coalition Formation Problem ($\mathcal {OCFP}$), is quite challenging and particularly important for multi-agent system. We describe it and present a multi-lateral negotiation mechanism that solves it by allowing the agents to conduct iterative negotiations on their respective tasks within their alternatives. A heuristic-based approach that considers the distance between each agent’s desired alternative and other agents’ proposed coalitions is introduced and evaluated.

1 Introduction

In this paper we introduce a new problem of coalition formation with externalities, called: One-shot Coalition Formation Problem $(\mathcal {OCFP})$, for which the coalition formation process should be considered as a one-shot activity. Coalition formation is defined as the process of forming a group of agents to perform a set of common tasks that the agents are unable to perform alone, or they do so inefficiently [11]. We consider a set of self-interested agents, each of which has several alternative sets of tasks, leading it to achieving its goal. We address cases in which task dependencies exist, hence each task may require outputs of other tasks for its performance. For example, Fig. 1 illustrates 4 agents $\{ a_1, a_2, a_3, a_4 \}$, representing 4 individuals, each wants to move from a starting city (nodes $\{a,b,c\}$) to a destination city (nodes $\{j,k\}$) and share its path segments costs (tasks $\{t_j \ | \ j=1..15 \}$) in order to reduce its total path cost. Each one may have several possible sequential tasks (paths) leading it to a goal (destination). Agent’s sequential tasks are represented by a directed acyclic graph. In such a context, each agent may need to form a series of coalitions at different points in time to reach its goal. In the literature, this is performed as a sequential coalitions formation process (coalition after coalition). Doing so, can lead to the formation of coalitions with inferior utility and to sub-optimal task execution and goal satisfaction¹. The problem here is that, after a coalition is formed at time t, another more beneficial coalition might no longer be possible at time t + 1 because of conflicting dependencies among remaining tasks. The challenging question is how to avoid live-locks when getting commitments? In particular, due to task dependencies, each agent may prefer to get a commitment from others, before committing to any coalition. In fact, dependencies among tasks lead necessarily to dependencies among possible coalitions.

For example, consider the case of agent $a_1$, whose goal is to move from city a to city j (cf. Fig. 1). $a_1$ aims to locate which path minimizes its cost (we assume that if two agents perform a task together, they share the induced cost). Thus, it may prefer to form a coalition with $a_2$ for tasks $t_1$ and $t_3$, and then another coalition with $a_3$ and $a_4$ for $t_5$. $a_1$ may alternatively go through $t_2$. In fact, $a_1$ has to get the needed commitments from $a_2, a_3$ and $a_4$ at the same time. However, $a_2$ and $a_4$ also have several alternatives that they may consider before committing to any coalition. The main motivation of each agent is to reach its goal and minimize costs. Its focus is therefore not on a coalition for the current task but on a coalition structure that meets its final goal. A coalition structure comprises several coalitions in which the agent is involved. Each coalition is associated with a time interval in which its tasks are executed. We assume that, within each structure, the time intervals do not intersect and there are no temporal conflicts. We require that coalitions that form allow agents to reach their goals and minimize their costs. For this, the agents should take into account the dependencies between tasks, to avoid non-beneficial coalition structures. Note that, when following a task-by-task coalition formation approach² some tasks may become impossible to perform and some agents may become unavailable, negatively affecting benefits. Thus, the quality of a coalition depends both on endogenous and exogenous factors.

Fig. 1.

Alternatives sets of agents $a_{1}, a_{2}, a_{3}, a_{4}$.

Plenty of coalition formation approaches have been proposed, but only a few of them deal with task dependencies [1, 9, 11]. Moreover, none of them facilitate the formation of multiple coalitions in a one-shot activity³, as required in $\mathcal {OCFP}$.

Against this background, we introduce the One-shot Coalition Formation Algorithm ($\mathcal {OCFA}$)—a distributed coalition formation algorithm that solves $\mathcal {OCFP}$ and meets its unique requirements. Here, in forming coalition structures, each agent has to take into account inter-coalition dependencies, allowing it to reach its goal at a minimum cost (or maximum gain). The formation of one coalition may affect the gain expected from other possible coalitions. Note that $\mathcal {OCFP}$ is different from the problem of coalition structures generation (CSG), where the aim is to find the coalition structure that maximizes the social welfare, or minimizes the agents’ deviation from their initial desired coalitions. Commonly, the CSG problem deals with partitioning the agents into mutually disjoint groups, to improve their performance [10]. In $\mathcal {OCFP}$, coalition structure generation focuses on identifying, for each agent, a profitable group of tasks from among multiple alternatives it has. It additionally seeks groups of agents—not necessarily disjoint—to perform the selected group of tasks. Moreover, in difference from the classical CSG problem, it considers the timing of sequentially executed dependent tasks. CSG may consider the time required for executing a task, but it does not deal with sequential task execution and the resulting temporal dependencies.

Our approach is heuristic-based, where the agents compute different metrics for making the decision on offers to be made, to be accepted or to be confirmed. Our mechanism comprises several steps: (i) Agents search for possible coalition structures, accounting for their utility functions and for dependencies among tasks. (ii) Agents’ aspirations are derived, and taken into account in future proposals. (iii) At each round, agents estimate the gap between their proposals and those of the other agents. (iv) Agents rank their possible coalition structures using a ranking strategy based on a set of characteristic and valuation parameters.

The remainder of this paper is organized as follows. Section 2 discusses related work. Section 3 presents the one-shot coalition formation method. Section 4 presents the experimental evaluation and Sect. 5 concludes this paper.

2 Related Work

There are few studies on coalition formation that deal with dependencies among tasks. Shehory et al. [11] aim at allocating tasks to agents in a distributed approach, but they do not consider several possible alternatives. In a centralized approach, Ramchurn et al. [1] address agent allocation for performing tasks with spatial and temporal constraints, but they do not consider multiple alternatives. Arib et al. [2] address situations where agents plan their activities dynamically and use these plans to coordinate their actions and search for the coalitions to be formed. In [10], mutually disjoint coalitions are formed by partitioning the set of agents, each task is allocated to a group of agents. Bistaffa et al. [3] assume that the agents are cooperative and the overall approach is centralized. Greco et al. [6] propose a model, based on the concept of valuation structure, for coalition structure generation. Hoefer et al. [8] analyze the effects of structural constraints but limited to the hedonic coalition formation games. In $\mathcal {OCFP}$, we do not necessarily allocate all tasks, and agents might be involved in several coalitions. Task inter-dependencies, and several possible subsets of tasks that reach a goal in different ways, have a prominent influence here. Also, we focus on self-interested agents with partial information sharing about others, e.g., utility functions are private.

Note that $\mathcal {OCFP}$ is different from the commonly known problem: Multi-Agent Planning (MAP) [4, 5, 7, 12] even if both assume agents with an individual set of tasks as input and as output a non-conflicting execution of their tasks. The major differences between MAP and $\mathcal {OCFP}$ are: (i) coordination: interdependent tasks are assigned to different agents, aiming at finding a non-conflicting execution of their plans. In $\mathcal {OCFP}$, the agents’ alternatives are assumed to be non-conflicting if they are executed individually. So, the aim is not to coordinate task execution, but to identify which possible executions can be more beneficial. (ii) joint tasks: joint tasks are predefined and known by all agents. The aim is to coordinate agents’ plan execution accordingly. In $\mathcal {OCFP}$, we assume that the tasks can be considered joint or disjoint depending on whether they are shared across alternatives or not. (iii) negotiation: negotiation is, mostly, about needed resources to perform tasks. In $\mathcal {OCFP}$, negotiation is about groups of tasks and agents to perform them. Furthermore, in planning via negotiation, it is assumed that the agents negotiate over the same set of tasks, which is different in $\mathcal {OCFP}$.

3 Coalition Formation Method

An $\mathcal {OCFP}$ is a tuple $\langle \mathcal {A}, \mathcal {T}, \mathcal {U}, \mathcal {G}, t_{limit}\rangle$ where $\mathcal {A} = \{a_{1}, a_{2}, ..., a_{n}\}$ is a set of self-interested agents, $\mathcal {T} = \{t_{1}, t_{2}, ..., t_{m}\}$ is a set of inter-dependent tasks, $\mathcal {U} = \{ u_{1}, u_{2}, ..., u_{n} \}$ is a set of utility functions⁴, one for each agent, $\mathcal {G} = \{g_{1}, g_{2}, ..., g_{n}\}$ is a set of goals, one for each agent, and $t_{limit} \in \mathbb {R}^{+}$ is the time limit for the coalition formation process. The aim of each agent a is to find a set of coalitions with respect to the dependencies to reach its goal g with the best possible value of u. A goal g can be reached by performing a set of tasks, that we call an alternative and denote $\alpha$. An agent may have several possible alternatives leading it to its goal. For instance, agent $a_{1}$ (cf. Fig. 1) has 3 alternatives, $a_{2}$ has 2, $a_{3}$ has 1 and $a_{4}$ has 4 alternatives. We denote by $\Pi _i$ the set of alternatives of an agent $a_i$.

In $\mathcal {OCFA}$ (Algorithm 1), we allow agents to identify beneficial coalitions to form, and to maintain an overall view on their possible coalitions during the coalition formation process. Specifically, we allow agents to engage in several negotiation threads with different disjoint agent groups, for different task sets. We have devised a mechanism that consists of a protocol and a set of strategies. We decompose the coalition formation process into several distinctive steps: 1) Exchange of alternatives: The agents exchange their alternatives; 2) Proposals generation: The agents compute their coalitions proposals, and compute the coalition structures; 3) Proposals: The agents select a desired alternative, then exchange their proposals accordingly; 4) Acceptances: The agents exchange their acceptances about the exchanged proposals; 5) Confirmations: The agents exchange their confirmations about the accepted proposals. The $\mathcal {OCFA}$ begins with the computation alternatives, where each agent computes it own. Then, it sets the nextStep variable to the Exchange of alternatives step. As long as no coalitions are formed and the time limit is not reached, it loops and iterates through the steps: Proposals generation, Proposals, Acceptances and Confirmations.

The Exchange of alternatives step is followed by the Proposals generation step, during which each agent proceeds to analyzing each alternative’s tasks and their corresponding dependencies in order to identify common tasks among them. A common task is common across two or more agents’ alternatives. The set of common tasks of an agent a is denoted $ft_{a} = \{t \ | \ t \in \bigcup \alpha _{a}, \ \exists a' \in \mathcal {A}: a' \ne a \wedge t \in \bigcup \alpha _{a'} \}$. For instance, for agent $a_{1}$ (cf. Fig. 1), all its tasks are common tasks except $\{t_{2}, t_{6}\}$. That is, $ft_{a_1} = \{t_{1}, t_{3}, t_{4}, t_{5}, t_{7}\}$. Then, the common tasks are grouped into sets according to the agents’ alternatives, that we call common sets of tasks (fs). Hence, for an agent a, the set of common sets is $\{ fs_{a} = \langle \mathcal {A}_{fs_{a}}, \mathcal {T}_{fs_{a}} \rangle \ | \ \forall t \in \mathcal {T}_{fs_{a}}, \forall a' \in \mathcal {A}_{fs_{a}}: a \ne a' \Rightarrow t \in ft_{a} \cap ft_{a'} \}$. A tuple $\langle \mathcal {A}_{fs}, \mathcal {T}_{fs} \rangle$ is a combination of a set of successive common tasks $\mathcal {T}_{fs}$, with respect to the dependencies, which can be performed by a group of agents $\mathcal {A}_{fs}$. For instance, an example of common sets for agent $a_{1}$ is: $\{ \langle \{a_{1}, a_{2}\}, \{t_{1}, t_{3}, t_{4}\} \rangle$, $\langle \{a_{1}, a_{2}\}, \{t_{1}, t_{3}\} \rangle$, $\langle \{a_{1}, a_{3}, a_{4}\}, \{t_{5}\} \rangle \}$. The set of common sets is then used to compute possible coalitions and coalition structures. We define a coalition as a tuple $c = \langle \mathcal {A}_{c}, \mathcal {T}_{c} \rangle$, where $\mathcal {A}_{c} \subseteq \mathcal {A}$ is a set of agents, $\mathcal {T}_{c} \subseteq \mathcal {T}$ a set of tasks and $\exists fs_{a}, fs_{a'}, a \ne a':\mathcal {A}_{c} = \mathcal {A}_{fs_{a}} = \mathcal {A}_{fs_{a'}} \wedge \mathcal {T}_{c} = \mathcal {T}_{fs_{a}} = \mathcal {T}_{fs_{a'}}$. We assume that $|\mathcal {A}_{c}| \ge 2$, $|\mathcal {T}_{c}| \ge 1$ and agents in $\mathcal {A}_{c}$ have agreed to perform the tasks in $\mathcal {T}_{c}$. A coalition structure $cs=\{c \ | \ \exists \alpha : \mathcal {T}_{c} \subseteq \alpha \}$ is defined as a set of coalitions to perform tasks over an alternative $\alpha$. We denote the set of all the coalitions of an agent $a_i$ by $\mathcal {C}_i$ and its coalition structures by $\mathcal {CS}_i$. Once the coalition proposals are computed, they are grouped into coalition structures according to the agents’ alternatives. This allows the agents to explore and keep updated their overall view on their alternatives. Hence, each alternative $\alpha$ corresponds to a coalition structures cs. We denote this association by $\mathcal {CS}(cs) = \alpha$. The set of the agents in a coalition structure is denoted $\Lambda (cs)$ and the set of its tasks is denoted $\varGamma (cs)$. Let’s consider $\alpha _{1,3} = \{t_{1}, t_{3}, t_{4}, t_{6}, t_{7}\}$ (cf. Fig. 1), the third alternative of the agent $a_{1}$; examples of possible coalitions are: $c_{1} = \langle \{a_{1},a_{2} \}, \{t_{1},t_{3}\} \rangle$, $c_{2} = \langle \{a_{1},a_{2},a_{4} \}, \{t_{4}\} \rangle$, $c_{3} = \langle \{a_{1},a_{3},a_{4} \}, \{t_{5}\} \rangle$, $c_{4} = \langle \{a_{1},a_{3}\}, \{t_{7}\} \rangle$, $c_{5} = \langle \{a_{1},a_{2} \}, \{t_{1},t_{3},t_{4} \} \rangle$. An example of a coalition structure that corresponds to $\alpha _{1,3}$ is: $cs_{1,3} = \{ c_{1},c_{2},c_{4} \}$. So, for an alternative, it is not required that its associated coalition structure fulfills all of its tasks.

3.1 Multilateral Negotiation Protocol

The negotiation protocol $\mathcal {NP}$ comprises three main steps: it starts with the Proposals step, proceeds with the Acceptances step, and ends with the Confirmations step. The agents can evaluate their possible coalition structures at the end of each step. They exchange proposals, but this does not entail a commitment to any specific coalition structure. For instance, after sending proposals to different agent groups, the sender agent is not required send them acceptances even if it receives acceptances from most of the agents (but not from all⁵). As each coalition might affect other possible coalitions, a coalition proposal that has not been accepted by an agent might render all other coalition proposals impossible to achieve because of the dependencies. During the negotiation, the agents send and receive proposals, acceptances and confirmations for coalitions to be formed. If sent proposals have been followed by acceptances, agents can go ahead by confirmations or change their proposals and not accept those they have sent. They can also avoid confirming proposals they proposed and accepted earlier. In our protocol, an agent’s confirmation of a proposal is not a binding agreement. Only mutually received confirmations about a specific coalition is a binding agreement. Therefore, once an agent has confirmed a proposal, it stays committed to it, unless none of the involved agents has sent a confirmation during the same negotiation round r.

Agents communicate via messages $\mathtt {m}=(\mathtt {t}, \mathtt {a}, \mathtt {a'}, \mathtt {c})$ where $\mathtt {t}$ is the performative, $\mathtt {a} \in \mathcal {A}$ is the sender, $\mathtt {a'} \subseteq \mathcal {A}_{c}$ ($|\mathcal {A}_{c}| \ge 1$) is the receiver and $\mathtt {c}$ is a coalition proposal. The set of all the sent and received messages is denoted $\mathcal {M}$. To facilitate negotiation, we introduce some interaction rules R$_{i}$:

• R$_{1}$: $\mathtt {m}=(Proposal, a, a' \in \mathcal {A}_{c}, c)$ can be submitted about c several times, but not during the same negotiation round r.

• R$_{2}$: $\mathtt {m}=(Accept, a, a' \in \mathcal {A}_{c'}, c')$ can be submitted, in a round r, only for agents $a'$ that have sent proposals about $c'$ to the agent a.

• R$_{3}$: $\mathtt {m}=(Confirm, a, a' \in \mathcal {A}_{c'}, c')$ can be submitted, in a round r, only for agents $a'$ that have accepted a proposal $c'$.

• R$_{4}$: During r, for two agents a and $a'$, an agreement can be established about a coalition c, only if both agents have confirmed it.

To be involved in a negotiation process, an agent starts by selecting a coalition structure cs and sending its coalition proposals $c \in cs$ to the agents $a \in \mathcal {A}_c$ (R$_{1}$). Then it waits to receive other agents’ proposals (during the same round r). If no proposals are received, the agent waits to the next round and selects another coalition structure $cs'$ to propose⁶. Else, if there are received proposals, the agent can send back acceptances if the received proposals meet its expected utility regarding its sent proposals (R$_{2}$). Then, the agent waits for others’ acceptances too. In case it receives acceptances that meet its expected utility, it replies to the senders with confirmations (R$_{3}$). Then, it waits for their confirmations. If it receives at least one confirmation, it must respect it, even if it does not fully meet its expected gain (R$_{4}$). If it receives no confirmation during the same round, it is considered free and returns to proposals step (R$_{1}$).

3.2 Ranking Coalition Structures

To engage in the negotiation protocol, an agent needs, at each Proposals step, to select a coalition structure cs from which it formulates its coalition proposals to other agents. To facilitate that, agents need to update their overall view on all possible coalition structures at each negotiation round. We introduce the profile structure ps, that should allow agents to characterize each of their coalition structures, and then, rank them accordingly.

Definition 1

A profile structure $ps = \langle t_{1}, t_{2}, ..., t_{| \bigcup (t \in \alpha \in \Pi )|} \rangle$ of a set of alternatives $\Pi$ is a vector that contains all the tasks in $\Pi$.

That is, each agent’s set of alternatives has a specific profile structure associated with it, which is defined according to the agent’s set of tasks. For instance, the profile structure of the set of alternatives of agent $a_{1}$ (cf. Fig. 1) is: $ps_{a_1} = \langle t_{2}, t_{7}, t_{1}, t_{3}, t_{5}$, $t_{4}, t_{6} \rangle$. We further define the alternative profile, which is a data representation structure characterizing each alternative of an agent.

Definition 2

An alternative profile $p^{\alpha } = \langle e_{1}, e_{2}, ..., e_{|ps|} \rangle$ is a binary vector defined over an alternative $\alpha$ regarding a profile structure ps, where $e_{i} \in \{0,1\}$, $e_{i} = 1$ means $t_{i} \in \alpha$ and $e_{i} = 0$ means $t_{i} \notin \alpha$.

For instance, let’s consider $\alpha _{1,3} = \{t_{1}, t_{3}, t_{4}, t_{6}, t_{7}\}$. Its profile is: $p^{\alpha _{1,3}} = \langle 0, 1, 1, 1, 0, 1, 1 \rangle$. Since a cs is associated with an $\alpha$, for ease of presentation, for the rest of this paper we assume that $p^{cs} = p^{\alpha }$ (a coalition structure profile is the same profile of the alternative with which it is associated: $p^{\alpha _{1,3}} = p^{cs_{1,3}}$) . Taking into account only the desired alternative of an agent for selecting the coalition structure to propose might lead to cyclic negotiation. To avoid this, an agent needs to consider other agents’ proposals to derive their intentions. Hence, we introduce the agent’s coalition structure view:

Definition 3

A coalition structure view $\upsilon ^{a'}_{cs}=\{c' \ | \ \exists c \in cs: \mathcal {T}_c = \mathcal {T}_{c'} \wedge a \in \mathcal {A}_{c'} \}$ is the set of received coalition proposals $c'$ from an agent $a'$ that are also proposed by a to $a'$ as coalition proposals c.

So, a coalition structure view $\upsilon ^{a'}_{cs}$ is a coalition structure that contains only coalition proposals received from agent $a'$ and that concerns only tasks in $\varGamma (cs)$. $\upsilon ^{a'}_{cs}$ is called: $a'$’s view on agent’s a coalition structures cs. For instance, suppose that agent $a_{1}$ has received a set of coalition proposals from $a_{2}$ about the tasks $\{t_{1}, t_{3}, t_{4}\}$ at round $r=2$. So, for $a_{1}$, the coalition structure view of $a_{2}$ on $cs_{1,3}$ is $\upsilon ^{a_{2}}_{cs_{1,3}} = \{ c'_{1} = \langle \{a_{1},a_{2} \}, \{t_{1},t_{3}\} \rangle$, $c'_{2} = \langle \{a_{1},a_{2},a_{4} \}, \{t_{4}\} \rangle \}$ and its profile is $p^{\upsilon ^{a_{2}}_{cs_{1,3}}} = \langle 0, 0, 1, 1, 0, 1, 0 \rangle$.

During the negotiations, the agents need to estimate how much an alternative $\alpha$, represented by a coalition structure cs, is close to the proposals sent by other agents. For this purpose, we introduce the footprint function $\sigma$ which computes how a coalition structure cs, represented by its profile $p^{cs}$, of agent a is close to another agent’s $a'$ view on cs, denoted by $\upsilon ^{a'}_{cs}$ and represented by its profile $p^{\upsilon ^{a'}_{cs}}$. $\sigma$’s value is defined as:

$$\sigma (p^{cs}, p^{\upsilon ^{a'}_{cs}}) = \mathop {\sum }\nolimits ^{i = 0 .. |ps|}_{e_{i} \in p^{cs}, e'_{i} \in p^{\upsilon ^{a'}_{cs}}} (e_{i} @ e'_{i}) ,\text { where}, $$

$$ e_{i} @ e'_{i} = \left\{ \begin{array}{l} 1, \ if: \ e_{i} = e'_{i} = 1 \\ 1/|ps|, \ if: \ (e_{i} = 1 \wedge e'_{i} = 0) \vee (e_{i} = 0 \wedge e'_{i} = 1) \\ 0, \ if: \ e_{i} = e'_{i} = 0 \end{array} \right. $$

The footprint of the coalition structure $cs_{1,3}$ regarding the proposals of $a_{2}$ is: $\sigma (p^{cs_{1,3}}, p^{\upsilon ^{a_{2}}_{cs_{1,3}}}) = \langle 0,1,1,1,0,1,1 \rangle @ \langle 0,0,1,1,0,1,0 \rangle = (0@0)+(1@0)+(1@1)+(1@1)+$ $(0@0)+(1@1)+(1@0) = 0+1/7+1+1+0+1+1/7 = 3.29$.

For an agent a, the footprint is computed for each round r between the coalition structure cs of the sent coalition proposals and other agents’ views on cs. But this value alone is not sufficient to reflect the global view on possible coalition structures according to agents’ proposals. Hence, we introduce the distance function $\pi ^{r}_{cs}$ to estimate the evolution made during negotiation regarding each alternative. It measures the distance between cs and all the coalition structure views on cs of other agents $a' \ne a$. Its value is computed at each round $r > 1$, regarding $(r-1)$ as follows:

$$\pi ^{r}_{cs} = \mathop {\sum }\nolimits _{a' \in \Lambda (cs) } \sigma ^{r}(p^{cs},p^{\upsilon ^{a'}_{cs}}) - \sigma ^{r-1}(p^{cs},p^{\upsilon ^{a'}_{cs}})$$

This allows agents to estimate how and which alternative is becoming close (or not) to other agents’ proposals. For instance, suppose that $a_{1}$ has received a set of coalition proposals $c=\{ \langle \{ a_{2}, a_{1}\}, \{ t_{1}\} \rangle \}$ from $a_{2}$ at round $r=3$ ($a_{1}$ wants to try alternative $\alpha _{1,3}=\{t_{1},t_{3},t_{4}, t_6,t_7\}$ and $a_{2}$ wants to try alternative $\alpha _{2,2}=\{t_{1},t_{9},t_{10}\}$). For $a_{1}$, $p^{\upsilon ^{a_{2}}_{cs_{1,3}}} = \langle 0,0,1,0,0,0,0 \rangle$. So, the footprint: $\sigma (p^{cs_{1,3}},p^{\upsilon ^{a_{2}}_{cs_{1,3}}}) = 1.57$. Then, for $a_1$, the distance of $cs_{1,3}$ according to the received coalition proposals from $a_{2}$ between $r=2$ and $r=3$ is: $\pi ^{3}_{cs_{1,3}}(\sigma ^{3}, \sigma ^{2}) =$ $\sigma ^{3} - \sigma ^{2} =$ $\sigma ^{3}(p^{cs_{1,3}},p^{\upsilon ^{a_{2}}_{cs_{1,3}}}) - \sigma ^{2}(p^{cs_{1,3}},p^{\upsilon ^{a_{2}}_{cs_{1,3}}}) = 1.57- 3.29 = - 1.72$. The distance $\pi ^{r}_{cs}$ is interpreted by a, regarding $a'$ as follows ($\mathcal {CS}(cs) = \alpha$):

• $if \ \pi ^{r}_{cs} \ge 1$ Strong convergence: $\exists t \in \alpha$ which was not proposed by $a'$ in $r - 1$ but proposed in r;

• $if \ 0< \pi ^{r}_{cs} < 1$ Weak divergence: $\exists t \notin \alpha$ which was proposed by $a'$ in $r-1$, but not proposed in r;

• $if \ 0> \pi ^{r}_{cs} > -1$ Weak convergence: $\exists t \notin \alpha$ which was not proposed by $a'$ in $r-1$, but proposed in r (having a new proposed task t even if $t \notin \alpha$ may render an alternative other than $\alpha$ close to the proposals of $a'$);

• $if \ \pi ^{r}_{cs} \le - 1$ Strong divergence: $\exists t \in \alpha$ which was proposed by $a'$ in $r - 1$ but not proposed in r;

• $if \ \pi ^{r}_{cs} = 0$: no evolution.

In addition to the estimated distance, which is based on the presence and absence of tasks in agents’ proposals and considers only two consecutive rounds (the current round r, and $r-1$), the agents need to take into account earlier information to reflect trends in the whole negotiation process and update the ranking order of their coalition structures. Hence, we introduce several parameters with concern to different aspects, as explained hereafter:

• Estimated utility weight ($\varepsilon$): is a normalized value ($\varepsilon \in [0,1[$) of the coalition structure estimated utility u(cs): $\varepsilon = \left\{ \begin{array}{l} 1 - \frac{ u(\delta )}{ u(cs) }, \ if \ u(\delta )\ne 0 \\ 0, \ otherwise \end{array} \right.$ where $u(\delta )$ denotes the agent utility reference value⁷ and $u(cs) > u(\delta )$. We assume that if $u(cs) \le u(\delta )$, cs will not be considered for negotiation.

• Tasks weight (rf): is a value reflecting how much tasks $t \in \varGamma (cs)$ are desired by other agents through their coalition proposals: $rf = \frac{\sum _{c \in cs } \sum _{t \in \mathcal {T}_{c} } \frac{ fr(t) }{ |\mathcal {A}_{c}|}}{\sum _{t' \in \mathcal {T}} fr(t')}$ where fr(t) returns the number of coalition proposals $c'$ for which $t \in \mathcal {T}_{c'}$.

• Coalition structure weight (w): is a value estimating the importance of a coalition structure cs, regarding other coalition structures: $\omega = \frac{rec(cs)}{ |\Lambda (cs) |}$ where rec(cs) returns the number of agents that have sent coalition proposals $c': \mathcal {T}_{c'} \cap \varGamma (cs) \ne \emptyset$. Note that, while rf focuses on the received proposals concerning a task t, w focuses on the agents that have sent proposals about tasks $t \in \varGamma (cs)$. The former returns a value according to the number of tasks in an alternative set, and the latter returns a value according to the number of agents involved in a coalition structure.

• Sent proposals weight (sf): is a value estimating the importance of a coalition structure cs for an agent, during the negotiation: $sf = \frac{ sent(cs)}{r}$ where sent(cs) returns the number of times cs was selected by the agent to send its coalition proposals, and r is the current negotiations round. The rationale here is that, the more a coalition structure cs is selected, the more it is preferred by the agent.

• Distance weight ($\vartheta$): is a normalized value of the distance $\pi _{cs}^{r}$:

  $$\vartheta = \left\{ \begin{array}{l} - \frac{ \pi _{cs}^{r} \times |\alpha | }{ |\mathcal {T}|^{2} }, \ if \ -1<\pi _{cs}^{r}<0 \ or \ 0<\pi _{cs}^{r}<1 \\ \frac{ \pi _{cs}^{r} \times |\alpha | }{ |\mathcal {T}|^{2} }, \ otherwise \end{array} \right. $$

where r indicates the current round of negotiation. $\mathcal {NP}$ allows agents to update their view about the possible coalition structures by keeping updated the above set of parameters, that we call, characteristic parameters $\mathcal {P} = \{ \varepsilon , \omega , rf, sf, \vartheta \}$, where $\forall e \in \mathcal {P}: -1 \le e \le 1$ prior to each proposals’ step. Additionally, to allow agents to rank their coalition structures during negotiation, we propose a ranking function named coalition structure acceptance indicator $\mathcal {V}_{cs}:(\mathcal {P} \times \tilde{\mathcal {P}}) \longrightarrow \mathbb {R}$, which is based on $\mathcal {P}$ and a set of valuation parameters $\tilde{\mathcal {P}} = \{ \tilde{\varepsilon }, \tilde{\omega }, \tilde{rf}, \tilde{sf}, \tilde{\vartheta } \}$, where $e \in \tilde{\mathcal {P}}: e > 0$. $\tilde{\mathcal {P}}$ is assumed to be initialized by the user to provide its preferences as follows:

• $\tilde{\varepsilon }$: valuation of the Estimated utility weight ($\varepsilon$).

• $\tilde{\omega }$: valuation of the Coalition structure weight (w).

• $\tilde{rf}$: valuation of the Tasks weight (rf).

• $\tilde{sf}$: valuation of the Sent proposals weight (sf).

• $\tilde{\vartheta }$: valuation of the Distance weight ($\vartheta$).

The valuation parameters values are computed at each round using the heuristic in (Algorithm 2), according to $\pi$. These parameters reflect the negotiation trend, thus allowing agents to explore the set $\mathcal {CS}$ by establishing a ranking order over it. The value of $\mathcal {V}_{cs}$ is defined as follows:

$$\mathcal {V}_{cs}(\mathcal {P}, \tilde{\mathcal {P}}) = (\tilde{\varepsilon })^{\varepsilon } + (\tilde{\omega })^{\omega } + (\tilde{rf})^{rf} + (\tilde{\vartheta })^{\vartheta } - (\tilde{sf})^{sf}$$

At the beginning (round $r=1$), each agent ranks its coalition structures by using its estimated utility, u(cs), defined as the expected utility if all involved agents $a \in \Lambda (cs)$ accept or confirm to perform jointly all the tasks $t \in \varGamma (cs)$. For rounds $r>1$, prior to each Proposals step, the agents use $\mathcal {V}_{cs}$ to rank their coalition structures. In addition to the characteristic parameters in $\mathcal {P}$, the valuation parameters in $\tilde{\mathcal {P}}$ are used as a means to introduce a valuation mechanism, allowing agents to prefer one parameter over others in $\mathcal {V}_{cs}$, according to the observed evolution in the negotiation. In doing so, agents will be able to dynamically react and select a coalition structure according to a specific characteristic parameter by increasing their valuation of that parameter.

In fact, having one valuation parameter notably superior to the others, makes the agent select the coalition structures, mostly, according to its associated characteristic parameter. For instance, if a user (represented by an agent) wants to find a coalition structure with a low cost, he can introduce a higher value of the valuation parameter $\tilde{\varepsilon }$. Note that such parameter preference may incure, in some cases, undesirable results. For example, having a higher value of $\tilde{\varepsilon }$ might lead agents to negotiate only the most beneficial coalition structures. In this case, a larger value of the valuation parameter $\tilde{sf}$ can force agents to alternate the proposals they send and explore more possibilities. For example, (in the heuristic in Algorithm 2), when $\pi = 0$ which means there is no evolution in the negotiation, we cancel the effect of the Distance weight and increase the valuation of the sent proposals weight (which will be subtracted in $\mathcal {V}_{cs}$) to decrease an agent’s value of coalition structures that are sent more frequently. In doing so, we guarantee that the agent will adopt an exploration attitude and try to find a coalition structure by exploring different coalition structures. This aims to avoid cyclic negotiation where each agent proposes the most preferred proposals in cs again and again, even though cs cannot be a solution.

3.3 Decision Making

Agents’ decisions are made based on their utility from the proposals, and acceptances at hand at each step. Ahead of the negotiation, an agent sets its referred utility value, denoted $u(\delta )$. After the first ranking (r = 1), an agent selects the coalition structure cs that has the highest $u(cs) > u(\delta )$ and sends all of the coalition proposals $c \in cs$ to all of the involved agents $a \in \mathcal {A}_c$. We assume that if $u(cs) = u(\delta )$, the agent will prefer to perform the tasks $t \in \varGamma (cs)$ alone. After sending all of the coalition proposals $c \in cs$, the agent updates its estimated utilities u(cs) according to the received coalition proposals and decides whether to accept proposals (if $u(cs) > u(\delta )$), or not. In case that $u(cs) \le u(\delta )$, it will select another coalition structure $cs'$ to propose. After sending acceptances about cs, the agent updates its estimated utility based on the received acceptances. If $u(cs) > u(\delta )$, it sends confirmations to the agents that have sent it acceptances and, then, waits to receive their confirmations too.

4 Experimental Evaluation

In this section, we experimentally evaluate $\mathcal {OCFA}$, (implemented in Java). To this aim, we assume that each task has a public cost $O^{+}(t)$, known by all the agents and a private cost $O^{-}(t)$, specific for each agent and only known by the owner. That is, for each agent, the cost of each task is $O(t) = O^{+}(t) + O^{-}(t)$. The cost of a coalition structure cs is denoted O(cs). We denote by $O^{max}$ the $cs \in \mathcal {CS}$ maximum cost and $O^{min}$ the $cs \in \mathcal {CS}$ minimum cost. Additionally, we introduce an allowed cost⁸ to assume by each agent during negotiations as: $O^{*} = \frac{O^{max} + O^{min} }{2}$. The estimated utility⁹ of each coalition $u(c)= \sum _{t \in \mathcal {T}_{c}}O(t) - [\ \sum _{t \in \mathcal {T}_{c}} (\frac{O^{+}(t)}{|\mathcal {A}_{c}|})+ O^{-}(t)]$, and $u(cs) = \sum _{c \in cs} u(c)$. So, the agents will search for a coalition structure where its cost $O(cs) < O^{*}$ and its utility verifies $u(cs) > u(\delta )$. We assume that the reference utility $u(\delta ) =0$.

In the first experiment, we consider 3 agents $\mathcal {A} = \{a_{1}, a_{2}, a_{3}\}$ with a limitation rate ($1 \geqslant O^{\bullet } \geqslant 0$) on the allowed cost for each agent. We additionally redefine $O^{*}$ as $O^{*} = O^{*} \times O^{\bullet }$. Further, for ease of presentation, we assume that all agents have the same alternatives set (same tasks) but with different costs. We assume that each alternatives set has 12 tasks, forming six alternatives ($\alpha _{1}, \alpha _{2}, \alpha _{3}, \alpha _{4}, \alpha _{5}, \alpha _{6}$). First, the results (Fig. 2) show that, starting from $O^{\bullet } = 1$ to $O^{\bullet } = 0.52$, the more we decrease $O^{\bullet }$, the more the negotiation requires more rounds to reach a solution. In fact, lower values of $O^{\bullet }$ make the agents accept lower costs, so, seek for higher gains. For instance, for $O^{\bullet } = 0.60$ a solution was found at round $r=11$ and for $O^{\bullet } = 0.52$ a solution was found at $r=24$.

Fig. 2.

Cost limit vs. negotiation rounds. Here, we studied the effect of decreasing $O^{*}$ during negotiation on the number of rounds to find a solution. The experimental settings we consider are $\tilde{\mathcal {P}}= \{\tilde{\varepsilon }=30, \tilde{\omega }=2, \tilde{rf}=5, \tilde{sf}=7, \tilde{\vartheta }=15\}$, $O^{+}(t) = 30$, $\forall t \in \mathcal {T}$, and $O^{-}$ is randomly generated: $0> O^{-}(t)<20$ for each task.

Second, we study the way the value of $\mathcal {V}_{cs}$ is obtained. Hence, we focus on the values of the elements $\tilde{\varepsilon }^{\varepsilon }$, $\tilde{\omega }^{\omega }$, $\tilde{rf}^{rf}$, $\tilde{\vartheta }^{\vartheta }$ and $\tilde{sf}^{sf}$ that define the value of $\mathcal {V}_{cs}$. To this end, we initialize $\tilde{\mathcal {P}} = \{\tilde{\varepsilon }=8, \tilde{\omega }=2, \tilde{rf}=20, \tilde{sf}=15, \tilde{\vartheta }=5 \}$, fix $O^{\bullet } = 0.52$ and keep the same alternatives sets as in the first experiment. Here, we have considered two cases for the agent $a_{1}$, which has an initial order over its alternatives, from the most beneficial to the less beneficial: $\alpha _{6}, \alpha _{3}, \alpha _{1}, \alpha _{2}, \alpha _{5}, \alpha _{4}$. In the first case, we study the contribution rate (the percentage of $\tilde{\varepsilon }^{\varepsilon }$, $\tilde{\omega }^{\omega }$, $\tilde{rf}^{rf}$, $\tilde{\vartheta }^{\vartheta }$ and $\tilde{sf}^{sf}$ values in $\mathcal {V}_{cs}$ value) for the most beneficial alternative $\alpha _{6}$ (cf. Fig. 3A) (which is the worst for other agents), and in the second case, we study the contribution rate for the final selected alternative $\alpha _{3}$ which has led to the solution (cf. Fig. 3B). During the negotiation, a solution was found at round $r=10$. The sent proposals from $a_{1}$ to the others at round at $r = 1$ : were about $\alpha _6$, at $r = 2$ : $\alpha _4$, at $r = 3$ : $\alpha _6$, at $r = 4$ : $\alpha _6$, at $r = 5$ : $\alpha _6$, at $r = 6$ : $\alpha _5$, at $r = 7$ : $\alpha _5$, at $r = 8$ : $\alpha _5$, at $r = 9$ : $\alpha _3$ and at $r = 10$ : $\alpha _3$. The results show that, in the first case (cf. Fig. 3A), for $r < 6$ where the most sent proposals were those for $\alpha _{6}$, the value $\tilde{sf}^{sf}$ was more substantial in rounds where $\pi < 0$ ($r=1,r=3,r=5$). After that, for $r \in [6,8]$, $\tilde{sf}^{sf}$ was less substantial, as proposals other than $\alpha _{6}$ were sent, induced by substantial values of $\tilde{\varepsilon }^{\varepsilon }$, $\tilde{\omega }^{\omega }$, $\tilde{rf}^{rf}$, $\tilde{\vartheta }^{\vartheta }$. For $r = 9$, the agent has observed an important convergence with the other agents, then the contribution of $\tilde{\vartheta }^{\vartheta }$ value in $\mathcal {V}_{cs}$ of $\alpha _{3}$ has been adjusted to be the most substantial value in order to keep $\alpha _{3}$ for the next round which has led to the solution at round $r = 10$.

In the second case (cf. Fig. 3B), as the alternative $\alpha _{3}$ was in the second position in the first established order, the results show that during negotiation ($r \le 8$) the most substantial value is that of the estimated cost $\tilde{\varepsilon }^{\varepsilon }$. The other values were mostly at the same level until round $r = 9$, during which the agent has observed an important convergence between others’ proposals and the alternative $\alpha _{3}$. Therefore, the value of $\tilde{\vartheta }^{\vartheta }$ was adjusted to maintain it for the next round, which has led to an effective solution at $r=10$.

Fig. 3.

The percentage (%) of $\tilde{\varepsilon }^{\varepsilon }$, $\tilde{\omega }^{\omega }$, $\tilde{rf}^{rf}$, $\tilde{\vartheta }^{\vartheta }$ and $\tilde{sf}^{sf}$ values in $\mathcal {V}_{cs}$ value at each round for $\mathcal {V}_{\alpha _{6}}$ (Fig. A) and $\mathcal {V}_{\alpha _{3}}$ (Fig. B).

In the third experiment, we aim at evaluating the $\mathcal {OCFA}$ by varying the number of negotiating agents and the number of alternatives in their respective alternatives sets. For this experiment, we introduce a new performance measure: Efficiency ($\varphi$), which is computed as an average of the gained profits across all agents over multiple experiments:

$\varphi = \frac{\sum _{1}^{n} \left( \frac{\sum _{a_{i} \in \mathcal {A} } u_{i}(\alpha _{i,k}) }{|\mathcal {A}|} \right) }{ N_{exp}}$ where n is the number of runs within an experiment given $O^{\bullet }_{i}$, $N_{exp}$ is the number of the experiments and the utility of the selected alternative $\alpha _{i,k}$ for an agent is: $u_{i}(\alpha _{i,k}) = \frac{ O^{-}_{i} - O^f_{i}(\alpha _{i,k}) }{ O^{-}_{i} }$ where $O^f_{i}(\alpha _{i,k})$ is the effective cost of $\alpha _{i,k}$ according to the formed coalitions and, $O^{-}_{i}$, is the minimum individual cost (i.e. the best cost that an agent can get when performing the preferred tasks alone).

As there is no comparable approach with our algorithm in the literature, we compare our results to the Best Alternative Algorithm ($\mathcal {BAA}$). In fact, we didn’t a comparison with an optimal solution approach, because the agents are selfish and do not reveal their private information. Hence, such a solution approach (for instance, by a linear programming solver) is not feasible in our problem. In $\mathcal {BAA}$, each agent orders all of its possible alternatives, it then selects its preferred alternative $\alpha ^{*}_{i}$ and proposes the coalition structure cs ($\alpha ^{cs}$) associated with it to the involved agents $a \in \Lambda (sc)$. After that, each agent $a \in \Lambda (cs)$ that has received a proposal concerning a coalition $c \in cs$ it proposed, will accept and confirm it to its respective sender¹⁰.

Fig. 4.

Efficiency vs. number of agents and alternatives (6 alternatives for Fig. A, 11 for Fig B, 12 for Fig. C and 19 for Fig. B). We examine 8 different sets of agents $|\mathcal {A}|=3..10$, each having different alternatives. We performed 4 different sub-experiments, for each set of agents, by varying the number of alternatives per agent (6, 11, 12, 19). We considered 10 values of $O^{\bullet } \in \{1$, 0.95, 0.90, 0.85, 0.80, 0.75, 0.70, 0.65, 0.60, $0.55\}$. The results represent the average of 20 runs for each value of $O^{\bullet }$.

As can be observed in Figs. 4A, 4B, 4C and 4D, the efficiency of $\mathcal {OCFA}$ is clearly higher than the efficiency of $\mathcal {BAA}$. We remark that the efficiency is in correlation with both the number of agents and the number of alternatives. Note however that higher efficiency values were recorded for $\{6,11\}$ alternatives and $|\mathcal {A}| \in \{8,9,10\}$ agents. The variation in efficiency values when increasing the number of agents is more significant in cases where the agents have less alternatives. The first observation is that, for both approaches, the interval between the minimum and the maximum efficiency values is inversely proportional to the number of alternatives. As we increase the number of alternatives, we get a smaller interval. The second observation is that, when we increase the number of alternatives in the $\mathcal {BAA}$ approach, the efficiency interval becomes smaller because of the maximum bound which becomes smaller (from 0.36 to 0.25), and the minimum bound remains mostly the same (around 0.05). In $\mathcal {OCFA}$ the efficiency interval becomes smaller because of the minimum bound which becomes higher (from around 0.21, 0.18 to 0.25), and the maximum bound remains mostly the same (around 0.36, 0.38). The third observation is that, while increasing the number of alternatives, the gap between the efficiency values of the two approaches becomes notably important; for 19 alternatives, the maximum value for $\mathcal {BAA}$ equals the minimum value for $\mathcal {OCFA}$ (cf. Fig. 4D).

5 Conclusion

In this paper, we addressed a new problem of coalition formation as a one-shot activity, where self-interested agents have several alternatives to reach different goals. Our approach is based on a multilateral negotiation protocol $\mathcal {NP}$, which is designed in a cyclic way over three main steps. During each one, agents compute a set of characteristic parameters $\mathcal {P}$ to use in a heuristic function in order to establish a ranking order over possible coalition structures. Our experimental evaluation shows that our approach allows the agents to converge to a solution. This is facilitated by an adjustable raking function that takes into account the trends of the negotiation. In this paper, we did not address scalability issues, and we deliberately did not consider strategic manipulation against our protocol. These aspects are out of scope of this paper. Furthermore, our experiments did not examine time constraints. Such constraints will be addressed in future work too.