=Paper=
{{Paper
|id=None
|storemode=property
|title=Experiments with Protocols for Service Negotiation
|pdfUrl=https://ceur-ws.org/Vol-752/25-31badicaetal.pdf
|volume=Vol-752
|dblpUrl=https://dblp.org/rec/conf/asa/BadicaS11
}}
==Experiments with Protocols for Service Negotiation==
https://ceur-ws.org/Vol-752/25-31badicaetal.pdf
PROCEEDINGS OF THE WORKSHOP ON APPLICATIONS OF SOFTWARE AGENTS
ISBN 978-86-7031-188-6, pp. 25 - 31, 2011
Experiments with Protocols for Service Negotiation∗
Costin Bădică and Mihnea Scafeş
University of Craiova, Software Engineering Department
Bvd.Decebal 107, Craiova, RO-200440, Romania
{badica costin scafes mihnea}@software.ucv.ro
Abstract. In this paper we provide experimental results concerning the impact
of the negotiation protocol onto the quality of the negotiation outcome as well
as onto the communication complexity of interactions incurred during negotia-
tions. We evaluate experimentally three negotiation protocols (Direct Task As-
signment, Contract Net and Iterated Contract Net) with respect to two perfor-
mance measures: negotiation outcome (i.e. utility) and communication complex-
ity (i.e. number of messages transferred), by assigning different busy profiles to
the contractors. We find that the Direct Task Assignment delivers the worst av-
erage outcome, but at the same time it uses the lowest number of messages. The
Contract Net and Iterated Contract Net deliver much higher utility on average, but
the Iterated Contract Net obtains the highest outcome for some configurations at
the cost of the highest number of messages.
1 Introduction
We have developed a conceptual framework for service negotiation that addresses pro-
tocols, subjects and decision components in a collaboration system for helping human
experts and population to deal with disasters (see the FP7 DIADEM project1 that targets
crisis management in the context of chemical incidents in industrial and urban areas).
Our framework supports generic one-to-many negotiations and it defines two roles:
manager and contractor [4, 2]. The manager is the agent that requests a service and thus
initiates the negotiation. The contractor is the agent that is able to provide the service
requested by the manager. For a more complete review of the conceptual framework,
please see [1]. A brief description of the design and implementation is given in [3].
Currently we have configured our framework with three negotiation protocols that
we have found useful in disaster and environment management problems. These pro-
tocols are Direct Task Assignment (DTA), Contract Net (CNET) and Iterated Contract
Net (ICNET)2 . For more information see [3].
Negotiation participants playing either the manager or contractor roles use utility
functions to quantify their preferences over proposals. In our framework the manager
∗
Mihnea Scafeş was supported by IOSUD-AMPOSDRU contract 109/25.09.2008.
1
DIADEM Distributed information acquisition and decision making for environmental man-
agement: http://www.ist-diadem.eu/.
2
CNET and ICNET are standardized by Foundation for Intelligent Physical Agents,
see http://www.fipa.org/specs/fipa00029/ and http://www.fipa.org/specs/
fipa00030/
25
PROCEEDINGS OF THE WORKSHOP ON APPLICATIONS OF SOFTWARE AGENTS, 2011
uses a weighted additive utility function over the negotiation issues to evaluate propos-
als and to select the service provider.
2 Experiments
Let us assume that a manager agent M is negotiating for contracting a service from a
contractor agent that is member of a set of n contractors C1 , . . . , Cn . Each contractor Ci
is characterized by her profile defined as a triple ([umin i , ui ], ci , bi ). Each contractor Ci
max
can offer a utility value ui to the manager such that ui ∈ [umin i , ui
max
] ⊆ [0, 1]. ci ∈ [0, 1]
is the probability that she will be able to satisfy the requirements set by the manager’s
{ }
request. Ci has a busy profile bi = bi1 , bi2 , . . . bim , where m is the maximum number
of iterations and bi j , 1 ≤ j ≤ m is the probability of the contractor Ci being busy
during iteration j. We assume that always bim = 0, so that Ci will propose during the
last negotiation iteration. The busy profiles are not taken into account when using the
DTA and when using CNET, only the busy probability of the first iteration is taken into
account. Busy profiles are mostly taken into account when using the ICNET protocol,
which is based on multiple iterations. Depending on the utilized protocol the negotiation
will incur a certain communication cost estimated as the number of messages exchanged
between the manager and the contractor during the negotiation. Moreover the quality
of the negotiation outcome will be estimated as the utility perceived by the manager for
the contracted service.
If the manager is utilizing the DTA negotiation protocol then she will randomly
assign the task to one of the contractors. However, a contractor that does not meet the
requirements will not be able to provide the service, so she will have to report failure. In
this case the manager will randomly select another contractor and so on, until a suitable
contractor is found (we assume this is always the case). Note however that this trial-
and-error process performed by the manager affects the outcome of the negotiation by
decrementing her perceived utility. More precisely, if the successful contractor Ci that
could perform the task was selected in the k-th trial then the utility perceived by the
manager will be ui × (1 − (k − 1)/n) rather than ui . Moreover, the communication cost
associated to this negotiation interaction consists of 2 ∗ k message exchanges.
If the manager is utilizing the CNET negotiation protocol then she will select the
contractor Ci that provides her the highest utility ui from those contractors that met
the requirements of the call for proposals and were not busy (i.e. they were able to
bid). The communication cost consumed for a busy contractor consists of 2 message
exchanges, while for a not busy contractor (it doesn’t matter if she could met or not the
requirements, according to the CNET negotiation protocol [4] she either proposed or
refused to bid) the communication cost consists of 3 message exchanges.
If the manager is utilizing the ICNET protocol we assume that she will perform as
many negotiation iterations as needed to select one contractor. We simplify the nego-
tiation by assuming that contractors do not change their bids between iterations. This
assumption is not as restrictive as it might look, because some contractors are busy and
can bid only in a late iteration. Moreover, we also assume that a busy contractor that
meets the requirements of the call for proposals will always find time to bid during a
certain negotiation iteration. The communication cost for a busy contractor consists in 2
26
PROCEEDINGS OF THE WORKSHOP ON APPLICATIONS OF SOFTWARE AGENTS, 2011
message exchanges, while for a non-busy contractor it consists of 3 message exchanges,
for each iteration.
In the simulation we considered one manager and 100 contractors.
There are at most 3 negotiation iterations and we consider 3 busy profiles that we
can assign to contractors:
1. available during the first and the second iteration with equal probability. In this case,
bi = {0.5, 0, 0 . This profile says that a contractor will be able to respond during the
first or the second iteration, but no later than the second iteration. These contractors
respond during the first stages of the negotiation.
2. mostly busy during the first iteration, but available during the second iteration for
sure. In this case, bi = {0.9, 0, 0 . This profile says that a contractor will be able
to respond during the first iteration in few situations, but it will surely respond
during the second iteration. These contractors respond during the middle stage of
the negotiation.
3. not available during the first iteration, but available during the second and third
with equal probability. In this case, bi = {1, 0.5, 0 . Contractors having this profile
do not respond during the first iteration, but they will respond during the second or
the third iteration, no later than the third iteration. These contractors respond during
the last stages of the negotiation.
In the experiment, we assign the three busy profiles to contractors by following
a certain configuration and for each configuration we run a bundle of 2000 negotia-
tions. We vary the percentage of contractors that have been assigned the three busy
profiles with a step of 5%. For example, we start from (0, 0, 100), meaning that all
the contractors have been assigned the third busy profile and then we continue with
(0, 5, 95), (0, 10, 90), . . . (100, 0, 0), in the final configuration all the contractors having
been assigned the first busy profile.
The values of the utilities ui are randomly selected for each negotiation instance
assuming uniform distributions. For this experiment, we consider [umin i , ui ] = [0, 1].
max
The status of the contractor (as satisfying or not satisfying the requirements of the man-
ager) is randomly selected for each negotiation instance, according to the probability ci .
We fixed the probability ci to 0.5 for all negotiations, for all configurations and for all
contractors.
We are interested in how each of the studied protocols performs in terms of outcome
and message traffic for each configuration of contractors. We run the negotiations in the
experiment for each negotiation protocol.
Figure 1 shows the utility of the manager when using the DTA protocol. The scale
labelled “first” shows the percentage of the contractors that can propose mostly during
the first iterations of the negotiation, i.e. they have been assigned the first busy profile.
The scale labelled “middle” shows the percentage of contractors that have been assigned
the second busy profile. The percentage of the contractors that have been assigned the
third profile is not shown in the figure, but it can be obtained by taking into account the
fact that the sum of all the percentages is 100.
The maximum utility for DTA is a little over 0.5, making this the most inefficient
protocol in terms of utility. The status of being “busy” is not taken into account by the
27
PROCEEDINGS OF THE WORKSHOP ON APPLICATIONS OF SOFTWARE AGENTS, 2011
Fig. 1. Utility for DTA
manager when she is playing the DTA negotiation protocol, i.e. if she selects a certain
contractor then the task will be assigned to her in any case. Nevertheless, if the assigned
contractor cannot finalize the task successfully then she will report failure and conse-
quently the manager will retry the operation of service contracting by assigning the task
to another contractor. However, the utility is almost the same for all configurations, the
average being around 0.5.
Fig. 2. Messages for DTA
Figure 2 shows the message statistics for the same protocol. In terms of messages,
DTA performs very well, being the protocol with the lowest number of messages, out-
performing the other protocols by far.
28
PROCEEDINGS OF THE WORKSHOP ON APPLICATIONS OF SOFTWARE AGENTS, 2011
Fig. 3. Utility for CNET
Figure 3 shows the utility for CNET, which was expected to decrease as the number
of contractors that propose during the first iteration decreases, because it receives less
proposals and the probability to receive good proposals (i.e. of high utility) decreases.
An interesting fact is that the utility decreases almost exponentially as the number of
contractors that propose during the first iteration decreases.
Fig. 4. Messages for CNET
The message count increases linearly with the number of contractors that propose
during the first iteration (Figure 4).
For ICNET (Figure 5), the utility decreases almost as for CNET until a point where
almost all contractors propose during iterations 2 & 3. Then it grows back to the initial
maximum very fast.
29
PROCEEDINGS OF THE WORKSHOP ON APPLICATIONS OF SOFTWARE AGENTS, 2011
Fig. 5. Utility for ICNET
Fig. 6. Messages for ICNET
30
PROCEEDINGS OF THE WORKSHOP ON APPLICATIONS OF SOFTWARE AGENTS, 2011
When most of the contractors propose during iterations 2 & 3, the message count
grows exponentially to over 400 (see Figure 6. For the rest of the configurations, the
message count varies almost the same as for CNET.
As future work we plan to expand the experiments in at least two directions: (i) to
consider more complex negotiation instances that take into account more negotiation
iterations, as well as that contractors might change their bids and managers can change
their strategy for accepting contractors’ bids during each iteration; (ii) to consider more
complex workflows involving at least two interdependent negotiations such that the
contracted service might also involve contracting of other required services.
References
1. Bădică, C., Scafeş, M.: Conceptual Framework for Design of Service Negotiation in Disaster
Management Applications. In: Bai, Q., Fukuta, N. (eds.), Advances in Practical Multi-Agent
Systems, Studies in Computational Intelligence 325, 359–375 Springer Verlag (2010)
2. Paurobally, S., Tamma, V., and Wooldridge, M.: A Framework for Web service negotiation.
ACM Transactions on Autonomous and Adaptive Systems 2(4), ACM Press (2007)
3. Scafeş, M., Bădică, C., Pavlin, G., and Kamermans, M.: Design and Implementation of a
Service Negotiation Framework for Collaborative Disaster Management Applications. Pro-
ceedings of the 2nd International Conference on Intelligent Networking and Collaborative
Systems INCOS’2010, 519–524 (2010)
4. Smith, R.G.: The Contract Net Protocol: High-Level Communication and Control in a Dis-
tributed Problem Solver. IEEE Transactions on Computers 29(12), 1104–1113 IEEE Com-
puter Society (1980)
5. Yang, J., Li, W.-L., and Hong, C.-Y.: An Improvement to CNCP in Large-Scale Muti-Agent
System. Proccedings of the 3rd International Conference on Innovative Computing Informa-
tion and Control ICICIC’08, 147 (2008)
31