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
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
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.
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.
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.
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
More formally, the offer format will be presented to the seller as follows:
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.

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”.
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.
Used symbols for Buyer strategy
Used symbols for Buyer strategy
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.

Disposition of the time axis.
As depicted in the Fig. 2, the buyer will generate a task τ at a time
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 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
Finally, we end this section by giving a buyer pseudo-algorithm (Algorithm 1) inspired from [3] which describes the main strategy of this latter.

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., (
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.
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.
Used symbols for seller strategy
Used symbols for seller strategy
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
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.

Seller strategy

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).
As mentioned in the Algorithm 2, the
process takes four parameters, namely: the first one
after running the WDPS. The second and third parameters
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:
or one of the tentative agreements
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:
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.
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.

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:
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

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
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.
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].
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.
Variables
Variables
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
Pricing of the buyers: Each buyer will evaluate initially each resource unit between
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.
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.

Social welfare and resource competition.

Served buyers and resource competition.

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

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.

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

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.
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.
