Keywords

1 Introduction

Automated negotiation is a process in which a group of agents communicate with each other either directly or indirectly to resolve their differences in the hope of eventually reaching an agreement. The interacting agents negotiate to coordinate their activities and to reach mutually acceptable agreements about the division of labor and resources [1].

For a Grid [2] to efficiently support a variety of applications, a resource management system is central to its operation [3]. Grid resource management [3, 4] involves multiple criteria optimization, and some of these criteria are generally classified into time criteria and cost criteria [5]. Sim [6–9] argued and showed that negotiation agents can play an essential role in realizing the Grid vision because the agents can act flexibly for the Grid resources whose performance changes dynamically. To maintain the good performance of the system, the negotiation agents for Grid resource management should be designed to not only optimize price utility (i.e., cost criteria) but be successful in reaching early agreements (i.e., time criteria) [4, 5]. This is because any delay in making a successful negotiation to acquire all the required Grid resources for Grid applications (i.e., resource consumers) before the deadline for executing a job will be considered as an overhead.

Different resource owners and consumers may have different objectives, polices, and preferences [5, 7]. For example, consumers may have conflicting criteria between acquiring cheaper resources and achieving faster negotiation speed (i.e., response time). The resource owner (respectively, a resource consumer) that prefers cheaper resource alternatives at the expense of having to wait longer is said to be more price optimizing (P-Optimizing), while a speed-Optimizing (S-Optimizing) resource owner (respectively, resource consumer) prefers to obtain a resource more rapidly perhaps by paying a higher price at an earlier round of negotiation than its deadline. Different emphasis on optimizing price and optimizing negotiation speed can be modeled by placing different weights on the two criteria. An exact (or equally distributed) concurrent price and speed optimizing (P-S-Optimizing) agent has equal emphasis on the two criteria. In this work, we use three negotiation modes for both competitive agents: P-Optimizing, S-Optimizing, and P-S-Optimizing negotiation.

The idea of adopting an EDA for coevolving the negotiation strategies of the agents that have different preference criteria such as optimizing price and optimizing negotiation speed was first proposed in [5]. The problem of ineffectiveness in coevolving negotiation strategies for the P-S-Optimizing negotiation is presented in [17]. Furthermore, in [17], one possible solution for resolving the difficulties of a P-S-Optimizing negotiation is suggested by restricting the solution space (which is the EA’s perspective; from the agents’ perspective, the negotiation corresponds to the adoption of a feasible strategy space) using predefined strategy profiles. However, in some cases, the fitness function originally used in [5] and [17] cannot effectively discriminate between the different emphases on the two criteria in the total utility space. To solve this problem, we propose a new fitness function that can better characterize the differences among P-Optimizing, S-Optimizing, and P-S-Optimizing solutions.

The rest of this paper is organized as follows: Section 2 specifies the negotiation model of this work. The coevolutionary framework based on GA and EDA is described in Sect. 3. The problem of coevolving strategies for P-S-Optimizing negotiation and its solution will be presented in Sect. 4. Section 5 presents the experimental results and analyses. Finally, Sect. 6 concludes this work with a summary and suggestions for future work.

2 P-S-Optimizing Negotiation

In a classical bargaining model, the utility function U x of agent x, where x∈{B,S} and \(\hat{x}\) denotes x’s opponent, is defined as follows: Let IP x and RP x be the initial and the reserve prices of x. Let D be the event in which x fails to reach an agreement with its opponent \(\hat{x}\). U x:[IP x ,RP x ]∪D→[0,1] such that U x(D)=0 and U x(P x )>U x(D) for any possible proposal P x ∈[IP x ,RP x ]. If x and \(\hat{x}\) are sensitive to time, let τ x be the deadline of x and \(\tau_{\hat{x}}\) be the deadline of \(\hat{x}\). An agreement price that is acceptable to both B and S lies within the interval [RP S ,RP B ].

In the bargaining model with complete information between B and S, both agents know the opponent’s initial price, reserve price, and deadline. If one of the agents has a significantly longer deadline than its opponent, the agent that has a longer deadline will have sufficient bargaining advantages. In other words, an agent that has the longer deadline will dominate the negotiation. Under these conditions, Sim [10, 11] proved that an agent’s optimal strategy can be computed using its opponent’s deadline and reserve price. It can be stated as the following theorem:

Theorem 1

If agent x’s deadline τ x is significantly longer than its opponent’s deadline \(\tau_{\hat{x}}\) (i.e., \(\tau_{x}\gg \tau_{\hat{x}} )\), agent x achieves its maximal utility when it adopts the strategy \(\lambda_{x} = \log_{\frac{\tau _{\hat{x}}}{\tau _{x}}}( \frac{\mathit{RP}_{\hat{x}} - \mathit{IP}_{x}}{\mathit{RP}_{x} - \mathit{IP}_{x}} )\).

2.1 Utility Functions

The total (aggregated) utility function U x of agent x is composed of two attributes—price and time (i.e., the number of negotiation rounds)—and is defined as follows.

$$ U^{x}( P_{x},T_{x} ) = w_{P} \times U_{P}^{x}( P_{x}) + w_{S} \times U_{S}^{x}( T_{x} )$$
(1)

where P x ∈{0,P C } and T x ∈{0,T C }, and P C and T C is are the price and time at which an agreement is reached. \(U_{P}^{x}(P_{C}) \in [0,1]\) is the price utility of x, and \(U_{S}^{x}(T_{C}) \in [0,1]\) is the speed utility of x. w P and w S are the weighting factors for price and (negotiation) speed, respectively, and w P +w S =1.

The price and speed utilities are given as follows:

(2)
(3)

where \(u_{\min} ^{P}\) is the minimum utility when x receives a deal at its reserve price and \(u_{\min} ^{S}\) is the minimum utility when x receives a deal at its deadline. For the experimental purpose, the values of \(u_{\min} ^{P}\) and \(u_{\min} ^{S}\) are defined as 0.1.

If x does not reach an agreement before its deadline, \(U_{P}^{x} =U_{S}^{x} = 0\), and thus, U x=0. Otherwise, U x(P C ,T C )>0.

2.2 Negotiation Strategies

This work considers the bilateral negotiation between B and S with incomplete information in which both agents do not know each other’s deadline and reserve price. Both B and S are sensitive to time; further, we adopt the time-dependent strategies proposed in [12]. The proposal \(P_{t}^{x}\) of x at time t, 0≤t≤τ x is defined as follows:

$$ P_{t}^{x} = \mathit{IP}_{x} + ( - 1 )^{\alpha} \biggl( \frac{t}{\tau _{x}} \biggr)^{\lambda _{x}}| \mathit{RP}_{x} - \mathit{IP}_{x} |$$
(4)

where α=0 for B and α=1 for S, and 0≤λ x ≤∞.

The time-dependent strategies can be classified into three categories: (i) conservative (conceding slowly, λ x >1), (ii) linear (conceding linearly, λ x =1), and (iii) conciliatory (conceding rapidly, 0<λ x <1) [12, 13].

2.3 Negotiation Protocol

The negotiation between B and S is carried out using Rubinstein’s alternating offers protocol [14]. B and S can conduct the negotiation only at discrete time points (e.g., in this work, S makes an offer at t=0,2,4,6,…, and B makes a counter-offer at t=1,3,5,7,…). The negotiation process ends in both cases: (i) once an offer or a counter-offer is immediately accepted (i.e., an agreement is reached) by the other one or (ii) once the earlier deadline is reached without any agreement. In the latter case, the negotiation process ends in a conflict, and the utility outcome will be zero.

2.4 Objective

For the given different deadlines and different preferences of the cost and time criteria (i.e., different values of w P and w S ), agents will face different opponents with different deadlines and strategies. Under these conditions, the objective of this work is to find an effective strategy λ x that would optimize U x(P x ,T x ). In this work, (evolutionary) learning is based on two asymmetric populations in which each population has its own fitness evaluation. Agents learn effective strategies by interacting with individuals from the other population through random pairing. In the following section, the detailed procedure will be described.

3 Coevolutionary Models for P-S-Optimizing Negotiation

When populations between two or more species interact, each may evolve in response to the characteristics of the other. The natural coevolution refers to the mutual (or inter-dependent) evolution between interacting populations. The survival skills of the natural coevolution by making mutually beneficial arrangements have long inspired scientists to develop coevolutionary algorithms for highly dependent problems in which there are strong interactions between two elements or among several elements.

In the bilateral negotiation problem domain, inter-population based coevolution having two populations is considered. The fitness of each individual of one population depends on each individual of the other population, and hence, an individual’s fitness landscape is not fixed but coupled. Therefore, coevolution is regarded as a type of landscape coupling where adaptive moves by one individual can potentially change the landscape of the other. The interaction between two populations comes from the pairing of strategies of each population, and therefore, a successful pairing mechanism is important. Furthermore, to achieve a better performance, the resulting pairing should make a sufficiently prevailing set in the feasible set. In this work, we use one-to-one random paring because of its simplicity and efficiency.

To coevolve effective strategies under different deadlines and different weights of price and speed preferences, a coevolutionary framework using real-coded GA and EDA is implemented. B and S have each of their populations d B and d S consist of a set of candidate strategies. D B and D S are the mating pool (MP) of B and S, respectively.

The evolution of the strategies of one population affects the strategies of the other population. In the process of coevolving strategies, each individual of the two populations will negotiate with the other through one-to-one random pairing. The fitness value of each individual is determined by its negotiation outcome. The details of the GA and EDA are as follows:

3.1 Encoding Scheme

A binary coding mechanism has drawbacks because of the existence of Hamming cliffs and the lack of computation precision [15, 16]. Therefore, in the GA and EDA, each negotiation strategy of the populations is encoded as a real number. Each individual in a population is mainly represented by the strategy that it has. For the experimental purpose, we consider the range of strategies for λ B and λ S in [0,10].

3.2 Fitness Function

To evaluate each individual of a population, the fitness function f(x) is defined as follows:

$$ f(x) = U^{x}( P_{x},T_{x} ) = w_{P} \times U_{P}^{x}(P_{x} ) + w_{S} \times U_{S}^{x}( T_{x} )$$
(5)

In each generation g, randomly pick one individual from \(D_{g}^{B}\) and randomly pick the corresponding individual from \(D_{g}^{S}\). Each selection procedure is carried out without a replacement. Then, the selected individuals of one population will negotiate with the selected individuals of the other population in a one-to-one manner. The values of the fitness function will be computed using the resulting negotiation outcomes. Finally, if an agent x reaches an agreement with its opponent, \(U_{P}^{x}( P_{x} ) > 0\), \(U_{S}^{x}( T_{x} ) > 0\), and f(x)=U x(P x ,T x )>0. If a negotiation is terminated without an agreement, f(x)=U x(P x ,T x )=0.

3.3 EAs for Coevolution

The characterizations of GA and EDA used in this work are described in Table 1. For more detailed information of the GA and EDA, refer to [17].

Table 1 Characterizations of GA and EDA
Full size table

The coevolution procedure for finding the two types of effective strategies (i.e., λ B and λ S ) from the two populations is described in Algorithm 1. The interaction between the two populations is in the fitness evaluation stage (at lines 3 and 8 in Algorithm 1).

Algorithm 1

EAs (GA and EDA) for coevolving negotiation strategies

figure a

4 Problem of P-S-Optimizing Negotiation and Its Solution

4.1 Problem of P-S-Optimizing Negotiation

The GA and EDA described in the previous section cannot coevolve the appropriate strategies for P-S-Optimizing negotiation because the original fitness function (which is the same as the utility function described in Sect. 3.2) cannot characterize different emphases (i.e., preference levels) on the cost and time criteria for some cases. That is, for the given values of w P and w S , the utility function U x(P x ,T x ) given in Sect. 3.2 cannot appropriately characterize the difference between \(U_{P}^{x}(P_{x})\) and \(U_{T}^{x}(T_{x})\) in some cases. For example, consider the case of the exact P-S-Optimizing negotiation setting (w P ,w S )=(0.5,0.5). The total utility U x(P x ,T x ) of the set \(U_{P}^{x}(P_{x}) = 0.7\) and \(U_{T}^{x}(T_{x}) = 0.3\) (which corresponds to a more P-Optimizing solution) will have the same value for the total utility U x(P x ,T x ) of the set \(U_{P}^{x}(P_{x}) =0.3\) and \(U_{T}^{x}(T_{x}) = 0.7\) (which corresponds to a more S-Optimizing solution). Furthermore, it is the same for the set \(U_{P}^{x}(P_{x}) = 0.5\) and \(U_{T}^{x}(T_{x}) = 0.5\) (which corresponds to the exact P-S-Optimizing solution). The above example shows that in some cases, the original fitness function cannot characterize the difference between P-Optimizing, S-Optimizing, and P-S-Optimizing solutions.

4.2 Proposed Fitness Function

The ambiguity of the original fitness function in the total utility space is solved by adopting the proportion of weighting factors (which represent the preference levels in the total utility space) in the calculation of the proposed fitness function. The key idea of the proposed utility function is to directly measure the difference (or similarity) between (i) the ratio of price and time weighting factors, and (ii) the corresponding ratio of the price and time utility functions. As the difference between them decreases, the value of the fitness function will be considerably high. The proposed fitness function is designed as follows:

5 Empirical Evaluation

A series of experiments was carried out to evaluate the performance of the original fitness function (in Sect. 3.2) and the proposed fitness function (in Sect. 4.2).

5.1 Experimental Settings

An empirical comparison of GA and EDA is also presented to determine which model is more suitable for coevolving negotiation strategies with different preference criteria for optimizing price and speed. The experimental parameter settings are as in Table 2.

Table 2 Parameter settings for EAs and negotiation
Full size table

For the purpose of the experiments, both competitive agents have the same weights of the preference criteria for the three negotiation modes. The settings for each negotiation mode are as follows: (w P ,w S )=(1.0,0.0) for P-Optimizing negotiation, (w P ,w S )=(0.1,0.9) for S-Optimizing negotiation, and (w P ,w S )=(0.5,0.5) for P-S-Optimizing negotiation.

5.2 Optimal Conditions

In the case of the P-Optimizing negotiation, we will experimentally prove the properness by examining two extreme cases: Case I and Case II.

Case I

If an agent B has a sufficient bargaining advantage over S(i.e., τ B ≫τ S ), B will dominate the negotiation irrespective of whether S adopts any strategies. The optimal negotiation strategy of B will be determined by Theorem 1. For example, under the negotiation parameter settings described in Table 1, the optimal strategy of B is when λ B =3, and the agreement is reached at P C =15 and T C =50. The strategy of S and λ S will not converge to a specific value, and thus, it will have a dynamic range of values. We describe this dynamic range as [Min. value, Max. value].

Case II

When both B and S do not have any bargaining advantage (i.e., τ B =τ S ), we can think that the agreement of the negotiation with the abovementioned negotiation parameters should be reached at a Pareto optimal point (i.e., P C =50). However, in a practical negotiation model, the point does not always follow the Pareto optimal point since the agent that proposes the first negotiation proposal (in our experiment S does) usually gets a lower payoff (or utility) in the alternating offers protocol. Under the Pareto optimal condition, the optimum strategies are when both λ B and λ S equal λ max =10 (i.e., both B and S do not concede at all).

In the case of S-Optimizing and P-S-Optimizing negotiations, there is no such theory as that in the case of P-Optimizing negotiation to prove the optimality of the solutions. However, the evaluation can be carried out by examining whether the solutions follow the general characteristics for the given negotiation mode. For example, in the case of the S-Optimizing negotiation, the agreement should be reached at an earlier negotiation time (than its deadline) by paying a relatively high price. The abovementioned two extreme cases are also used for evaluating the optimality of the solutions. Interestingly, according to Proposition 7 given in [13], irrespective of the deadline, agents with linear strategies are more likely to make deals than those with conservative strategies while achieving higher utility than those with conciliatory strategies. Hence, linear strategies (i.e., λ B =1.0 and λ S =1.0) are optimal solutions for the exact P-S-optimizing negotiation.

5.3 Experimental Results

The results of these two extreme cases for the original utility function and the proposed utility function are shown in Tables 3–6.

Table 3 Results obtained using original fitness function for Case I
Full size table

5.3.1 Results Obtained Using Original Fitness Function

The results are listed in Tables 3 and 4. The original fitness function in Eq. (5) is the same as the total utility function in Eq. (1).

Table 4 Results obtained using original fitness function for Case II
Full size table

Observation 1

Both GA and EDA with the fitness function in Eq. (5) find good strategies for P-Optimizing and S-Optimizing negotiation, respectively.

Analysis

In both Case I (in Table 3) and Case II (in Table 4), λ B and λ S has close to optimum solutions, as discussed in Sect. 5.1.

Observation 2

Both GA and EDA with the fitness function in Eq. (5) cannot find effective candidate solutions for the P-S-Optimizing negotiation.

Analysis

In both Case I (in Table 3) and Case II (in Table 4), λ B and λ S did not converge to the values that we expected (Similarly, by using the EDA proposed in [5], we found that λ B and λ S did not converge in the case of P-S-Optimization). This is because more conceding strategies will be cut off as the evolution proceeds since these strategies will get a lower payoff than the other strategies (i.e., linear or conservative strategies) eventually. Hence, λ B and λ S of both GA and EDA tend to be more P-Optimizing.

5.3.2 Results Obtained Using Proposed Fitness Function

The results are listed in Tables 5 and 6. The proposed fitness function does not equal the utility function any longer. The proposed fitness function measures the similarity between the ratio of weighting factors and the ratio of price and speed utilities. For example, for the P-Optimizing negotiation (i.e., (w P ,w S )=(1.0,0.0)), and in Case I (i.e., B has significant bargaining advantage than S), the optimum utilities are obtained at (P C ,T C )=(15,50). For \(B, U_{P}^{B}( P_{C} ) = 0.8875\) and \(U_{S}^{B}( T_{C} ) = 0.55\). Hence, the optimum value of the proposed fitness function is \(f_{\mathit{opt}}^{B}(x) =1 - \big| \frac{w_{S}}{w_{P}} - \frac{U_{S}^{x}( T_{C} )}{U_{P}^{x}( P_{C})} \big| = 1 - \big| \frac{0.0}{1.0} - \frac{0.55}{0.8875} \big| = 0.3803\). For S, \(U_{P}^{B}( P_{C} ) = 0.1\) and \(U_{S}^{B}( T_{C} ) = 0.1\). Hence, the optimum value of the proposed fitness function is \(f_{\mathit{opt}}^{S}(x) = 1 - \big| \frac{w_{S}}{w_{P}} - \frac{U_{S}^{x}( T_{C})}{U_{P}^{x}( P_{C} )} \big| = 1 - \big| \frac{0.0}{1.0} - \frac{0.1}{0.1} \big | =0.0\). Likewise, for different preference criteria and negotiation parameter settings, different optimum (i.e., maximum) values of the fitness function will be drawn from the proposed fitness function (e.g., for the above example, the maximum value \(f_{\mathit{opt}}^{B}(x)\) for B is 0.3803). More analyses and experiments related to this issue will be presented in our future paper.

Table 5 Results obtained using proposed fitness function for Case I
Full size table
Table 6 Results obtained using proposed fitness function for Case II
Full size table

Observation 3

Both GA and EDA with the proposed fitness function find effective strategies for the P-Optimizing negotiation.

Analysis

The results show that both GA and EDA using the new fitness function achieved good performance. In Case I (in Table 5), λ B converges close to the values of the optimum solutions. Furthermore, in Case II (in Table 6), λ B and λ S converge close to the values of the optimum solutions.

Observation 4

In Case I, the GA with the proposed fitness function finds effective candidate solutions for the S-Optimizing negotiation. However, the EDA cannot coevolve S-Optimizing strategies. In Case II, both GA and EDA can coevolve effective S-Optimizing strategies.

Analysis

In Case I (in Table 5), the GA can get more conceding strategies that can reach early agreements. However, the EDA cannot find solutions at all. This result shows that the EDA does not have a sufficient search capability to find solutions for the S-Optimizing negotiation. In Case II (in Table 6), both GA and EDA can find effective strategies that are considerably more conceding strategies than linear strategies (i.e., λ B =0.1561 and λ B =0.0026 for the GA, and λ B =0.2595 and λ B =0.0090 for the EDA).

Observation 5

In Case I, both GA and EDA with the proposed fitness function find effective candidate solutions for the P-S-Optimizing negotiation. The EDA has better performance than the GA in terms of the evolution speed. In Case II, both GA and EDA can coevolve effective P-S-Optimizing strategies.

Analysis

In Case I (in Table 5), the GA needs considerably more generations to converge to solutions than the EDA (i.e., 2059.01 generations for the GA, and 59.03 generations for the EDA). This result shows that the EDA has better performance with respect to coevolving effective P-S-Optimizing strategies in terms of the evolution speed (i.e., the number of generations required for the coevolution). In Case II (in Table 6), both GA and EDA can coevolve effective P-S-Optimizing strategies that are close to the value of the linear strategy (i.e., λ B =0.9519 and λ B =1 for the GA, and λ B =0.9508 and λ B =1 for the EDA).

6 Conclusions and Future Work

This paper provides empirical evidence for coevolving negotiation strategies for the negotiation between the two competitive agents having different preference criteria for optimizing price and negotiation speed. Two rather different evolutionary approaches, EDA and GA, were respectively used and compared for coevolving the strategies. The experimental results (given in Tables 3 and 4) showed that adopting the GA and EDA were a good choice for coevolving effective strategies for the P-Optimizing and the S-Optimizing negotiations. However, we found that both GA and EDA did not converge to proper solutions (that we expected in Sect. 5.1) in the case of the P-S-Optimizing negotiation. The main problem of the failure in coevolving the strategies was that the original fitness function (given in [5] and [17]) could not effectively characterize the different weights on the cost and time preference criteria in the total utility space. On the basis of the analysis, we proposed the new utility function in Sect. 4.2. The experimental results (given in Tables 5 and 6) showed that the proposed method achieved more reliable results in the case of the P-S-Optimizing negotiation than the method used in [5] and [17]. However, the results also showed that the EDA using the new fitness function did not coevolve effective strategies for the S-Optimizing negotiation, and the GA using the new fitness function was not effective in the case of the P-S-Optimizing negotiation since it required considerably more generations than EDA. To develop more reliable models that are successful and efficient in all cases, a hybrid model [20] can be adopted to compensate for the defects of each evolutionary approach by combining the GA and the EDA.

Our future work includes an exhaustive analysis that considers (i) more combinations of different preference weights between the cost and the time criteria (e.g., more P-Optimizing such as (w P ,w S )=(0.7,0.3) and more S-Optimizing such as (w P ,w S )=(0.3,0.7) cases) and (ii) heterogeneous negotiation (e.g., the case when one agent is P-Optimizing, while the other agent is S-Optimizing, and all these types of cases). Furthermore, by reducing and focusing on the feasible solution space, the restriction scheme of the solution space in [17] can help to reduce the computational overhead and to obtain more high-quality solutions.