Using Reference Points for Competitive Negotiations in Service Composition

Abstract

In a market of services, it is likely that the number of service implementations that exhibit similar functionalities with varying Quality of Service (QoS) will significantly increase. In this context, the provision of a QoS-aware SBA becomes a decision problem on how to select the appropriate services. The approach adopted in the present work is to model both service providers and customers as software agents, and to use automated agent negotiation to dynamically select a set of provider agents whose services QoSs satisfy the customer’s requirements. The main features that an automated agent negotiation process should satisfy in order to be applied in service composition are discussed concluding that a multi-issue one-to-many negotiation should be used. In such a setting, we show that using reference points for trading off when different provider agents compete to provide the same service, allows to find (near) Pareto optimal agreements if they exist.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

A Service-Based Application (SBA) is a complex business application composed of a number of possibly independent, self-contained, loosely-coupled services, each one performing a specific functionality, and communicating with each other through standard protocols [7]. Such services could be provided by third parties, so the owner of the SBA does not control its execution. A service can be characterized also by quality aspects, i.e., by non-functional features referred to as Quality of Service (QoS) attributes [22].

In a market of services, customers require SBAs with specific QoS requirements, usually expressed as end-to-end requirements, and several service implementations providing the same functionality are available. So, the selection of services providing the required functionalities with QoS attribute values such that the QoS of the resulting application satisfies the customer’s end-to-end QoS requirements is a decision problem. It constitutes an NP-hard problem, complicated and difficult to solve, hence several heuristics approaches have been proposed in the literature.

One of the adopted approaches is to model both service providers and customers as software agents, and to use automated agent negotiation to dynamically select a set of provider agents whose services have QoS values that satisfy the customer’s requirements. In an e-commerce based competitive market of services, QoS values are generally bargainable issues, and their adaptive provision can incentivize the selection of a specific service. Moreover, trading off among issue values allows to search for win–win cooperative solutions for the composition in multi-issue negotiation (e.g., paying higher price for a service delivered sooner).

In this work, we discuss the use of software agents and automated negotiation as a means to dynamically select the set of service providers (Sect. 2) competing to provide a service. The main requirements that an automated agent negotiation process should satisfy in order to be applied in service composition are presented (Sect. 3). Such characteristics differ from standard negotiation approaches, so making it difficult to derive optimality properties of the obtained negotiation results. We show that the negotiation process adopted for selecting services for an SBA, has strong similarity with the automated multi-agent multi-issue negotiation solution adopted in [21] to solve a resource allocation problem (Sect. 4). As such, we show that also when more provider agents compete to provide the same service, it is still possible to obtain negotiation outcomes that are (near) Pareto-optimal for the selected set of providers.

2 Composing QoS-Based Services

The service composition process usually starts from an abstract representation of a composition request, we refer to as an Abstract Workflow (AW). A simple representation of an AW, also known as the workflow structure, is a directed acyclic graph $AW=(AS,P)$ where $AS={AS_{1},\ldots , AS_{n}}$ is a set of nodes, and P is a set of directed arcs. Each node represents an Abstract Service ($AS_i$), i.e., a service description that specifies a required functionality. Each directed arc that connects two nodes represents a precedence relation among the corresponding ASs. In order to provide a required SBA, each $AS_i$ has to be bounded to a concrete service (we will refer to just as service), i.e., a Web service implementing the functionality specified by the corresponding $AS_i$. Services are provided by different agents, and they may be characterized by quality attributes referring to the service non-functional characteristics.

Typical QoS attributes are: cost - the amount that a service requester needs to pay to execute the service; time - the execution time between the requests sent and results received; reliability - the ability of a service to function correctly and consistently; availability - the probability that the service is ready to be invoked; performance - related to the service response time and latency; security - related to confidentiality and access control aspects. It is becoming of vital importance to take into account the value of these attributes when selecting services to provide an executable workflow, since different customers requiring an SBA may have different expectations and requirements on its end-to-end QoS values. In fact, when requiring SBAs users specify their QoS preferences at the workflow level rather than at service level, since they are usually not involved in the service composition process, so they are not aware of how to split a global preference at the level of single services.

2.1 Service Selection

One step of the service composition process is to identify the optimal service selection to meet the user’s QoS requirements [22]. In general, service selection can be modeled as a Multi-dimension Multi-choice Knapsack Problem (MMKP), which is known to be an NP-hard problem. Exact solutions require long-time computations for large problems, so heuristics approaches are necessary.

By the way, optimization-based approaches consider that the provider’s offered values for service QoS attributes are pre-determined and not customizable, but this is unlikely in the context of a dynamic market of services. In fact, the dynamic nature of Web services, and their provision in the Internet-based market of services, require to make the following assumptions:

• the user’s QoS requirements may change according to dynamic market demand-supply conditions,

• the set of services available may change in time,

• the QoS values of services may change according to market demand-supply mechanisms, and so they cannot be fixed at the application design-time.

These assumptions make global optimization-based approaches, as the ones proposed in [4] unfeasible in our scenario. For this reason in this work a negotiation-based approach allowing to consider flexible and negotiable QoS attribute values, is adopted. In our approach, it is assumed that service providers are modeled as software agents, we refer to as Service Providers (SPs), negotiating with a Service Compositor agent (SC) acting on behalf of a user. Negotiation is used for the dynamic selection of the SPs able to provide services whose QoS values, once aggregated, fulfill the user’s QoS preferences.

3 Negotiation Requirements for Service Composition

Software agents are a natural way to represent service providers and consumers, and their defining characteristics are essential to realize the full potential of service-oriented systems. Software agents are autonomous problem solving entities, situated in an environment, able to reach their own objectives and to respond to the uncertainty of the environment they operate in, due to flexible decision making capabilities [12]. These characteristics make software agents a useful computational paradigm to model respectively providers that offer services at given conditions, and consumers that require services at other, sometimes conflicting, conditions. Providers and consumers, interacting according to specified protocols and interfaces, have to establish their agreed conditions to respectively provide and consume services. Software agent automated negotiation is one of the approaches adopted for reaching agreements, so it can be used to select services in a service composition. Nevertheless, when negotiation occurs in a realistic market of services, the market characteristics impose specific requirements on the negotiation process, as described in the following subsections.

3.1 One-to-Many

Negotiation usually takes place between two agents willing to come to an agreement on conflicting interests. Most approaches in service composition, that use negotiation mechanisms to select services according to their QoS values, usually apply negotiation for each required service independently from the others relying on bilateral one-to-one negotiation mechanisms [17, 19]. They apply classical negotiation approaches consisting in bilateral interactions of an alternate succession of offers and counteroffers.

In our approach negotiation is used to dynamically select the SPs that offer services with suitable QoS attribute values, but it is assumed that all the agents offering services are involved in the negotiation process. Hence, given an AW composed of n ASs (with $n \ge 2$), and k SPs (with $k \ge 1$) for each of the n ASs in the composition, the number of potential negotiating agents may vary from $n+1$ to $n*k+1$ agents, where 1 SC agent is in charge of finding the optimal selection of SPs, according to the QoS user’s constraints, to instantiate each AS. Hence, the negotiation is necessarily one-to-many.

3.2 Incomplete Information

In order to prepare an offer $\mathbf x _i^t$ at negotiation round t, a service provider agent i uses a set of negotiation strategies to generate values for each negotiated issue. Of course, agents must be equipped with algorithms to evaluate the received and proposed offers. The value of a specific offer is represented in terms of agent utility. Hence, the utility $U_i$ for an agent i is a function that depends on the specific agent i, and on an offer $\mathbf x _j^t$ such as $U_i(\mathbf x _j^t) \rightarrow [0,1]$.

Usually in SBA negotiation the strategies and utility functions adopted by the provider agents are private information. In fact, when SBAs are provided in an open, dynamic and competitive market of services, it is not realistic to assume that their strategies are shared. Furthermore, these strategies may change depending on the market demand-supply trends, so making their shared knowledge unfeasible without causing communication overheads. For these cases, negotiation mechanisms have to be designed so that negotiators can come to an agreement even though they have no prior knowledge (complete or partial) of the utility functions of the other agents involved in the negotiation. Hence, negotiation occurs in an incomplete information setting where agents utility functions, reserve values in terms of utilities, and concession strategies are private information.

The communication occurs only between the SPs and the SC. In addition, also SC constraints on the QoS of the composition may be private. However, even in the case of public constrains, SPs are not able to directly evaluate such constraints since they are not aware of the other offers.

3.3 Multi-issue

Negotiation on non-functional parameters of the services composing an SBA is clearly a multi-issue one. In fact, when a service is a component of an SBA, even in the case of a single issue, its value has to be composed with the values of the other services in the composition provided in an independent way, so the negotiation becomes a multi-issue one. More specifically, in the single issue case, the SPs formulate offers containing single issues, but the SC has to evaluate them in an aggregated manner, dealing with a multi-issue evaluation.

In this work, we consider multi-issue SPs offers, hence, an offer made by an SP i at round t is a n-tuple $\mathbf x _i^t=(x_{i,1}^t,\dots ,x_{i,m}^t)$, where $x_{i,j}^t$ is a specific value in the domain $\mathfrak {R}$ of the QoS attribute $j \in M$. Multi-issue negotiation is more complex and challenging than single-issue one as the solution space is multi-dimensional, and it is often difficult to reach a Pareto-efficient solution especially in the case of self-interested agents that do not know each other’s preferences [14]. Finally, for a single value of utility, different compositions of issues may be available, making the counteroffer process intractable. Typically the strategy of selecting a different configuration of issues values with the same utility value is called trade-off.

Typical approaches to multi-issue negotiation are package deal and issue-by-issue [10]. In a package deal negotiation, an offer includes a value for each issue under negotiation, so allowing trade-off to be made among issues. Approaches that adopt issue-by-issue negotiation are based on the assumption that the issues under negotiation are independent. If not, the inter-dependency is addressed by negotiating one issue at a time according to a chosen topology [10]. A general approach to composition should include the case of dependency among issues (e.g., price and time). In this case package deal is the only solution and trade-off is possible among issues. When issues values are interdependent, linear and non-linear utility functions can be used (e.g., Cobb–Douglas, widely used in the economics field [15]).

3.4 Coordinated Interaction

The negotiation mechanism allows to establish a sort of Service Level Agreement (SLA) for QoS-aware SBAs between the SC and the selected SPs. As already said, in a composition of services, also when a single issue is negotiated, its global value is given by the aggregation of the QoS values, each one provided by a service for each AS. That means that the offers received by the SC for a single AS cannot be evaluated independently from the ones received for the other ASs, so a coordination among negotiations for the single abstract services is necessary. A negotiation mechanism for service composition should allow both to negotiate with the SPs providing services for each required functionality in the AW, and also to evaluate the aggregated QoS value of the received offers [5]. So a coordination step is necessary. This type of negotiation can be very time-consuming, so the possibility for the SC to concurrently negotiate with the SPs of each AS at the same time is advisable. Generally, a buyer obtains more desirable negotiation outcomes when it negotiates concurrently with all the sellers in competitive situations in which there is information uncertainty and there is a deadline for the negotiation to complete [3]. The coordination step occurs, at the end of each negotiation iteration, when the SC evaluates the aggregation of the received offers in order to allow SPs to adjust their successive offers if an agreement is not reached.

4 The Negotiation Formalization

Let us consider an AW with n ASs (with $n \ge 2$) and m QoS issues (with $m \ge 1$) for each of them, and k SPs (with $k \ge 1$) for each of the n ASs. For each issue j the SC agent has a constraint $C_j$ on the whole AW. The SPs formulate new offers, and the SC evaluates the aggregated value of all considered issues. In this way, it is possible to simulate what happens in a real market of services where a user requesting an SBA does not have information on the SPs strategies. This means that the SC is not able to make single counter-proposals with respect to each received offer, because the change of a value of a particular QoS can impact the constraints to be fulfilled by the QoS of the other services. SC accepts an offer $\mathbf x _i^t = (x_{i,1}^t, \dots , x_{i,m}^t) \in \mathfrak {R}^m$ of the i-th SP if the aggregated value of the offer with the values of the offers for the remaining ASs, satisfies the global constraints, so leading to an agreement.

Definition 1

In case of additive issues, a set of exactly n offers $(\mathbf x _1^t, \dots , \mathbf x _n^t)$ is an agreement (A) at round t $\Longleftrightarrow$ $\sum _{i=1}^{n} x_{i,j}^t \le C_j$, $\forall j \in m$.

If an agreement is reached with the offers sent at round t, the negotiation ends successfully at that round, otherwise all the offers are rejected and, if $t+1 < t_{MAX}$, the SC engages all SPs in another negotiation round until the deadline $t_{MAX}$ is reached. Generally, offers are evaluated in terms of agent utility. In a multi-issue negotiation round an agent can either generate a new offer conceding in its utility (i.e., using a concession strategy), or it can select a new offer with the same utility (i.e., using a trading-off strategy in case of dependent issues). In this latter case, these offers belong to the same agent utility curve known as an indifference curve.

The i-th SP utility is evaluated in terms of its own offer $\mathbf x _i$. In this work we consider evaluation functions that are non-linear. Moreover, the considered evaluation functions are continuous, strictly convex and strictly monotonically increasing in each of the issues.

In general, the utility of an offer $\mathbf x _i$ at round t is evaluated as follows:

$$\begin{aligned} u_{i}(\mathbf {x}_i,t) = \left\{ \begin{array}{lll} 0 &{} \text{ if } &{} \text{ t } = t_{MAX} \,\text{ and } \text{ not }\, (\mathbf A )\\ v_{i}(\mathbf x _{i}) &{} \text{ if } &{} t < t_{MAX} \,\text{ and }\, (\mathbf A )\end{array} \right. \end{aligned}$$

(1)

where, $v_{i}(\mathbf x _{i})$ is the evaluation function, A is an agreement and $t_{MAX}$ is the deadline.

Here, we explicitly model a collaborative approach among different providers of different services to obtain a win–win opportunity. To enhance the possibility to reach an agreement, each agent may choose the issue values corresponding to a benefit for the other agents on its indifference curve. Indeed, while keeping the same value of utility, the agent chooses to collaborate in order to find an alternative that is better for the others, by trading-off among values. Competition remains among providers of the same service, and it occurs at the concession step.

4.1 The Agents Bidding Strategy

In this work, we focus on the collaborative part of the negotiation, i.e., when agents make trade-off, without considering any concession strategy. In particular, we started from the trading-off strategy proposed in [21] for multi-agent multi-issue negotiation, called the orthogonal bidding strategy that was adopted when multiple agents negotiate to distribute units of resources among them. The strategy relies on the possibility of each agent involved in the negotiation to evaluate a so called reference point introduced in [20], taking into account the bids of all the other agents involved in the negotiation. Of course, in multi-agent negotiation a reference point cannot be directly computed by applying a one-to-one agent interaction, as in [14]. The same happens in service composition since a single agent offer cannot be used to determine another agent offer because issues are partitioned among more than two agents.

A reference point of an agent, calculated according to the offers of the other agents, as in [21], allows the agent to select, step by step, a new offer on its indifference curve as the point that minimizes the Euclidean distance between the curve and the reference point. Practically, the reference point of an agent represents the desired bid in order to reach an agreement, keeping fixed all the other agents bids. Note that at each step only one agent can send an offer, while the other offers should be kept fixed, so reference points have to be computed one at a time.

In our reference market-based scenario, it is likely that for each AS in the AW more than one SP may issue offers. For this reason, we adopt the heuristic method proposed in [1] to select at each round a set of agents providing a set of promising offers at that round, by assuming that the issues that are negotiated upon are additive (so the workflow structure is not relevant for their composition). The method consists in evaluating the utility of each offer, and in selecting the most promising set of offers, one for each AS, with respect to the global constraints, by considering global constraints as upper bounds for each issue of the composition. So, a promising combination of offers $\mathscr {B}=(\mathbf b _1^t, \dots , \mathbf b _n^t)$, one for each AS, is obtained.

Definition 2

A selected offer $\mathbf b _k^t$ at round t for the $AS_k$ is the one that maximizes the following equation:

$$\begin{aligned} \sum ^{m}_{j=1} \frac{\underset{\forall x_{i,j}^t \in AS_k}{max}(x_{i,j}^t) - x_{i,j}^t}{\sum _{k=1}^n \underset{\forall x_{i,j}^t \in AS_k}{max}(x_{i,j}^t) - \sum _{k=1}^n \underset{\forall x_{i,j}^t \in AS_k}{min}(x_{i,j}^t)} \end{aligned}$$

(2)

where, $max(x_{i,j}^t)$ is the maximum $x_{i,j}^t$ issue value offered by the agent i for the issue j of all the available offers for the $AS_k$ at time t (i.e., $\forall x_{i,j}^t \in AS_k$), while $min(x_{i,j}^t)$ is the corresponding minimum $x_{i,j}^t$ issue value. Equation 2 estimates how good an offer is, by evaluating the QoS values w.r.t. both the ones offered by the other SPs of the same service, by taking as a reference the maximum offered value for that issue, and the QoS values of a possible combination of offers. In fact, the numerator gives an indication of how good the value of each QoS parameter is with respect to the QoS value offered by other SPs of the same AS, and it is then related to the possible aggregated values of the same issue for all the ASs.

Differently from the work of [21], the offers and the SC constraints are private information, so it is not feasible for each SP to compute its own reference point. For these reasons, in our approach, reference points for each AS are calculated by the SC, as a sort of counteroffer, at the coordination step relying on the offers selected for the most promising combination at a given round. In addition, reference points are sent to all SPs providing the same AS, so involving them again in the negotiation even though not selected. So, the SC plays the role of a sort of mediator, since it is the only one that has the necessary information to compute reference points.

A reference point is defined as follows:

Definition 3

The reference point for the SPs corresponding to an $AS_i$ and to m issues at round t is:

$$\begin{aligned} \mathbf r _{i}^t = \left( C_1 - \sum _{k \in N - \left\{ i \right\} }b_{k,1}^t, \dots , C_m - \sum _{k \in N - \left\{ i \right\} }b_{k,m}^t \right) \end{aligned}$$

(3)

where, $\mathbf b _{k}^t$ is the last bid of agent $k \in N - \left\{ i \right\}$ selected for the considered combination at that round.

In [21], the authors proved that a set of offers $(\mathbf x _{1}^t,\dots ,\mathbf x _{n}^t)$ is an agreement at round t iff each reference point $\mathbf r _{i}$ for each agent i Pareto dominates the bid of the agent it is calculated for, i.e., $r_{i,j}^t \ge x_{i,j}^t$. Starting from this, the authors proved that, when trading-off among possible offers with the same utility, the orthogonal bidding strategy they propose leads to an agreement that is Pareto optimal and that, if it exists, it is unique. The corresponding theorems were proved for the case of $k=3$ and $m=2$. The Definition 3 of reference point is the same as the one defined in [21] with the difference that the constraints $C_j$ (with $j \in M$) are not normalized in the set [0, 1]. So the same theorems apply also in our case provided that reference points are calculated with respect to the set of selected offers at each round, so the Pareto optimality and the uniqueness of the Pareto optimal agreement is referred to the agents providing the set of selected offers $\mathscr {B}$ at the considered round. In fact, different sets of selected offers may lead to different Pareto optimal agreements.

In our approach a reference point, calculated according to Definition 3, is assumed to be the reference point for the entire set of available SPs for each AS at a given round. In this way, all SPs available for each AS are able to negotiate at the successive round by formulating offers based on the value of the reference point, so to avoid discharging offers that may become more promising at successive rounds.

4.2 Weighted Reference Points

When the number of ASs increases, it is undesirable that an SP for a given AS waits for the offers of the others SPs of the remaining ASs to get its reference point, since reference points are computed one at a time. This is even more crucial in an open market of services, since the time spent in negotiation may prevent its use in this scenario. To avoid this, reference points referred to a given round t should be computed relying only on the offers available at the previous round as follows:

Definition 4

The timed reference point for the $SP_i$ corresponding to an $AS_i$ at round $t+1$ is:

$$\begin{aligned} \bar{\mathbf{r }}_{i}^{t+1} = \left( C_1 - \sum _{k \in N - \left\{ i \right\} }x_{k,1}^t, \dots , C_m - \sum _{k \in N - \left\{ i \right\} }x_{k,m}^t\right) \end{aligned}$$

(4)

where, for simplicity there is one SP agent for each AS.

Unfortunately, with this definition of reference point, the convergence of the orthogonal bidding strategy is not guaranteed, but it can diverge and lead to an oscillatory behavior. This is due to the fact that reference points are concurrently computed at round t, and used by the SPs to formulate bids at round $t+1$. This prevents the adjustment of bids for each AS, step by step, within the same round that is a prerequisite for the convergence to the agreement. On the other hand, considering the offers at the previous round when computing reference points, is the only way to concurrently negotiate with the SPs for all ASs, so avoiding that the deadlines for each round depend on the number of ASs. To keep the convergence of the bidding strategy, while keeping the possibility to concurrently compute reference points, it is necessary to provide SPs with reference points that allow for different adjustments of bids, in terms of different “weights” that depend on the issue values of the offers with respect to their aggregated values. For this reason, in [6] we introduced a new reference point, named the weighted reference point ($\hat{\mathbf{r }}_{i}^t$) as follows:

Fig. 1

$\hat{\mathbf{r }}_{i}^{t}$ and $\bar{\mathbf{r }}_{i}^{t}$ for 2 negotiation rounds

Definition 5

The weighted reference point for the $SP_i$ corresponding to an $AS_i$ at round $t+1$ is $\hat{\mathbf{r }}_{i}^{t+1}=(\hat{r}_{i,1}^{t+1},\dots ,$ $\hat{r}_{i,m}^{t+1})$, with $\hat{r}_{i,j}^{t+1}$ defined as follows:

$$\begin{aligned} \hat{r}_{i,j}^{t+1} = \dfrac{x_{i,j}^t}{\sum _{k=1}^{n}{x_{k,j}^t}} \cdot \bar{r}_{i,j}^{t+1}=\omega _{i,j}^{t} \cdot \bar{r}_{i,j}^{t+1} \end{aligned}$$

(5)

where $\omega _{i,j}^{t}$ is the weight of the issue value at time t compared to the aggregated value of all the bids for that issue, and $\bar{r}_{i,j}^{t+1}$ is the timed reference point of Definition 4.

In Fig. 1, the behavior of a negotiation in the first two rounds is reported showing reference points and offers in the case of weighted and timed reference points with the same initial configuration. As shown, for $SP_1$ the $\hat{\mathbf{r }}_{1}^{t}$ value corresponds to a scaled version towards the origin of $\bar{\mathbf{r }}_{1}^{t}$, since the relative weights of the two issues are comparable in the overall agreement. Instead, for $SP_2$ and $SP_3$ the weighted reference points lead to different new bids (number 2) with respect to the case of timed reference points.

According to [6], when trading-off among possible offers with the same utility, the weighted orthogonal bidding strategy leads to an agreement. An investigation of different definitions of weighted reference points for service composition is necessary to verify if Pareto optimality properties can be applied to agreements found when concurrent negotiation is allowed.

5 Simulation Results

Let us consider an AW consisting of 2 ASs and 2 SPs for each AS. Negotiation occurs on two issues (e.g., issue1 can be the service execution time, and issue2 its cost). SPs utility functions are modeled using the well known Cobb–Douglas functions given by:

$$\begin{aligned} u_i(\mathbf x _i,t)= \gamma (x_{i,1}^t)^\alpha (x_{i,2}^t)^\beta \end{aligned}$$

(6)

where, $\alpha$, $\beta$ and $\gamma$ are constant factors, with $\alpha \ge 0$, $\beta \ge 0$, and $\gamma > 0$, that are randomly assigned to each agent (and different for each of them), and $x_{i,j} \ge 0$.

Fig. 2

Negotiation evolution for an AW with 2 ASs, and 4 SPs

In Fig. 2, the evolution of a negotiation execution for the considered experimental setting is shown. In particular, we plotted, for each AS, all SPs issue offers (crosses in the figure) that approach the reference point computed according Definition 3 (empty circles in the figure) for that AS. The best offers selected at each round (filled circles), one for each AS, are used to compute the reference points for the successive round. The negotiation ends successfully with the set of offers respectively sent by $SP_1$ and $SP_3$ converging to the Pareto optimal agreement.

Fig. 3

Offers evolution of the SPs for $AS_3$

Fig. 4

$\bar{\mathbf{r }}_{i}^{t}$ (top) and $\hat{\mathbf{r }}_{i}^{t}$ (bottom) convergence

In Fig. 3, a different negotiation execution is reported for two provider agents of $AS_3$, indicating the reference points computed at each round, the corresponding offers respectively sent by the two agents, and the selected offers at each round. As shown, from round 1 to round 4, the offers sent by $SP_2$ are selected as the most promising ones, while from round 5 to round 10, the offers selected as the most promising ones are those sent by $SP_1$. The negotiation ends with an agreement including the offer sent by $SP_1$ at round 10. The possibility to negotiate at each round with all available providers for a given AS, allowed to achieve a Pareto optimal agreement with an agent that would have been discarded since it was not promising at the beginning of the negotiation. Hence, a reference point computed considering a set of single selected offers at a given round, allows to select a different set of offers at a successive round.

It could happen that an offer for an AS included in a Pareto optimal agreement may be provided by two different SPs, if the indifference curves intersect: in such a case just one of the SPs is randomly selected since the selected agent is not relevant for the Pareto optimality of the agreement.

Finally, in Fig. 4, a complete negotiation execution is shown when reference points are computed respectively according to Definition 4 (see Fig. 4 top) and Definition 5 (see Fig. 4 bottom), starting from the same configuration of SPs and ASs. In the first case, the negotiation does not converge to an agreement in 100 rounds, while in the second case such agreement is reached very quickly. These experiments suggest that when considering weighted reference points they converge to an agreement and, if it exists, it can be found through a weighted orthogonal bidding strategy. Hence, reference points can be concurrently computed.

6 Related Work

As discussed in Sect. 3, negotiation for service composition is a package-deal multi-issue one. While single-issue negotiation is widely studied in literature, multi-issue negotiation is less mature [14]. Typically, multi issue-negotiation approaches can be classified as mediated or not mediated ones. Most of the not mediated approaches rely on bilateral interactions [2]. A variety of searching methods are proposed in literature, as for example, similarity criteria based search [9], or decentralized search [14]. In this paper, we deal with the problem of multi-issue negotiations where the component issue values are provided by multiple agents, and thus a requester agent is negotiating with multiple trading partners. In multi-issue, multi-agent negotiation literature, it is often assumed that there is an unbiased mediator who collects the agents preferences and proposes offers to the trading agents [8, 11, 14, 18]. In this work, the SC agent plays a sort of mediator role. In [14], the authors propose a Pareto optimal mediating protocol where, at each step, the mediator provides a negotiation baseline and the agents propose base offers on this line. In [18], the authors use one-to-many multiple negotiations with a coordinator able to change the strategies of a specific negotiation thread. In [11], the authors proposed a protocol for multi-issue negotiation with not linear utility functions and complex preference spaces. They propose a simulated annealing-based approach as a way to regulate agent decision making, along with the use of a mediator.

In this work, we only focus on trading-off. Trading-off to find optimal solution in bilateral multi-issue negotiation was addressed in [9, 14]. In particular, in [14] an alternating projection strategy was proposed, with reference points evaluated with respect to the last offer of the other agent. In [23] such strategy was extended to the multi-agent case, by evaluating reference points as a mean sum of all the offers at each step. Differently from our case, in [23] an agreement corresponds to a single point in the negotiation space, and weights are the same for all the agents. In [9], the authors used the notion of fuzzy similarity to approximate the preference weights of the negotiation opponent in order to select the most similar offer to the last received offer in a pool of randomly generated trade-off offers. In [8], the authors present a constraint proposal method to generate Pareto-frontier of a multi-issue negotiation corresponding to a given reference point. In practice, the mediator adjusts a hyperplane according to predetermined reference points, until the agents most preferred alternatives on the hyperplane coincide. By choosing reference points on the line connecting the agent global optima, Pareto optimal points are produced, and the mediator’s problem has a solution when the number of issues is either two or any odd number greater than two [13]. In [21], the authors present an automated multi-agent multi-issue negotiation for allocation of unit resources, similar to our case. The proposed bidding strategy requires that at each round the agents make bids in a sequential order in order to compute a reference point for each agent involved in the negotiation. In our approach, reference points are calculated for each set of provider agents providing a specific functionality required in a service composition.

Generally, a buyer gets more desirable negotiation outcomes when it negotiates concurrently with all the sellers in competitive situations in which there are information uncertainty and deadlines [16]. A model of concurrent negotiation was addressed in [2], where agents are allowed to make counter-proposal without having received proposals from all other trading partners. In [16], the multiple negotiation threads still happen in the same negotiation round, as in our case, but the heuristic methods used by the negotiation coordinator strongly depend on history information about trading partners and negotiation environment. In our dynamic market based scenario, past information is not always relevant to drive negotiation.

7 Conclusions

In this work, we discussed the main features that make software agent negotiation a suitable approach to select services depending on their QoS attribute values. As described, when service provision occurs in a competitive market of service providers, the adopted negotiation model has to meet specific requirements to be applied in a service composition problem. Since negotiation occurs among a user requesting an SBA and the providers available to deliver the appropriate service components, usually characterized by multiple QoS attributes, negotiation is a multi-agent and multi-issue one. For this type of negotiation it is more difficult to derive theoretical understanding of its behavior, and more crucially to define when agreements that are Pareto optimal can be found. In this work, we refer to a scenario where a composition of services have to be delivered with QoS value satisfying a user’s request, assuming that for each component service more providers are available on the market, and they may provide the same service with different QoS additive values. In this scenario, we proposed a variation of the orthogonal bidding strategy based on the approach presented in [21], and showed how it allows to find an agreement, if it exists, that is Pareto optimal. Furthermore, the possibility to negotiate at each round with all available providers for each abstract service in the composition, allows to achieve a Pareto optimal agreement with a provider agent that would have been discarded according to the adopted heuristics, since it was not promising at the beginning of the negotiation. Hence, a reference point computed considering a set of selected offers at a given round, allows to select a different set of offers at a successive round.

In addition, by introducing a weighted reference point, we show that it is still possible to find an agreement also in the case the Service Compositor concurrently computes all the reference points for each Abstract Service. This allows to avoid making the length of negotiation depending on the number of the Abstract Services composing the Abstract Workflow, that is the case when computing reference points one at a time. This aspect is important when adopting negotiation for service composition. This is even more crucial when the considered reference scenario for service composition is an open market of services, since the time spent in negotiation may prevent its use in these settings.