A composite greedy seller strategy in decentralized many-to-many negotiation

Abstract

In the automated many-to-many negotiation model for leasing resource contract under Cloud computing environment, the main concern will be over finding a good approximation approach to this type of negotiation problem, since an optimal solution to that problem would be intractable due to the inherent complexity of the leasing resource negotiation along with the Cloud’s specifications. In order to get that good approximation, decentralized negotiation, leveled commitment contracts as well as lightweight agent strategies had been proposed, resulting to a fast and well-approximate negotiation decisions. To this end, we had conceived a “composite-greedy” algorithm for the seller’s strategy to address a variant of WDP which is the seller’s main problem under such settings. The composite greedy seller strategy will be a two-step strategy: the first one applies a classification according to the offers’ revenue and the second one according to the offers’ densities, and thereafter the seller will pick the one that maximizes the most his expected utility. Experimental results show the effectiveness of our approach compared to some related ones over different performance measures.

Keywords

Decentralized many-to-many negotiation winner determination problem combinatorial auctions seller strategy multi-agent systems

1. Introduction

Cloud computing allows the consumer to customize the machine’s specifications as well as the usage time with respect to its task’s requirements. Cloud computing achieves this by relying on the virtualization technology that allows to separate a physical computing device into one or more virtual devices. Deploying Cloud computing as an enterprise solution had been motivated by the fact that there is no need of upfront costs which hasn’t been the case previously with traditional infrastructure where premises, machineries and their maintainability requirements had to be satisfied upfront before projecting the deployment of any plan.

Marketing resources under cloud computing environments is characterized by three difficulties: First, a huge number of market’s participants (buyers and sellers). Second, a transaction’s complex structure due to the inherent complexity of the leasing contract, and finally, a non-stop (continuous) auction had to be implemented in such environments where the resources could be requested anytime and anywhere in order to comply to the Cloud’s standards. In such cases, conceiving optimized strategies for either the buyer or the seller will turn out to be computationally intractable since many factors (such as market dynamics, multiple contracting opportunities) are inter-dependent as well as problems of trustworthiness from market’s participants might arise over the integrity of the controlling agent since they are assumed to be self-interested and rational. For that reason, some good approximations had been proposed by Bo An et al. [3], in which the authors had incorporated leveled-commitment contract in the negotiation protocol which makes it possible to take away the controlling agent (auctioneer), allowing for agents to make fast and local negotiation decisions which had been turned out to be a good approximation.

In our previous work [11], our main concern was on implementing a buyer strategy in a many-to-many negotiation that has to do better than other related strategies while using an existing seller strategy [3]. However, in this paper, our objective will be to implement a seller strategy in a many-to-many negotiation that has a better trade-off on the performance measures than other related strategies while using an existing buyer strategy [3]. Thus, the objective of our current research is to deal with issues that the sellers had to be confronted. In this regard, the seller will face a series of a so-called “special winner determination problem” (SWDP) – a variant of WDP – which we have named so, due to the fact that the decisions might not be definite, resulting to a third outcome in addition to the two traditional ones found in WDP, i.e. success or reject, which is pending. That latter outcome “pending” had been conceived when solving SWDP for the simple reason that each contract is not definite and the contract’s parties could renege their commitments on it, as long as its delivery time had not yet been reached. In fact, the intervening time between the contract’s submission time and its delivery time is the allowable time for both contract’s parties if they want to disengage from their commitments. So, as soon as the contract’s delivery time was reached, the contract will be sealed and becomes like the contracts dealt with in standard WDP, for which both contract’s parties (seller and buyer) haven’t the right to disengage from their commitment and instead have to respect it. Moreover, the difference between SWDP and a standard WDP comes from the fact that in SWDP, the contracts might have different submission times. This is explained by the fact that offers with an earlier submission time have been previously passed with success some past SWDP’s that had allow them to compete with new coming offers on the recent SWDP’s and have to keep repeating that process until their corresponding delivery time had been reached in order to see their status switching from “pending” into a “success” status.

The event that triggers the SWDP procedure will be the reception of a new offer, as it is supposed that the seller is not allowed to negotiate beyond what his capacities could afford, which makes sense since the seller must check whether or not he could satisfy this new offer in addition to those already contracted. It is then a continuous auction held by each seller on his own resources, where each offer might pass with success many seller’s SWDP’s before being definitely accepted. Since SWDP will be processed as much as new incoming offers would be received by the seller, the need of implementing a lightweight strategy that must be very efficient in terms of responsiveness for the seller under Cloud computing environment is then required. In this paper a “composite-greedy” seller approach had been conceived, whose complexity is $O (n)$ , where n is the number of bids, since our approach is composed of two greedy approaches having both a time complexity of $O (n)$ . Thus, our approach processes each SWDP with two greedy classifications before generating any corresponding negotiation decisions: one that relies on the offer’s bidding price as it is in [3], and the other on the offer’s densities which consists of the ratio bidding price/resource demanded. The second greedy approach based on offer’s density has been inspired from S. Zaman et al. [29] where they applied the offer’s density classification on a combinatorial auction context. Afterwards, the seller will pick the best classification that maximizes the most his expected utility. The chosen classification will generate its proper negotiation decisions that have to be followed by the seller.

The automated decentralized many-to-many negotiation is also motivated from real-world applications, such as CLASP [4] which is a middleware assuring the communication within large-scale distributed systems, in which each autonomous system might require the execution of some plans that sometimes exceed its local resources. This will arise the need of outsourcing some of the system’s computation tasks to other systems disposing of some idle resources, creating by the way a win-win situation among the systems belonging to the same virtual organization. In the other hand, the existent commercially fixed price-schemes such as Amazon EC2 spot instances [2] have their own drawbacks. First they are not economically efficient [27] in the sense that the buyer with the highest bid isn’t guaranteed to get the requested resources since those approaches are based on first come first served principle and secondly, fixed prices schemes do not necessarily reflect the equilibrium prices that arise from the market supply and demand and the only advantage that characterize them are only their running time performances.

The reminder of this paper is organized as follows. In Section 2, we survey different combinatorial auctions as well as decentralized negotiation models. In Section 3 we make an overview description of the leveled-commitment contract as well as its format employed in the distributed negotiation. We detail the buyer and proposed seller strategy in Sections 4 and 5 respectively. Finally, Section 6 empirically evaluates the efficiency of the proposed “composite-greedy” strategy, while Section 7 concludes.

2. Related work

Since the proposed seller approach is a part of a many-to-many negotiation model under cloud computing environment, we will first be interested in some economic aspects of the cloud. Chun et al. [5] have analyzed the optimal choice from a provider’s standpoint with respect of two pricing schemes: subscription and pay-per-use pricing models. Mazhelis et al. [15] introduced an analytical model of hybrid cloud costs which helps to identify a cost-efficient division of the computing capacity between the private and the public portion of a hybrid cloud. This will help to achieve both increased utilization rate of the in-house infrastructure and limited use of the more expensive public cloud. Yehuda et al. [1] analyzed the pricing of Amazon EC2 and claimed that it is not market-driven, but rather is generated at random from within a tight price interval via a dynamic hidden reserve price.

Distributed (decentralized) negotiation approaches are considered as approximate approaches for the type of negotiation problem we are dealt with. They have been associated with multi-threaded negotiations, that is, the buyer runs concurrent negotiations for the aim to better explore the search space of bids and secure good deals. Many-to-Many negotiations are more efficient in combination with the leveled-commitment contract [23], as the buyer might receive new offers which are more interesting than previous contracted ones. The fact that the seller/buyer could disengage from any contract which forces the other participant to re-bid again, will eventually cause a huge number of offers to be generated in the marketplace system. The more new offers will be generated, the more SWDP’s must be run, which forces the seller to be very computationally and timely efficient to deal with the huge number of offers that might be received. This logically requires lightweight strategies, like greedy ones inside the seller’s reasoning in order to not cause any side effect, like latency in the market system. Among decentralized negotiations, there is the approach of B. An et al. [3] which have implemented a myopic seller strategy, in a decentralized many-to-many negotiation context under the Cloud computing environment. That sort of strategy accepts an offer if and only if some immediate payoff could be earned by accepting it without accounting for its current decisions on the future utilities. The offer classification algorithm of that strategy will consist of evaluating offers sorted in a decreasing way according to their revenues while respecting the constraint of not making agreements beyond what the seller’s capacity allows for. Lai et al. [13] have proposed a decentralized model with an alternating-offer protocol for dealing with multi-attribute negotiation, where the responding and proposing agents have to find out the best offers that benefit them both using indifference curve.

Concerning combinatorial auctions, the seller will not take decisions concerning which buyer will be assigned what proportions of his resources like in automated negotiation, but instead he will delegate it to a central entity called the auctioneer, which will be responsible on all the resource allocation decisions of the auction. Among the approaches belonging to the combinatorial auctions, S. Zaman et al. [29] have proposed two one-to-many (one seller and many buyers) Combinatorial Auction-Based Allocation mechanisms for the cloud computing to solve the virtual machine allocation problem (VMAP) in which the auctioneer works on behalf of the seller. The first one consisting of maximizing the seller revenue through a linear programming approach which is characterized by a prohibitively running time; The second one is a greedy approach consisting of classifying in a decreasing way each offer not according to their revenues as in [3], but to their densities. However the extent of expressiveness in the mechanism proposed by S. Zaman et al. [29] is slightly reduced as the buyers can’t express directly the usage time of their required resources in their bid formulations. Indeed, as the auction consists of a continuous series of rounds for which each round run by the auctioneer will allow the beneficiaries of just using one unit of time of the acquired resources, the bidder has to participate and win as much of combinatorial auction rounds as needed to finish off his task. Hence, this type of auction is not suitable for non-fault tolerant tasks as they generate to the buyer negative utility in case of failure for winning consecutively the auction rounds needed. Sandholm [21] used the technique of pruning the search tree to devise approximate algorithms for the computationally hard WDP. Penya et al. [20] proposed a model based on simultaneous reverse combinatorial auctions for electricity retail where customers choose their supplier from competing electricity retailers. Naoki Fukuta and Takayuki Ito [7] have proposed an algorithm that runs an auction while conforming the constraint of not loosing the allocation efficiency. Wu et al. [28] have proposed to first recast the WDP problem into the maximum weight clique problem (MWCP) and solving the transformed problem with a recent heuristic dedicated to the MWCP. This had produced performances that competes very favorably with the powerful CPLEX solver. Sghir et al. [24] have proposed a dedicated tabu search algorithm (TSX_WDP) for the WDP. Other approaches [19,25] rely on genetic-based algorithms to solve WDP in combinatorial reverse auctions. Mito et al. [16] propose three heuristic bid ordering schemes for solving WDP; the first two schemes take into account the number of goods shared by conflicting bids and the third one is based on a recursive application of such local heuristic functions. They have been proved to be scalable compared with the conventional linear programming (LP) relaxation based schemes and could quickly provide an optimum solution under optimization schemes such as the branch-and-bound method. Sandholm [22] have proposed a sophisticated search algorithm for the problem of combinatorial auction. It uses decomposition techniques, upper and lower bounding (also across components), elaborate and dynamically chosen bid ordering heuristics, and a host of structural observations. Garg et al. [8] designed a double auction-based meta-scheduler for grids that takes inspiration from auction principles in allocating resources to parallel applications with competing QoS demands, which has been proven to perform much better than classical scheduling mechanisms in similar working conditions. Finally, many-to-many double-sided combinatorial auction mechanisms [6,26] will not be helpful for solving our problem as the resource allocation decisions will consist of a matchmaking process between the entire bids and asks of all the market participants. Thus such approaches aren’t decentralizable to take advantage of them.

Finally, seller strategy could send information that might be helpful to the buyer besides the standard contract’s terms. Sellers could be classified by the extent of their willingness to sell their resources as Nguyen et al. [17,18] have argued that the sellers’ strategies aren’t always likely to be similar. They argue that some of the sellers might be desperately searching for an agreement which are called conceders, whereas others adopt a tough stance which are called non-conceders. Such information may be based on past experiences, obtained from a trusted third party, or from a system of referrals [14]. Another way to get know more about the seller is by letting him sending off counter-offers or at a further degree arguing its rejection regarding the buyer’s offer, so that the buyer could make proper decisions at subsequent negotiation rounds [12]. Goyal et al. [10] had presented a fuzzy attitude-based bidding strategy which employs a dual assessment, i.e. the assessment of the attributes of the goods as well as the eagerness of the agent to procure the good. This assessment will then be used for bidding in the auction.

3. Leveled commitment contract

In this section, we will talk about the offer’s submission format as well as its possible stages that go through under the leveled-commitment negotiation protocol.

3.1. Submission offer format

Each offer should comply with the leasing contract information requirements that include among other: the leasing period which will be called in this paper the usage time for the required resources $pd$ , the decommitment penalty $pe$ , the offer’s earliest start time $est$ by which the buyer would not accept any provisioning resources by the seller before that time and $dl$ for which he would not accept any provisioning resources by the seller after that time.

More formally, the offer format will be presented to the seller as follows: $⟨ pr, pe, R, est, pd, dl ⟩$ where $pr$ stands for the contract’s proposing price and $R$ for the contract’s demanded resources along with their corresponding quantities.

3.2. Bid’s stages in leveled commitment negotiation

Before describing the seller and buyer strategy that deal with leveled-commitment contracts, we will give an overview of how that concept is integrated in the negotiation protocol. On the whole, leveled-commitment contracts, unlike full-commitment contracts for which neither parties of the contract could break it up, allows the contractor to be freed from the contract [23]. The disengagement of the contract will incur either no cost or a penalty depending on the offer’s stage which will be shown in Fig. 1.

Fig. 1.

Finite state machine of the bid’s stages [3].

Figure 1 shows the three different stages that the bid goes across where each stage symbolizes the extent of commitment each participant is committed for. First, the “buyer reasoning” is the initial state where the offer is about to be formulated by the buyer and sent it to the seller. Then, it will be processed by the “seller reasoning” component of the seller that accepts offers exceeding his reserve price, turning them into tentative agreements, otherwise rejecting them along with the acceptable quotes in order to be kept for further consideration. In the “tentative contract” state of Fig. 1, the buyer has the possibility to confirm the agreement turning it into a final agreement or cancelling that agreement by either contract’s parties if one of them want to renege his commitment on it. In case the contract had become final, the disengagement of the contract will come along with a penalty fee for the party who wants to renege its commitment, otherwise the decommitment will come at no cost.

Note that, any disengagement from a participant must occur before the contract takes effect. Put differently, the disengagement, if there was one, must happen before the delivery time that was mentioned in the contract has been reached. After that time, the contract takes effect and becomes what we call “definite final agreement”.

4. Buyer strategy

Since the buyer will negotiate with sellers his required resources through leveled-commitment contracts, he has to cope with the uncertainty of seeing the seller disengaging a contract linked with him in case where he receives a one with higher revenue. For this reason, the buyer will use redundant resources [3] to cope with such an uncertainty by negotiating over two sets of resources, each of which should satisfy all his required resources. Which means that in case where one set of resources has been diminished and doesn’t include all the resources required due to some disengagements from the sellers, the buyer could still resort to his second set of resources to start his task τ. However, even if increasing the number of redandunt resources will increase the probability of success for the buyer to start his task, this will have as a side effect to increase the expenses of penalties fees the buyer has to make since more disengagement of contracts for duplicate resources are needed to handle such a situation.

Before digging further into the buyer strategy, Table 1 lists the symbols and their definitions which are used in the subsequent formulas and the pseudo-algorithm.

Table 1
Used symbols for Buyer strategy

t The current time

$vt$ The next time in which the buyer will execute its strategy

o Represents a simple offer

$T o$ Represents a tentative agreement offer

$F o$ Represents a final agreement offer

${TA}_{b}$ Represents the tentative agreement set

$A_{b}$ Represents the final agreement set

$tg (b)$ Represents the task generation time

$est (b)$ Represents the earliest start time to start the task τ

$dl (b)$ Represents the deadline for starting the task τ

$R_{s}$ Represents the seller’s resources available for sell

$R_{b}$ Represents all the resources required by the buyer b

${CR}_{b}$ Represents the current demanded resources of the buyer

$step$ Represents the time of the negotiation round (step)

${iter}_{i}$ Represents the ith iteration time

$ψ (r)$ Represents the demand/supply ratio for the resource r

$υ_{b} (t)$ The utility generated when b executes τ. This utility gets its highest value at $est (b)$ and decreases linearly as the time of execution gets away from it

$q (R_{b}, r)$ Stands for the quantity of units r the buyer needs

$c_{b} (r)$ Stands for the unit cost of resource r

In terms of the disposition of the time axis of the buyer, this will mainly be divided in iterations which in turns are consisting of multiple negotiation rounds as showed in Fig. 2.

Fig. 2.

Disposition of the time axis.

As depicted in the Fig. 2, the buyer will generate a task τ at a time $tg (b)$ , then he will set dynamically new iterations as long as the task hasn’t yet started. In fact, after the buyer has set an iteration which consists of multiple rounds of negotiation, he will verify, each time the current time t equals the iteration time whether or not he has satisfied all his required resources by means of final agreements. If it is the case, the task will start and no longer iterations will be set afterwards. On the other hand, if he fails, he should set a next iteration time and should negotiate his contracts with the provisioning time set at that next iteration time. In the Fig. 2, there was up to 5 iterations for the buyer in order to negotiate all his required resources.

Concerning his offering price, the buyer will apply different formulas for different types of offers [3] which play an important role about their provisioning time restrictions:

The partial agreement: In case where the seller could satisfy a portion of the buyer’s demand, a partial agreement could be made. Since the buyer has to make at least two partial agreements that complement each other in order to satisfy his requirement of resources, a synchronization on their provisioning times is required for the sake of getting provisioned with all the resources at the same time. That common time among the partial agreements is called $estp$ , that stands for “earliest start time for partial agreements”. Moreover, the $dlp$ “deadline for partial agreements” must be equal to $estp$ in order to let no time frame to all the sellers than a point of time in order to provision their contracts’ resources. The pricing for a partial agreement containing $R$ resources where $R \subset R_{b}$ is defined as: $\begin{array}{rcl} pr (R, {iter}_{i}, dl, t) \\ (1) & = \sum_{r \in R} q (R, r) pd (b) pr (r, {iter}_{i}, dl, t) \\ pr (r, {iter}_{i}, dl, t) \\ = c_{b} (r) \\ (2) & + \frac{(pr (R_{b}, {iter}_{i}, dl, t) - c (R_{b})) ψ (r) c_{b} (r)}{pd (b) \sum_{r \in R_{b}} ψ (r) c_{b} (r) q (R_{b}, r)} \\ (3) & c (R_{b}) = \sum_{r \in R_{b}} c_{b} (r) pd (b) \end{array}$

The full agreement: is an agreement that satisfies all the needs of the buyer. No synchronization is then needed with other offers as that offer in itself is independent. The buyer will negotiate such agreement, by offering to the seller the discretion for the provisioning time within the interval $[est, dl]$ . Formally, the offering price for all required resources $R_{b}$ is defined as:

\begin{array}{l} pr (R_{b}, {iter}_{i}, dl, t) \\ = c (R_{b}) + (RP ({iter}_{i}, dl (b)) - c (R_{b})) \\ (4) & \times (\frac{t - tg (b)}{dl (b) - tg (b)}) \\ RP ({iter}_{i}, dl) \\ (5) & = \{\begin{matrix} \frac{\int_{{iter}_{i}}^{dl (b)} υ_{b} (t^{'}) d t^{'}}{dl (b) - dl (ρ_{i})} & if dl (b) \neq {iter}_{i} \\ υ_{b} ({iter}_{i}) & otherwise \end{matrix} \end{array}

Finally, we end this section by giving a buyer pseudo-algorithm (Algorithm 1) inspired from [3] which describes the main strategy of this latter.

Algorithm 1

Negotiation strategy of the buyer

The main points of the main loop of the buyer pseudo-algorithm are:

In the first foreach loop, the buyer has to negotiate only with sellers that are not bounded by a contract with him.

In the body of that first loop, the offer must be the intersection between the buyer’s current demanded resources and the seller’s resources in order to make contracts’ resources complementing each other.

Each time the current time reaches the iteration time, i.e., ( $t = estp$ ), the buyer has to verify whether he could start the task τ. If he fails, he has to update his $estp$ to the next iteration time. The same principle applies when ( $t = T_{bk}$ ), except that the buyer couldn’t start his task if he has successfully gathered all his resources at that time.

At the end of the while loop, the buyer will loop through each of contract in the tentative agreement set and confirm all those which strictly complement the final agreement set, i.e. $A_{b} \cap T o = \emptyset$ .

5. Proposed seller strategy

Before digging into the seller strategy which our contribution lies in, Table 2 lists the symbols and their definitions which are used in the subsequent formulas and pseudo-algorithms. Then in the last two subsections, we will talk about the rationale for integrating the two greedy algorithms in our proposed seller strategy, one based on the offers’ revenues and the other on the offers’ densities.

Table 2
Used symbols for seller strategy

t The current time

${DA}_{s}$ The set of the seller s’s definite final agreements

$A_{s}$ The set of the seller s’s final agreements

${TA}_{s}$ The set of the seller s’s tentative agreements

The new coming offer that triggers WDPS

$R_{s}$ The set of s’s seller resources available for sale

$pd (o)$ The resource usage time required by the contract o

$q (r)$ The quantity demanded for the resource r

$c_{s} (r)$ The seller’s cost for the resource r

$ϕ (o)$ The seller’s reserve price for the resources demanded in the offer o

$ψ (r)$ The ratio demand/supply of the resource r

$R (o)$ The set of resources demanded by the offer o

$pr (o)$ The offering price of the offer o

$cost (o)$ The seller’s cost for the offer o

$pe (o)$ The offer o’s decommitment penalty

$v (o)$ The offer o’s value with respect to a specific seller’s offer classification

$stage (o)$ The offer o’s current stage

$rwdps (o)$ The offer o’s outcome with respect to the latest WDPS

$bidder (o)$ The identity of the bidder who submitted the offer o

In this paper, our main concern is on designing a seller strategy that has to perform the best in the evaluation part. Basically, the process of offers reordering to solve WDPS will be triggered each time the seller receives a new incoming offer that must exceed the seller’s reserve price $ϕ (o)$ [3] defined as follows: $\begin{matrix} (6) & ϕ (o) = \sum_{r \in R (o)} q (r) c_{s} (r) (1 + ψ (r)) pd (o) \end{matrix}$

Each time the seller proceeds to classify his offers according to a given classification for the purpose of resolving the WDPS, he will do it two times in a greedy way. Greedy classifications will consider first the offers that are best ranked according to the classification’s specifications since they have the highest values, making the highest ranked offers being served first than the lowest ones when the offers are bidding on the same resources. Indeed, if an offer had been rejected, it doesn’t mean that all subsequent lower ranked offers must be so, as their demands might differ on the resource types and quantities required from that rejected offer, which might let them being accepted by the seller.

In Algorithm 2 the main seller strategy will be presented. It gives the overview of the main activities undertaken by the seller during his negotiation, and it will be followed by Algorithm 3 that describes what directives have to be followed by the seller after solving a WDPS.

Algorithm 2

Seller strategy

Algorithm 3

Instead of describing the underlying procedure of under a pseudo-algorithm format, we have chosen to describe it through a textual description and by using equations (7), (8) and (9).

5.1. The WDPS resolution process

As mentioned in the Algorithm 2, the process takes four parameters, namely: the first one $R_{s}$ is the available resources that could be traded by the seller, as the seller has as a constraint to not exceed his capacity when trading his resources. Put differently, the seller has to satisfy all the accepted offers from ${DA}_{s}$ , $A_{s}$ , ${TA}_{s}$ and after running the WDPS. The second and third parameters $A_{s}$ and ${TA}_{s}$ are the offers still under the seller consideration that had at least passed previously one WDPS, and finally the fourth one is a new coming offer that had triggered that WDPS to be executed by the seller.

The WDPS strategy undertaken by the seller consists of a two-step classification, where each step is of greedy type: the first one is nothing than Bo An et al. [3] classification, where the offers will be classified and valued in a decreasing way according to their respective revenues. More formally, each offer’s value is computed according to that classification as follows: $\begin{matrix} (7) & v (o) = \{\begin{matrix} pr (o) - cost (o) + pe (o) \\ if o \in A_{s}, \\ pr (o) - cost (o) \\ Otherwise . \end{matrix} \end{matrix}$ Where “Otherwise” refers to the simple offer or one of the tentative agreements ${TA}_{s}$ . In the equation (7), final agreements had been advantaged over non-final agreements by adding the penalty decommitment to their valuations. This is because, a buyer disengagement from a final agreement will cause the seller to be compensated by a penalty unlike the other agreement stages, for which the buyer might disengage them for free.

After evaluating the first classification, the seller will evaluate the second greedy classification that consists of valuing each offer according to their densities. The offer’s density is determined by the ratio of offering price/resources demanded. The seller will loop over those offers beginning from the highest values and ending to the lowest ones, in a greedy fashion in his way of allocating the resources. The formulas of computing the valuation of each offer under that classification are as follow: $\begin{matrix} (8) & v (o) = \{\begin{matrix} \frac{pr (o) - cost (o) + pe (o)}{\sqrt{\sum_{i = 1}^{n} c_{s} (r_{i}) * q (r_{i})}} & if o \in A_{s}, \\ \frac{pr (o) - cost (o)}{\sqrt{\sum_{i = 1}^{n} c_{s} (r_{i}) * q (r_{i})}} & Otherwise . \end{matrix} \end{matrix}$ Where n is the number of resource types demanded in the offer o.

After investigating the two classifications cited previously, the seller will pick the one that generates the highest expected utility defined as follows:

The chosen classification that the seller has adopted thereafter will generate its corresponding directives that the seller has to follow. Those directives are described in the pseudo-algorithm 3. In summary, the classification’s directives told the seller to keep the offers which are passed the WDPS with success for later consideration and the others must be disengaged according to their corresponding stages.

5.2. Greedy classification based on offer’s density

In this subsection, a typical scenario will be shown in Fig. 3 in which a greedy-based offer density classification edges a greedy-based offer revenue classification. For clarification purpose, in Fig. 3, all the white rectangles refer to the offer’s resources demanded and the shaded ones represent their respective revenues.

Fig. 3.

Situation suited for greedy-based offer density.

The scenario, in which a greedy-based offer density classification will outperform a greedy-based offer revenue classification is when there are multiple combinations of offers, each of which demands all the seller’s resources capacity. The scenario showed in Fig. 3 is an example of that, where two combinations of offers require all the seller’s resources, which means that if one of them happens to be accepted by the seller then no spare seller resources will be leftover. Those two combinations are: ${O 1}$ and the group of offers: ${O 2, O 3, O 4}$ . By applying a greedy-based offer revenue classification, proposed by Bo An et al. [3], the seller will opt for the offer $O 1$ , because it generates the highest individual revenue. But, on the other hand, if he applies a classification based on offer’s density, he will rather accept the group of offers: $O 2$ , $O 3$ and $O 4$ over the offer $O 1$ for the sake of their densities. This classification with respect to that scenario is better than the former, which is explained by the fact that even though each offer of the offer set generates a smaller revenue than the offer $O 1$ , their cumulative revenue is higher than $O 1$ .

5.3. Greedy classification based on offer’s revenue

The classification based on offer’s revenue might take advantage over the classification based on offer’s density in case where this latter left some seller’s resources unassigned.

For the sake of clarification, we point out that in Fig. 4, all the white rectangles refer to the offer’s resources demanded and the shaded ones are their respective revenues, except for the bottom rectangle containing ${C, D}$ , which represents the unassigned resources that are leftover after applying the offer classification by the seller.

Fig. 4.

Situation suited for greedy-based offer revenue.

As depicted in Fig. 4, the seller by opting for a greedy-based offer revenue classification will accept offers $O 1$ and $O 2$ (encompassed by the upper curly brace) and reject the others. This will generate a higher revenue than what will be generated by applying a greedy-based offer density classification, where the offers accepted by this latter are encompassed by the lower curly brace.

Whenever the application of a greedy-based offer density classification produces some unassigned resources off the seller’s resources while the greedy-based offer revenue classification will not, this will generally mean that the latter will produce higher revenue than the former, which had been the case in the scenario depicted by Fig. 4.

6. Experimental results

For the sake of readability, the proposed composite-greedy seller strategy in the following figures have been labeled as “Composite-Greedy”, the greedy seller strategy [3] as “Greedy” and the Amazon fixed price scheme [2] as “Amazon-X” where X denotes the ratio price/cost of the seller. The proposed approach has been compared with [3] because it is the only market-based approach designed to run in cloud computing environment, implementing a many-to-many negotiation model and negotiating through leveled commitment contracts. In the greedy seller strategy [3], there is only one classification consisting of classifying the offers according to their revenues, in contrast to ours, where two classifications have to happen in order to choose which offer to keep and which offer to reject.

Amazon have also been chosen in our experimental setting to be assessed against our approach because it is a cloud-based commercial approach. It is important to remind that Amazon schemes are deprived from any disengagement feature and operate in first-in first-out fashion by applying a fixed-price scheme, which is not economically efficient [27].

The data used in the comparative study have been inspired by the current design of the GENI infrastructure [9].

6.1. Experimental setup

A series of simulations have been performed using different combinations of parameters from Table 3 as input to the different negotiation mechanisms. Each parameter is drawn randomly within its respective interval.

Table 3
Variables

Variables Values

Number of sellers $[5, 12]$

No. of resource types per seller $[2, 8]$

Quantity of a resource per seller $[2, 15]$

Unit cost of a resource $[10, 100]$

Initial bid of unit-resource $[300, 400]$

No. of resource types per buyer $[2, 6]$

Quantity of a resource per buyer $[2, 6]$

Value/cost ratio for the buyer $[1.2, 5.0]$

$dl (b)$ $[22, 41]$

$pd (b)$ $[30, 70]$

$ψ (r)$ $[0.2, 6.0]$

negotiation round 0.2

Variables	Values
Number of sellers	$[5, 12]$
No. of resource types per seller	$[2, 8]$
Quantity of a resource per seller	$[2, 15]$
Unit cost of a resource	$[10, 100]$
Initial bid of unit-resource	$[300, 400]$
No. of resource types per buyer	$[2, 6]$
Quantity of a resource per buyer	$[2, 6]$
Value/cost ratio for the buyer	$[1.2, 5.0]$
$dl (b)$	$[22, 41]$
$pd (b)$	$[30, 70]$
$ψ (r)$	$[0.2, 6.0]$
negotiation round	0.2

Requirements of the buyer: The requirements of each buyer in terms of the number of resources will be generated from Table 3, in which a buyer requires 2 up to 6 resources. The number of instances for each resources requested by the buyer will range from 2 to 6.

The timing of the buyer: The requested time of each resource will range from 30 to 70 while the deadline of each buyer’s tasks fall in the range $[22, 41]$ .

Pricing of the buyers: Each buyer will evaluate initially each resource unit between $[300, 400]$ , and make more and more concession as the negotiation progresses. Value/cost ratio is used as a factor to determine the upper bound the buyer could afford for each resource. For example if value/cost ratio is set to 2 and the initial bid for a given resource unit to 300, it means that the buyer could bid for that resource a price that goes from 300 up to ( $300 * 2 = 600$ ).

Supplies of the seller: The seller on his side can supply 2 up to 8 types of resources with a quantity of each of them ranging between 2 to 8.

Resource demand/supply ratio: To reflect each value of the demand/supply ratio that might come from Table 3, we have begun by first generating the sellers’ supplies, and based on that we have kept generating buyers’ demands until the desired ratio’s value is reached.

6.2. Observations and analysis of results

Due to the limited computational resources disposed in our personal desktop empowered with an i5 processor, we have conducted only 1002 simulations on the different ratio’s resource/demand. Since the social welfare of different mechanisms could be significantly disparate, we report the ratio of the social welfare, when sellers deploy the greedy classification [3] and the fixed price Amazon scheme [2] to the social welfare where the sellers deploy the “composite-greedy” classification. It will be followed by five other metrics which are representative of the seller strategy’s characteristics, namely, buyer utility on average, percentage of buyers served, seller strategy’s revenue, seller strategy runtime and resource utilization.

Fig. 5.

Social welfare and resource competition.

Fig. 6.

Served buyers and resource competition.

Fig. 7.

Buyer utility on average and resource competition.

From Fig. 5, the proposed seller negotiation model generates higher social welfare than any other evaluated mechanisms. However, the Amazon schemes with lower prices generate the highest social welfare when $ψ (r)$ takes on values of 0.8 and 1.0 because they generate the highest buyer served rate – the rate of served buyers who had successfully started their tasks – on those values, as it is shown in Fig. 6. In fact, we could observe from Fig. 6 that both greedy strategies, i.e. simple and composite ones, generate a lower served buyer rate when the value $ψ (r)$ equates (0.6; 0.8 or 1.0) in comparison to the Amazon schemes with lower prices. This happens because each agent will not accept or offer any offer worse than his expectation. Moreover, since the fixed price scheme of Amazon doesn’t include any disengagement possibilities, the single-minded buyers will be condemned to keep their contracted resources unused in case of failing in their negotiations, generating by the way a negative utility as it is shown from Fig. 7. Such situations let consequently drop the served buyer rate as shown in Fig. 6 when the resource competition $ψ (r)$ is large. In effect, those two negative effects on Figs 7 and 6 on the buyers side when applying Amazon scheme, come from the fact that these schemes are deprived from the decommitment feature. This implies that buyers will keep away resources unused when they can’t gather all the resources to start their tasks, which may even drop further the served buyer rate of Fig. 6 since those unused resources might be exploited by other buyers to help them satisfy their missing resources. A third negative effect could be added when using a protocol deprived from the decommitment feature. That effect is the result of decreasing social welfare due to the decrease of the served buyer rate which in turn was caused by the deprivation of the decommitment feature. The decrease of social welfare is correlated with the decrease of the buyers served rate, since the execution of buyers’ tasks represent their main source of utility.

Fig. 8.

Seller’s revenue on average and resource competition.

We could observe from Fig. 8, that the “composite-greedy” strategy generates on average a higher seller utility than the “greedy” strategy [3]. This is pretty obvious since our seller strategy encompasses the seller strategy defined in [3], and try to make better decisions by making further exploration through the evaluation of an additional classification which is based on offer’s density, and then pick the best one among the two, each time it has to resolve the WDPS. Moreover, from Fig. 8, we could observe a relationship between the pricing applied in the Amazon fixed price scheme and the generated seller’s revenue in which it increases with the increase of the pricing applied by that scheme, which generates a revenue up to a level that is higher than any other negotiation model where the ratio price/cost starts to reach 12. However, observing Figs 7 and 8, we notice that the increase on the utility of the seller on the Amazon fixed price scheme is not without any side effects. In fact, it is made at the detriment of the buyer’s utility leading it even to generate a negative utility on average when the ratio price/cost of Amazon scheme reaches a certain threshold. This could be simply explained by the fact that the Amazon fixed-price scheme is deprived from the decommitment feature, condemning buyers who don’t longer need the resources to keep and buy them, leading them to generate losses that increase with the increase of the price/cost of Amazon scheme.

Fig. 9.

Utilization and resource competition.

The Fig. 9 shows that the “composite-greedy” strategy produces the best performances in that metric (resource exploitation rate) followed by the “greedy” strategy and the amazon fixed-price schemes. This is partly because the composite greedy strategy makes a better approximate approach than its counterpart greedy approach by trying to maximize the seller’s expected utility (Eq. (9)) through the evaluation of multiple strategies (i.e. in our case, there are two evaluated classifications against one classification in the greedy approach), and as a consequence, it leads to a higher resource usage efficiency reflected through in Fig. 9. The increase of the rate of resource utilization is partly correlated with the increase of the served buyer rate in Fig. 6. This claim is proved by the relationship found between Figs 6 and 9, which is logical since the utilization rate is nothing than the proportion of allocated resources to the buyers community. However, there are some irregularities in that relationship when $ψ (r)$ equates (0.6; 0.8 or 1.0) where approaches having a lower resource utilization rates (Amazon schemes) manage to obtain a higher buyer served rate; it is explained by the fact that Fig. 6 shows only the buyers served rate of those who had successfully started their tasks and ignoring those who failed to do so, even though they had unnecessarily contracted a significant part of the market’s resources which had contributed to the increase of utilization rate in Fig. 9.

Fig. 10.

Runtime of seller strategy and resource competition.

In terms of running time shown in Fig. 10, the most efficient one is obviously the Amazon fixed-price scheme since it allocates resources for participants on a trivial basis: first-come first served, followed by the greedy approach [3], and proposed “composite-greedy” approach which gets the least performance on that metric due to the additional steps taken in its way to determine and classify the buyers’ offers.

7. Conclusion

This paper proposed a seller negotiation strategy suited for intractable many-to-many negotiation problems. In those problems, many buyers and sellers interact with each other using thread negotiations allowing each of them to perform many negotiations in parallel. An approximation to such problems consists of decentralizing the computational workload by letting the negotiation decisions being taken locally by all the market participants. This means in part, that each seller will hold his own auction based on his own available resources instead of referring to a third and central entity. Adding to that, the seller must take into account the extent of commitment of each offer while conducting his proper auction; the leveled commitment concept is combined with the decentralized negotiation protocol in order to achieve a better approximation for such negotiation problems. However, even though applying a decentralized negotiation protocol to reduce the workload of that problem, sellers and buyers have to adopt efficient computational strategies so that no unacceptable delay would be generated in the market system. Having compared the proposed “composite-greedy” seller strategy to other related strategies deployed in the Cloud environment, we could deduce that the proposed approach is a better choice when the aim is to obtain higher seller revenue and higher resource utilization while not compromising the computational efficiency and time complexity of the seller negotiation approach.

References

Agmon Ben-Yehuda

et al., Deconstructing Amazon EC2 spot instance pricing, ACM Transactions on Economics and Computation 1(3) (2013), 16. doi:10.1145/2509413.2509416.

Amazon Elastic Compute Cloud, http://aws.amazon.com/ec2/.

et al., Automated negotiation with decommitment for dynamic resource allocation in cloud computing, in: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: Volume 1–Volume 1. International Foundation for Autonomous Agents and Multiagent Systems, 2010.

Branson,

Douglis,

Fawcett,

Liu,

Riabov and

Ye, CLASP: Collaborating, autonomous data stream processing systems, in: Proceedings of the ACM/IFIP/USENIX 8th International Middleware Conference, 2007, pp. 348–367.

S.-H.

Chun and

B.-S.

Choi, Service models and pricing schemes for cloud computing, Cluster Computing 17(2) (2014), 529–535. doi:10.1007/s10586-013-0296-1.

Fujiwara,

Aida and

Ono, Applying Double-Sided Combinational Auctions to Resource Allocation in Cloud Computing, Applications and the Internet (SAINT), 2010 10th IEEE/IPSJ International Symposium on, IEEE, 2010.

Fukuta and

Ito, Fine-grained efficient resource allocation using approximated combinatorial auctions, Web Intelligence and Agent Systems: An International Journal 7(1) (2009), 43–63.

S.K.

Garg

et al., Double auction-inspired meta-scheduling of parallel applications on global grids, Journal of Parallel and Distributed Computing 73(4) (2013), 450–464. doi:10.1016/j.jpdc.2012.09.012.

GENI System Overview, http://www.geni.net/.

10.

Goyal and

Ma, A fuzzy attitude based bidding strategy in continuous double auctions, Web Intelligence and Agent Systems: An International Journal 10(1) (2012), 65–74.

11.

M.R.

Habes,

Belleili-Souici and

Vercouter, A dynamic hybrid buyer bidding strategy for decentralized and cloud-based many-to-many negotiation, Multiagent and Grid Systems 10(3) (2014), 165–183. doi:10.3233/MGS-140221.

12.

N.R.

Jennings

et al., Automated negotiation: Prospects, methods and challenges, Group Decision and Negotiation 10(2) (2001), 199–215. doi:10.1023/A:1008746126376.

13.

Lai,

Sycara and

Li, A decentralized model for automated multi-attribute negotiations with incomplete information and general utility functions, Multiagent and Grid Systems 4(1) (2008), 45–65. doi:10.3233/MGS-2008-4104.

14.

S.E.

Lander and

V.R.

Lesser, Sharing metainformation to guide cooperative search among heterogeneous reusable agents, Knowledge and Data Engineering, IEEE Transactions on 9(2) (1997), 193–208. doi:10.1109/69.591446.

15.

Mazhelis and

Tyrväinen, Economic aspects of hybrid cloud infrastructure: User organization perspective, Information Systems Frontiers 14(4) (2012), 845–869. doi:10.1007/s10796-011-9326-9.

16.

Mito and

Fujita, On heuristics for solving winner determination problem in combinatorial auctions, Journal of Heuristics 10(5) (2004), 507–523. doi:10.1023/B:HEUR.0000045322.51784.2a.

17.

T.D.

Nguyen and

N.R.

Jennings, Coordinating Multiple Concurrent Negotiations, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, Vol. 3, IEEE Computer Society, 2004.

18.

T.D.

Nguyen and

N.R.

Jennings, Managing commitments in multiple concurrent negotiations, Electronic Commerce Research and Applications 4(4) (2006), 362–376. doi:10.1016/j.elerap.2005.06.005.

19.

Patodi,

A.K.

Ray and

Jenamani, GA Based Winner Determination in Combinatorial Reverse Auction, Emerging Applications of Information Technology (EAIT), 2011 Second International Conference on, IEEE, 2011.

20.

Y.K.

Penya and

N.R.

Jennings, Optimal combinatorial electricity markets, Web Intelligence and Agent Systems: An International Journal 6(2) (2008), 123–135.

21.

Sandholm, Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence 135(1) (2002), 1–54. doi:10.1016/S0004-3702(01)00159-X.

22.

Sandholm

et al., CABOB: A Fast Optimal Algorithm for Combinatorial Auctions, International Joint Conference on Artificial Intelligence, Vol. 17, Lawrence Erlbaum Associates LTD, 2001.

23.

Sandholm and

Lesser, Leveled commitment contracts and strategic breach, Games and Economic Behavior 35(1–2) (2001), 212–270. doi:10.1006/game.2000.0831.

24.

Sghir

et al., A Recombination-Based Tabu Search Algorithm for the Winner Determination Problem, Artificial Evolution, Springer International Publishing, 2013.

25.

Shil ,

Kumar,

Mouhoub and

Sadaoui, An Approach to Solve Winner Determination in Combinatorial Reverse Auctions Using Genetic Algorithms, Proceedings of the 15th Annual Conference Companion on Genetic and Evolutionary Computation, ACM, 2013.

26.

Sun

et al., Efficient Nash Equilibrium Based Cloud Resource Allocation by Using a Continuous Double Auction, Computer Design and Applications (ICCDA), 2010 International Conference on, Vol. 1, IEEE, 2010.

27.

Wang, Auctions versus posted-price selling, The American Economic Review 83(4) (1993), 838–851.

28.

Wu and

J.-K.

Hao, Solving the winner determination problem via a weighted maximum clique heuristic, Expert Systems with Applications 42(1) (2015), 355–365. doi:10.1016/j.eswa.2014.07.027.

29.

Zaman and

Grosu, Combinatorial auction-based allocation of virtual machine instances in clouds, Journal of Parallel and Distributed Computing 73(4) (2013), 495–508. doi:10.1016/j.jpdc.2012.12.006.

t	The current time
$vt$	The next time in which the buyer will execute its strategy
o	Represents a simple offer
$T o$	Represents a tentative agreement offer
$F o$	Represents a final agreement offer
${TA}_{b}$	Represents the tentative agreement set
$A_{b}$	Represents the final agreement set
$tg (b)$	Represents the task generation time
$est (b)$	Represents the earliest start time to start the task τ
$dl (b)$	Represents the deadline for starting the task τ
$R_{s}$	Represents the seller’s resources available for sell
$R_{b}$	Represents all the resources required by the buyer b
${CR}_{b}$	Represents the current demanded resources of the buyer
$step$	Represents the time of the negotiation round (step)
${iter}_{i}$	Represents the ith iteration time
$ψ (r)$	Represents the demand/supply ratio for the resource r
$υ_{b} (t)$	The utility generated when b executes τ. This utility gets its highest value at $est (b)$ and decreases linearly as the time of execution gets away from it
$q (R_{b}, r)$	Stands for the quantity of units r the buyer needs
$c_{b} (r)$	Stands for the unit cost of resource r

t	The current time
${DA}_{s}$	The set of the seller s’s definite final agreements
$A_{s}$	The set of the seller s’s final agreements
${TA}_{s}$	The set of the seller s’s tentative agreements
	The new coming offer that triggers WDPS
$R_{s}$	The set of s’s seller resources available for sale
$pd (o)$	The resource usage time required by the contract o
$q (r)$	The quantity demanded for the resource r
$c_{s} (r)$	The seller’s cost for the resource r
$ϕ (o)$	The seller’s reserve price for the resources demanded in the offer o
$ψ (r)$	The ratio demand/supply of the resource r
$R (o)$	The set of resources demanded by the offer o
$pr (o)$	The offering price of the offer o
$cost (o)$	The seller’s cost for the offer o
$pe (o)$	The offer o’s decommitment penalty
$v (o)$	The offer o’s value with respect to a specific seller’s offer classification
$stage (o)$	The offer o’s current stage
$rwdps (o)$	The offer o’s outcome with respect to the latest WDPS
$bidder (o)$	The identity of the bidder who submitted the offer o