International Journal of Computers, Communications & Control
Vol. I (2006), No. 3, pp. 85-92

Coalition Formation for Cooperative Information Agent-Based Systems

Nacer eddine Zarour, Sabrina Bouzidi

Abstract: The communication technology evolution led to an increase of the carried
out services’ and tasks’ number. The aim of actual research in the cooperation and
particularly the negotiation between agents is to reach a coherent global state of the
multiagent system by favoring agents’ synergy. In this paper, we propose a coalition
formation-based negotiation model for the task allocation in the cooperative infor-
mation agent-based systems. In this model, the agent that activates a negotiation
seeks partners for achieving a complex task. The way that the partners take part in
a coalition is done one by one according to the choice of all the coalition members.
This choice is based on a multicriterion analysis. Some obtained experimental results
show the suggested model performances.
Keywords: Negotiation, coalition formation, cooperative information systems, mul-
tiagent systems, task allocation.

1 Introduction

In an open environment as Cooperative Information Systems (CISs), which gathers distributed; het-
erogeneous; and autonomous Information Systems (ISs), the cooperation requires the intervention of a
negotiation process in order to identify and structure the various problems, to propose and defend the
solutions, to re-examine the intentions in a conflict, and finally to confirm the commitments [1]. In our
context, each IS is modelled by an autonomous, rational, and egoistic agent.

Several negotiation models were developed like Market mechanisms [2], Contract Net Protocol [3],
Social Laws [4], MultiAgent Planification [5], and Organizational structures (coalitions, teams, con-
gregations, etc.) [6]. The coalition formation is a negotiation technique which is particularly preferred
for solving the conflicts between agents whose behavior is economic and thus rational. A coalition is a
short-term organization based on specific and contextual commitments of involving agents. This allows
agents to profit from their respective competencies. To solve the task allocation problem, several coali-
tion formation-based models were suggested [7] [8] [3]. However, these models are not adapted to the
context of CISs because they do not define relations of partnership between agents, but rather relations of
subcontracting. Generally in these models, the agent that activates a negotiation process will only decides
to structure the coalition. It selects its partners separately according to its own desires. Consequently, the
agents’ autonomy is not respected.

The objective of this work is to propose a coalition formation-based model for the task allocation in
CISs. The proposed model, named CFoTACIS1 , is inspired from the reality of the cooperation between
entreprises. It respects the agents’ autonomy by allowing them to take part in the coalition formation
process. It is recursive and includes four phases, the initialization, the negotiation, the evaluation, and
the finalization.

The rest of the paper is organized as follows. In the following section, we present some related
work to the coalition formation. In section 3, we develop the suggested negotiation model. Section 4
enumerates the proposed model properties. Some experimental results are presented in section 5. Section
6 summarizes the contributions of this paper and the research perspectives.

1Coalition Formation for Task Allocation in Cooperative Information Systems.

Copyright c© 2006 by CCC Publications
Selected paper from ICCCC 2006



86 Nacer eddine Zarour, Sabrina Bouzidi

2 Related work

According to the literature, we consider two approaches for studying the coalition formation process,
the macroscopic approach and the microscopic one. The macroscopic approach, which is based on the
game theory, considers the coalition as the basic unit [9]. The microscopic approach considers agents as
the basic unit where several models were proposed and applied in many fields, especially the e-business
[10] and the task allocation [7] [8] [3].

We focuss our discussion on the models based on the second approach which deal with the task allo-
cation problem. In [7], the authors proposed a model where agents exchange their preferences w.r.t. the
possible solutions. Although, forcing agents to form alliances ensures the termination of the negotiation
process, but the model does not respect agents’ freedom since it imposes a solution which may not satisfy
all agents.

In [8], the authors propose a model where the agent that activates the negotiation process first filters
agents of its environment. It uses a multicriterion analysis to find agents that best satisfy its requirements.
Then, it starts an argumentative negotiation with the candidates, which are classified according to its
preferences. This approach does not ensure the reach of a consensus but limiting the negotiation time
seems to be a reasonable strategy.

Two models are proposed in [3]. The first one is dedicated to the competitive agents. The agent
selection is based on a preference model, which is built using several criteria. The major inconvenient
of this model is that the representing agent of the coalition has a kind of authority on the coalition
members. In the second model, agents cooperate in an altruistic way. The model ensures the reach
of a consensus and has some advantages like the integration of the new partners one by one in the
coalition. However, the altruistic strategy of agents does not require the gradual integration of agents in
the coalition. This approach seems to be interesting in the case of egoistic agents. In [10], the authors
proposed a formalization of the trust criteria which an agent grants to the other ones of the environment.
This trust modeling ensures the stability in the coalition formation due to its reliability. However, the
authors do not specify how to find the value of the current evaluation of trust. In order to response at this
question in our proposal, we will deduce the trust from some criteria.

3 CFoTACIS: A coalition formation-based negotiation model in CISs

Before describing the suggested model, let us admit the following assumption: an agent which wants
to integrate the CIS must update the portal of this CIS [4]. It must specify its localization, its know-how,
the information about its branch of industry, its competencies, its capital, etc.

CFoTACIS is recursive and includes four phases, the initialization, the negotiation, the evaluation,
and the finalization. In the beginning of the negotiation process, the manager which is the first coalition
member, follows only the model phases. After that, when new partners join the coalition and become
members, all the members try to find the next partner. The negotiation process iters until the coalition
size will be reached. Let us give the essential description of the different phases

3.1 The initialization phase

The manager consults the portal of the CIS (first assumption) to obtain useful informations on agents.
Then, it decomposes the global task into subtasks w.r.t. the agents’ industry branches. For each subtask,
the manager makes a set of the candidates among agents of the environment.



Coalition Formation for Cooperative Information Agent-Based Systems 87

3.2 The negotiation phase

The manager simultaneously sends the proposals to agents of the same set. The message which the
manager sends to the candidates must contain all information about the cooperation project, as well as
the waiting period that accords to them. Then, the manager receives the responses from the candidates.
Figure 1 represents the state transitions for a negotiation between a manager (m) and a candidate (c).
After receiving a proposal from a manager for cooperation, a candidate can:

• refuse to cooperate (refuse(c, m));
• accept to achieve the subtask (accept(c, m));
• accept to achieve the subtask and also propose to achieve another subtask(s) (ok(c, m));
• refuse to achieve the subtask but propose to achieve another subtask(s) (no(c, m));
• not answer. In this case, after the expiry of a waiting period, the manager considers the not reply

as a rejection (refuse(c, m)).

If the candidate agrees to cooperate, it must send to the manager a message that contains its consideration
of the cost and the time for achieving the subtask, as well as the maximum reply time that it grants to the
manager to evaluate the proposal.

Figure 1: State transition graph of the negotiation between the manager (m) and a candidate (c)

3.3 The evaluation phase

After receiving the candidates’ responses, the manager evaluates and classifies them according to
their importances. The evaluation is made using a multicriterion analysis. This phase includes two
stages. The first one deals with the evaluation of the criteria and the second one with the aggregation of
the evaluations.

Criterion evaluation

In this stage, the manager evaluates agents which sent their proposals according to various criteria.
In [11], the author defines a whole of interesting criteria for the selection of the most adequate partner.
We select those which seem most significant to our context. We have classified the criteria into three
categories:

(a) Criteria related to the partner
- the cooperation degree of the candidate agent with the manager (D1)



88 Nacer eddine Zarour, Sabrina Bouzidi

- the cooperation degree of the manager with the candidate agent (D2)
- the quality of the relation (D3) deduced from three others subcriteria:

(i) respect of the allowed time for achieving the subtask (S1)
(ii) the quality of achieving the subtask (S2).
(iii) Honesty with regard to the profit distribution after the last experiment (S3)

- the experiment in the cooperation:
(i) the cooperation number carried out by the partner (A1)
(ii) the cooperation number carried out by the partner without interruption (A2).

(b) Criteria related to the cooperation
- the capital (C1).
- the technical capacity (C2).
- the technological competencies (C3)
- the existence of a single capability (C4).

(c) Criteria related to the candidate agent proposal The candidate must specify in its acceptance
message the time T and the cost C for achieving the subtask.

The aggregation stage

After the evaluation of the different criteria, the manager incorporates the evaluations associated with
all the criteria in order to have an overall estimate of each agent. In CFoTACIS, the aggregation of the
criteria is used in two cases:

(i) For the trust quantification: The trust e, which results from the current relation with the agent
partner, is carried out using the equation

e = p1*S1+p2*S2+p3*S3

Where p1, p2, and p3 are the weights that the agent must specify and p1+p2+p3=1.
(ii) For the evaluation of each candidate: the aggregation operator is defined using a deviation at an

aspiration point which gathers the preferred values of the criteria [12]. The evaluations are represented
using a vector named b. The deviation b to the aspiration point a is defined by the relation.

deviation(a,b) = Maxj=1..p(λ j(aj-bj))

With λ j=1/( Idealj- AntiIdealj) and p is the number of criteria. Ideal is a vector which gathers the
maximal criteria values of the evaluation vector and AntiIdeal is a vector which gathers the minimal
criteria values of the evaluation vector.

The best evaluation d* is that which minimizes the deviation to the aspiration point:

d*=min{ deviation(a,b)}

For well explaining the evaluation mechanism, let us consider the following example. Agents Ag1,
Ag2, and Ag3 are evaluated according only to the criteria criterion1, criterion2, and criterion3 in the
vectors eval1, eval2, and eval3 (table 1).

Agents Ag1 Ag2 Ag3 Ideal antiIdeal λ
Criterion eval1 λ (Ideal-eval1) eval2 λ (Ideal-eval2) eval3 λ (Ideal-eval3)
Criterion1 0.18 0 0.10 1 0.14 0.50 0.18 0.10 12.5
Criterion2 0.16 0 0.12 1 0.15 0.25 0.16 0.12 25
Criterion3 0.10 1 0.18 0 0.15 0.375 018 0.10 12.5
deviation 1 1 0.50
d* 0.50



Coalition Formation for Cooperative Information Agent-Based Systems 89

Table 1: An illustrative example of the adopted aggregation operator

3.4 The finalization phase

After evaluating agents’ proposals, the manager classes agents in a list according to their deviations.
The manager sends the agent which is at the head of the list a message for inviting it to join the coalition;
else it contacts the next agent in the list, and so on.

The coalition members merge their deviation vectors to have a unified view of the candidates. This
merger allows the coalition members to have supplemented information since agents have only a partial
vision of their environment. The merger is carried out by the minimum operator. Let us consider an
example showing how to make the unified evaluation vector. Agent Ag3 is evaluated by the members
Ag1 (eval1) and Ag2 (eval2) w.r.t. to the eleven (11) criteria (see section 3.3.1).

eval1= (0.32, 0.56, 0.88, 20, 10, 2000, 1500, 5, 1, 0.53, 0.23)

eval2= (0.56, 0.12, 0.68, 20, 10, 2000, 1500, 5, 1, 0.53, 0.23)

The unified deviation vector is

eval= (0.32, 0.12, 0.68, 20, 10, 2000, 1500, 5, 1, 0.53, 0.23)

Thus, for each subtask, the coalition members together try to choose the adequate partner.
The negotiation process will be finished when the coalition size is reached, and therefore, the coali-

tion members start the execution of the tasks. Hence, with CFoTACIS, the decision of the coalition
structure is collective.

4 The CFoTACIS Properties

The proposed model presents several advantages. The choice of the partners is carried out by the
coalition members thanks to the unification process of agents’ estimates carried out by each member. The
adopted aggregation operator does not authorize the compensation, which permits to choose a partner
which has acceptable values for all the criteria. CFoTACIS ensures the equity property because it offers
the same chances to the candidates by limiting the time of the binary negotiations. When the candidate
specifies its waiting time, this avoid the coalition members to send message to an agent that is no more
waiting. Consequently, a considerable profit of time will be obtained. When a partner disengages, it is
obvious that it will be sanctioned. This sanction is expressed by the A2 parameter (see section 3.3.1.a). In
this case, the coalition members have two alternatives for replacing the disengaged agent. They propose
the subtask to the coalition members to cheek whether it exists a partner which is interested to achieve
it. Therefore, a new negotiation process is avoided. The second alternative is applied when there are not
members which are interested. The coalition is obliged to start a new negotiation process to find another
partner. Finally, if the manager could not find partners or the required size of the coalition is not reached;
the negotiation process will be remade.

5 Experimental results

We have implemented CFoTACIS using JADE 3.0 (Java Agent DEvelopment). We have compared
its performances with those of a similar model [3]. We remind that in [3], the author proposed two



90 Nacer eddine Zarour, Sabrina Bouzidi

negotiation models. We are interesting to the one dedicated to egoistic agents considering the rationality
of our agents.

We have made several series of experiments. In this paper, we show the effect of varying the agents’
and subtasks’ number on the global time of the negotiation process (figures 2 and 3).

Figure 2: The negotiation time versus the agents’ number for different subtasks’ number in CFoTACIS

Figure 3: The negotiation time versus the agents’ number for different subtasks’ number in the model
proposed in [3]

In each negotiation process, we fixe the subtasks’ number and we increase the agents’ number to
finally deduce the consumed time. The graphs presented in this section are drowning using the Origin
6.0 software.

On the graph of figure 2 (CFoTACIS), we observe that we could vary agents’ number from 2 to 100
and subtasks’ number from 2 to 10. Whereas, on the figure 4 (the comparative model), we could vary
agents’ number only from 2 to 8 and subtasks’ number only from 2 to 7. Therefore, we deduce that the
CFoTACIS’ scalability is stronger than the one of the comparative model. One reason of this result is
that in the comparative model, all agents are in competition for the coalition formation. So, if we have
"n" agents in the system, we have also "n" parallel negotiations which cause a scheduling problem in the
system. On the other hand, we observe that the negotiation time in CFoTACIS increases as agents’ and



Coalition Formation for Cooperative Information Agent-Based Systems 91

subtasks’ number increase. But this increase stills reasonable and very small in comparing it with the one
of the comparative model. This is due to the weak scalability of the last one. Also, in the comparative
model, there is no limitation of the negotiation time between agents

6 Summary and Conclusions

In this paper, we have proposed a coalition formation-based negotiation model for the cooperative
information agent-based systems, named CFoTACIS. The proposed model is inspired from the reality of
the cooperation between enterprises. It includes four phases, the initialization, the negotiation, the evalu-
ation, and the finalization. The essential properties of CFoTACIS are its consideration of the preferences
of the coalition members for choosing the future partners. It does not apply any authority on agents
and ensures the equity by limiting the time of the binary negotiations due to the absence of the cycles
in the proposed negotiation protocol. However, it does not ensure the reach of a consensus but tries to
encourage agents to cooperate. The simulation results show that in CFoTACIS the spent time for the
negotiation is reasonable and the messages’ number is deterministic. These results have been confirmed
by comparing the CFoTACIS’ performances with those of the negotiation model proposed in [3].

In the future work, we will improve CFoTACIS so that it will ensure the reach of a consensus. Also,
we will adopt it in other application fields like e-commerce.

References

[1] L. Putnam, M. S. Pool, “Conflict and Negociation In Handbook of Organizational Communication: An
Intersciplinary Perspective,” F.M.Jablinetal, Eds. Saga Newbury Park,, pp. 549-599, California, 1987.

[2] T. Sandholm, “An Algorithm for Optimal Winner Determinism in Combinatorial Auctions,” In Proc. of the
16th Int. Joint Conf. on AI, Stockholm, Sweden,, 1999.

[3] S. Aknine, “Modèles et méthodes de Coordination des Systèmes Multi Agents,” Thesis of Doctorate, Uni-
versity Paris IX Dauphine-UFR Science of the Organizations,, December 2000.

[4] N. Zarour, M. Boufaida, and L. Seinturier, “A Negotiation Framework for Organizational Information Sys-
tems,” Int. Journal of information Technology and Decision Making (IJITDM). World Scientific Publishing
Co,, vol. 3, nř2, pp. 213-238, June 2004.

[5] A. E. F. Saghrouchni and S. Haddad, “Recursive Model for Distributed Plannin,” In Proc. of the 2nd Int.
Conf. On Multi-Agent Systems (ICMAS’96),, AAAI Press. Kyoto, Japan, 1996.

[6] C. Brooks and E. Durfee, “Congregating and Market Formation,” Proc. of the 1st Int. joint conf. on Au-
tonomous Agents and Multiagent systems,, ACM Press, pp 96-103, 2002.

[7] A. E .F. Saghrouchni and G. Vauvert, “Formation de Coalitions pour Agents Rationnels,” In Proc. of
ILIPN’2000. VIIIth days of LIPN. Multi-Agent Systemes and Formal Specification and Software Technologies
,,Viltaneuse, France 09, 11-12, 2000.

[8] L. K. Soh, C. Tsatsouli, and H. Servey, “A Satisficing Negotiated and Learning Coalition Formation Archi-
tecture,” In V.Lesser, C.Ortiz, and M.Tambe, editors, Distributed Sensor Networks: a Multi-Agent perspec-
tive,,Kluwer Academic Publishers, 04, 25-27, 2001.

[9] L. Larson and T. Sandholm, “Anytime Coalition Structure Generation: an Average Case Study,” Journal of
Experiments and Therotical Al,11, 1-20, 2000.

[10] Vassileva, J. Breban and S. Horsch, “Agent Reasoning Mechanism for Long-Term Coalitions Based on De-
cision Making and Trust,” Computational Intelligence, 18, 4, Special Issue on Agent Mediated Electronic
Commerce,, pp 583-595, Nov. 2002.



92 Nacer eddine Zarour, Sabrina Bouzidi

[11] C. Li and K. Sycara, “A Stable and Efficient Scheme for Task Allocation via Agent Coalition Formation,”
www.2.cs.cmu.edu/ softagents/papers/CCO3.pdf,, 2003.

[12] ] N. R. Jennings, P. Faratin, P. Johnson, M. J. O’Brien, and M. Wiegand, “Using Intelligent Agents to
Manage Business Processes,” Practical application of intelligent Agents and Multi-Agents technology, PAAM
96,1999.

Nacer eddine Zarour, Sabrina Bouzidi
University Mentouri of Constantine

LIRE Laboratory, 25000 Algeria
E-mail: nasro_zarour@yahoo.fr, sab_bouzidi@yahoo.fr