2012 International Symposium on Cloud and Services Computing

Strategic bidding for Cloud resources under Dynamic Pricing schemes

K.Sowmya1, R.P.Sundarraj2
Department of Management Studies
IIT Madras
1
[email protected], [email protected]

Abstract— Cloud computing offers computing and storage The availability of different pricing schemes has in turn
services which can be dynamically developed, composed and led to a broader set of options to choose for a cloud user.
deployed on virtualized infrastructure. Cloud providers This fact is further magnified by newer schemes of pricing
holding excess spare capacity, incentivize customers to such as the dynamic pricing where users bid for compute
purchase it by selling them in a market (spot market), where resources on the cloud. Users need to think strategically
the prices are derived dynamically based on supply and before choosing a pricing model or placing their bids.
demand. The cloud providers allow clients to bid on this excess The purpose of this paper is to specifically examine the
capacity by allocating resources to bidders while their bids behavior of bidders in a dynamic cloud resource pricing
exceed a intermittently changing dynamic spot price. In this
environment and propose strategies that can serve as a
paper we have used game theory to model the bidding
reference for bidders intending to procure compute resources
strategies of bidders in a spot market who are attempting to
procure the cloud instances, as a prisoner dilemma game. We on the cloud. A game theoretic approach has been taken to
then analyze real time data from Amazon EC2 spot market to model the set of strategies available to bidders. We have
validate this model. In a single shot prisoner dilemma game proposed a Prisoner Dilemma game to model the bidding
mutual defection is the Nash equilibrium. We find that a strategies of the bidders. We then identify the conditions
majority (approx. 85%) of bidders choose to Defect which is under which this game can be modeled as a Prisoner
in-line with the single shot classical prisoner dilemma game. Dilemma game. For this we have resorted to simulation to
However considering that most bidders in a spot market are identify the ranges within which the game can be modeled as
repetitive bidders, we propose a Co-operation strategy which is a Prisoner Dilemma game. We then evaluate our model
in-line with the Iterated Prisoner Dilemma Game. using real-time spot price data. Next we examine the current
strategies of the bidders from this data to understand the
Keywords- Cloud Computing; Spot pricing; Dynamic pricing; strategies that are being adopted by bidders in real-time.
Bidding; Prisoner Dilemma; Repeated Games Section 2, provides a review of literature of the cloud
pricing and dynamic pricing literature. Section 3, provides
I. INTRODUCTION
the context for Spot pricing. In section 4, we model the
As per the NIST definition, Cloud computing is a model bidding strategies as a Normal form Game and compare it
for enabling convenient, on-demand network access to a with the Classic prisoner dilemma game. The simulation
shared pool of configurable computing resources (e.g., model used to check for the Prisoner dilemma condition is
networks, servers, storage, applications, and services) that also described in Section 4. In section 5, we provide our
can be rapidly provisioned and released with minimal observations and results. Section 6 provides the summary
management effort or service provider interaction [1]. and scope for future work.
Despite some well-known fears like security, trust and
privacy, cloud computing continues to draw more adopters. II. LITERATURE REVIEW
From the recent industry reports [2] one can clearly infer that
A. Cloud Pricing
the emerging network of cloud players is bound to expand
[3]. This is primarily because of the flexibility that it offers Much before the advent of Cloud Computing, online
to organizations to meet variable demand without any fixed markets for computational resources have been proposed by
investment in capacity. These online businesses experience many researchers. One of the earliest works is the
fluctuations in the number of users of their platforms. It is POPCORN MARKET project by Regev and Nisan [4].
thus necessary for these businesses to support any sudden Since then many economic models for sharing computing
surge in demand without incurring excessive upfront resources have been formulated. In the case of Cloud service
investments in computing infrastructure. The expansion in providers, every provider has its own pricing scheme. For
the size and number of cloud players would in turn create a example, Salesforce uses “pay per use” scheme [5]. Amazon
demand for robust and efficient pricing models, as large and uses “pay-per-use fixed pricing” say first 50 TB / Month of
mid-size cloud vendors try to capture greater market share. Storage used costs $0.150 per GB [6]. Some others use “pay
Selection of a pricing policy for the cloud is complicated due for the resources” that are assessed based on speed of
to the constant fluctuation in the number of users and the bandwidth or amount of storage (storage or bandwidth size).
heterogeneous nature of their demand. This has resulted in This method is more common in Platform as a Service
adoption of different types of pricing models by the cloud (PaaS) and Infrastructure as a Service (IaaS) deployments.
vendors. According to Weinhardt et al. [5], the most prevalent method
of pricing in cloud is pay per use (also known as the on-

978-0-7695-4931-6/12 $26.00 © 2012 IEEE 25

DOI 10.1109/ISCOS.2012.28
demand model), which is based on units with constant price. From the above section we can say that the spot market is
Another common pricing model is subscription, whereby like a (N + 1)th price auction of multiple goods where each
users sign a contract (subscribe) based on constant price of client bids for a single good which is the spot instance [15].
service unit for a longer period of time, for example six The provider chooses the top N bidders. The value of N
months or a year (also known as reserved instance model). varies based on the supply (unused capacity at hand) and
Obviously, customers and providers would like to use static cannot exceed the available capacity. The provider sets the
and simple pricing models in order to ease payment uniform price to the price declared by the highest bidder
prediction. Nevertheless, research indicates that dynamic who did not win the auction (bidder number N + 1) and
pricing can be more efficient [7] [8].
publishes it. The top N bidders are declared as winners and
B. Dynamic Pricing pay the published price.
According to Reinartz, dynamic pricing is the dynamic IV. MODELING THE STRATEGIES OF BIDDERS IN A SPOT
adjustment of prices to consumers depending upon the value
MARKET
these customers attribute to a product or service [9]. Narahari
et al provides a review of the models used in dynamic A. Bidding Strategies as a Normal Form Game
pricing: Inventory based models, data-driven models, game-
theoretic models, machine learning models and simulation Consider the case of two bidders Player 1 and Player 2
models [10]. The concept of dynamic pricing has been bidding in a given spot-market instance for which the
studied and implemented widely in utility industry, average spot-price is known and given. In this scenario, the
especially in the electricity distribution industry [11]. There players have the option to bid high or low,. In this paper, we
are several works that have studied dynamic pricing in the define high and low with respect to the spot price; bid prices
context of cloud computing. Kondo demonstrates how users above (below) the spot price are considered as high (low).
should bid optimally on spot (a dynamic pricing scheme) Clearly four combinations of options are feasible:
instances to reach different objectives with desired levels of
confidence in a cloud computing setup [12]. Few researchers a) Both Player 1 and Player 2 bid a high value.
have gone a step further and examined Amazon spot price b) Both Player 1 and Player 2 bid a low value
traces and built decision models around that. Buyya et al c) Player 1 bids a high value and Player 2 bids a low
have provided a statistical modeling of spot prices in a public value.
cloud environment [13]. Dynamic pricing, in principle, d) Player 1 bids a low value and Player 2 bids a high
encourages users to shift their flexible workloads from value.
provider's peak hours to off-peak hours and thus obtain
monetary incentives. An analysis of one year spot price data Since spot price is determined based on the supply and
by Wee shows that it is reasonable for users to shift their demand, bidders can strategically co-operate with each other
workloads from on-demand to spot since it was on an by bidding low. A low bidding strategy by all the bidders
average 52.3% cheaper; however, shifting the workload to would, in turn, force the cloud provider to reduce the spot
cheaper spot periods provides only 3.7 % additional cost price. On the other hand, even though spot users could be
savings [14]. price conscious, they might want to enjoy relatively
uninterrupted service. Hence the bidders would take
III. CONTEXTUALIZING SPOT PRICING advantage of the opportunistic capacity by submitting a
higher maximum bid price, since they often would pay the
Research on dynamic pricing schemes has attracted the operating spot-price and not pay that their bid price.
industry to implement and use dynamic pricing. For Let BL denote a low spot price and BH denote a high spot
example one of the top cloud service providers Amazon price. The opportunistic advantage achieved by a player
EC2 has implemented the dynamic pricing model through bidding high when the other player bids low (since higher
their spot pricing scheme. bidder still procures the spot at low price) is denoted by .
Spot Instances enable users to bid for unused capacity, Thus, in Game Theory terms, such a bidder is called a
i.e. the capacity that remains with the cloud provider after defectors. A player bidding low is at a disadvantage when
fulfilling the on-demand and reserved instance demands. the other player has bid high since he/she faces higher
Instances are charged the Spot Price, which is set by the chance of intermediate termination. Such a player is called a
service provider and fluctuates periodically depending on cooperator and the disadvantage is denoted by . Whenever a
the supply of and demand for Spot Instance capacity. spot user faces termination he may choose to a) wait till the
Consider a bidder, whose has a certain valuation for spot instance is allocated again or b) continue his computing
executing a task on a particular type of spot instance. In a job on the on-demand instance. In this paper we focus only
spot pricing scheme, if the bid price exceeds the current spot on case b.
price, the instance is allocated until either the user chooses Based on these inputs the moves of both players are
to terminate upon task completion or the termination is captured as a normal form game (see Fig 1).When both
initiated by the vendor upon the spot price increasing above players co-operate with each other placing a low bid, the
the bid price. In this paper we look at strategies for bidding resulting spot price determined by the cloud vendor will also
in a spot market.

26
be low, i.e when both players bid at BL, the resulting spot Rewriting equations (1) and (2) based on the payoffs given
price cannot exceed BL, hence the payoffs in cell A (in in the game in Figure 1, we have
Figure 1) for both players is –BL. Similarly, when both
players defect by bidding high (Cell D), the resulting spot ሺെ‫ܤ‬௟ ൅ ɒሻ  ൐  െ௟  ൐  െ௛  ൐ ሺെ‫ܤ‬௟ െ Ʉሻ (3)
price determined by the cloud vendor is also high. Cells B
and C represent cases where one player defects and other െ௟  ൐  ሾሺെ‫ܤ‬௟ െ Ʉሻ  ൅  ሺെ‫ܤ‬௟ ൅ ɒሻሿȀʹ (4)
player co-operates. Since bidding for spot instances is like a
(N+1) auction, the lowest of the two bid values is finally 1) Computing BL, BH, ߟܽ݊݀߬
chosen as the bid price. In this case the lowest bid price is As per the definition in previous section, BL is chosen
BL. In addition the Defecting player gets an advantage from a range of values between the average spot price and
captured by  and the Co-operating player gets a the minimum spot price. Similarly BH is chosen from a
disadvantage captured by . range of values between average spot price and maximum
spot price. The advantage of Defecting () is computed as
Player 2 the difference between the Bid price (BH) and actual Spot
Price. The disadvantage due to Co-operating is computed as
Co-operate Defect the difference between the On-Demand price and the Bid
(place a low bid) (place a high bid)
price (BL), since it is assumed that when spot users who get
(-BL, -BL) (-BL- , -BL+) intermittently terminated would continue their computing
Co-operate
jobs on an on-demand instance.
Player 1

(place a low bid) B

A
To test for conditions (1) and (2), we have used real time
(-BL+ , -BL-) (-BH , -BH) spot price data from Amazon EC2. To choose the range of
Defect
(place a high bid) values for BH and BL that satisfy conditions 1 and 2 a
C D simulation model using ARENA 12.0 was formulated. Since
BL and BH are chosen between the ranges above and below
Figure 1. Normal form Game capturing the Bidding strategies and payoffs
. the mean we have formulated BH and BL as depicted by
We extend the generalized normal form game given in equations (3) and (4).
Figure 1 into a classic prisoner dilemma game in the
following section. BH <=  + ʄ ---- (3)

BL >=  - ʄ ---- (4)

B. Bidding Strategies as a Prisoner Dilemma Game
The classic prisoner dilemma game is shown in Figure 2. where  is the average spot price
For the game depicted in Figure 1 to be a Prisoner  is the standard deviation
Dilemma game, the conditions given by equations (1)  is the PD factor
and (2) need to be met.
2) Determining the PD factor ()
The objective is to maximize the factor ʄ, which in turn
gives maximum BH and minimum BL. Max BH and Min BL
Player 2 maximize the number of bidders who satisfy the Prisoner
Defect dilemma conditions (1) and (2), for this reason we refer to
Co-operate
(place a low bid)
(place a high the factor ʄ as the PD factor.
bid)
Co-operate From equation (4):
(a, a) (b, c)
Player 1

(place a low bid)

ʄ > = (  - BL ) / 
Defect
(c, b) (d , d) Objective: Max (  - BL ) / 
(place a high bid)

Subject to: c > a > d > b

Figure 2. The classic Prisoner Dilemma Game Where,
C = -BL + 
Where: [16] A = -BL
D = -BH
c>a>d>b (1) B = -BL - 
 = BH - 
a > (b + c)/ 2 (2)

27
  = OD – BL TABLE 1: RESCALING FIGURE 6 TO SPECIFIC VALUES OF ON-DEMAND
OD = on-demand price PRICE AND NUMBER OF BIDDERS a
% of On- % of Bid Spot BD * Bidder
By observing real-time data from Amazon EC2 Spot the demand Distribution price N/100 Strategy
price (OD) (BD) b c
values for ,  and OD were determined. The simulation
results yielded a  of 0.9. Increasing  beyond 0.9 failed to
satisfy the conditions (3) and (4). However, decreasing  0 - 30% - - - NA
below 0.9 continued to meet the conditions (3) and (4). To 30-39% 9.00 0.456 5.67 Low
test for different values of  < 0.9 , we used an Iterated Grid Bidder
Search Method. 40-49% 5 0.57 3.15 High
3) Testing using iterated Grid Search Method Bidder
50-59% 14 0.684 8.82 High
An iterated Grid Search Method was used to choose Bidder
different values of BH and BL in accordance with 60-69% 14 0.798 8.82 High
Equation(5) and (6). Bidder
70-79% 9 0.912 5.67 High
BH =  –  ---- (5) Bidder
80-89% 10.2 1.026 6.426 High
Bidder
BL =  –  ---- (6) 90-99% 3.5 1.14 2.205 NA

where  < 0.9, BL > 0 , BH > 0 100-200% 35.3 > 1.14 - NA

A simulation model was built to test using the Iterated
a. od = 1.14,  = 0.505, BHmax = 1.092, BLmin = 0.01 and N = 6
Grid Search Method. The pseudocode used for the b. S = OD * od
simulation model is given below: c. (S <  , Low; S > , High)

PseudoCode: Figure 3 and Figure 4 summarize the simulation results.

Figure 3 provides a plot of BL and BH for different values of
// Calculate the mean and standard deviation of the ʄ obtained from multiple simulation runs. We can observe
dataset that as ʄ moves closer to the mean the BL and BH band
Assign AvgSpotPrice, StdDeviation become narrower. However, Figure 4 which provides a
// Determine the On-Demand Price for that dataset graphical view of c, a, d, b for different values of  obtained
Assign OnDPrice from multiple simulation runs. We can observe that c, a, d
//Choose the PD factor for the dataset and b lines are placed one above the other and continue to
Assign  = 0.9 remain so for decreasing values of  (in steps of 0.01). This
//Decrement PD factor in steps of 0.01 and repeat the indicates that irrespective of the thinning band, the Prisoner
computations for each step. dilemma condition is met.
for  > AvgSpotPrice
 =  – 0.01
Compute Bh = AvgSpotPrice +  (StdDeviation)
Compute Bl = AvgSpotPrice +  (StdDeviation)
Compute  = OnDPrice - Bl
Compute  = Bh - AvgSpotPrice
if (Bh > 0 AND Bl > 0)
Compute c = -Bl + 
Compute a = -Bl
Compute d = -Bh
Compute b = -Bl- 
if (c > a AND a> d AND d> b)
if ( a > (b + c) /2)
return Prisoner Dilemma satisfied
else
return Prisoner Dilemma not satisfied
else Figure 3. A plot of BL and BH for different values of  obtained from
return Prisoner Dilemma satisfied multiple simulation runs.
else
return Bid values cannot be negative

28
 High Bid or Low Bid, based on whether it is above or below
the mean ().
Clearly from Table 1, we can observe that most bidders
about (85%) choose to Bid High (indicative of Defection)
and a meager number (15%) choose to Bid Low (indicative
of Co-operation).
A. Coherence with Single shot Prisoner Dilemma Game
In a single shot prisoner dilemma game mutual
defection is the equilibrium strategy, i.e., both the players (if
they are self-interested and rational) should choose to
Defect by bidding high. Results from our analysis indicate
that the bidders who are competing for spot instances
behave in-line with the game-theoretic prediction by
predominantly Defecting. This indicates that the bidders are
bidding strategically. This result is acceptable only for
Figure 4: A plot of C, A, D, B for different values of  obtained from
multiple simulation runs
bidders who bid on the spot market only once. However,
bidders on a spot market are not one-time bidders, the
bidders need to be conscious of the fact that they would be
V. OBSERVATIONS AND RESULTS bidding in multiple rounds. Hence, a strategic bidder should
Comparing the equilibrium solution in the previous look at bidding in multiple rounds which can be captured in
section with the actual bidding strategies in real-time is the form of an iterated prisoner dilemma.
crucial to understand and create a blueprint of bidder B. Strategic Bidding Using Iterated Prisoner Dilemma
behavior while procuring cloud services electronically. To Most bidders on a spot market may not be first time
achieve this we have used real time bidding information of users; hence the co-operation may be due to the fact that
users in a spot market from Amazon EC2 (one of the largest they are bidding in multiple rounds, which can be modeled
players in the cloud services market). Figure 6 provides a as a repeated or an iterated prisoner dilemma game. There
snapshot of Spot Bid distribution as a percentage of On- are results which indicate that repetition yields co-operation
Demand prices. On the outset we can infer from the chart in in a Prisoner Dilemma game [17]. The optimal (points-
Figure 6 that, a significant number of bidders are bidding maximizing) strategy for the one-time PD game is simply
either close to or above the on-demand price itself. defection; as explained above, this is true whatever the
composition of opponents may be. However, in the iterated-
PD game the optimal strategy depends upon the strategies of
likely opponents, and how they will react to defection and
cooperation. The best deterministic strategy was found to be
tit for tat. The strategy is simply to cooperate on the first
iteration of the game; after that, the player does what his or
her opponent did on the previous move. Co-operation
tended to be collectively stable in an iterated prisoner
dilemma game.
Whether cooperation is the best strategy, depends to a
great extent on the probability (generally indicated by )
that the players will meet again [17] which is also called the
discount parameter. When the bidders have a negligible
chance of meeting again  is low– each interaction can in
Figure 6: Snapshot from Amazon EC2: Spot Bid distribution as a
percentage of OnDemand price. effect be modeled as a single-shot Prisoner's Dilemma
game, and the strategy "ALL DEFECT" is the most
However we cannot directly compare the results from appropriate, because even if one of the bidder decides to
section 3 with that depicted by Figure 6. Hence we have re- cooperate, then a rational self-interested opponent will try to
baselined the chart using the real-time on-demand price and opportunistically exploiting that by defecting. But in the
the corresponding average spot price from the data set used iterated Prisoner Dilemma the total value of repeated co-
in the simulation model in section 3. Table 1 indicates the operations in repeated interactions can become larger than
re-baselined data. We then look for rows that fall within the the benefit of a single Defection (tit for tat strategy).
BLmin and BLmax values, which is further categorized as a In the context of bidding for the Spot Instances, when
the bidders realize that mutual co-operation will yield

29
greater benefits in the long run and start bidding low , the [7] A. Anandasivam and M. M. Premm, "Bid price control and dynamic
pricing in clouds," Proceedings of the European Conference on
overall spot price set by the vendor starts to decline. This Information Systems, pp. 1-14, 2009.
can cause a cyclical effect and in a market comprising of [8] M. Mihailescu and Teo.Y, " Dynamic resource pricing on federated
strategic bidders the spot price can eventually be as low as Clouds.," Proceedings of 10th IEEE/ACM International Conference
the vendor’s reserve price. on Cluster, Cloud and Grid Computing (CCGrid) , pp. 513-517, 2010.
[9] W. Reinartz, "Customising prices in online markets," European
C. Triggering Co-operation Business Forum, pp. 35-41, 2001.
Even when the discount parameter  is high enough to [10] Y. Narahari, C. Raju, K. Ravikumar and S. Shah, " Dynamic pricing
attract reciprocal cooperation there is still a question of models for electronic business.," Sadhana(30), pp. 231-256, 2005.
whether and how cooperation might start. In the current case [11] M. Baughman and S. S. Siddiqi, " Real-time pricing of reactive
power: theory and case study results.," IEEE Transactions on Power
of bidding for spot instances, there is a degree of Systems (6:1), pp. 23-29, 1991.
predictability, since the spot price history data for the last 90 [12] A. Andrzejak, D. Kondo and S. Yi, "Decision model for cloud
days is publicly available. Bidders in a spot market can use computing under SLA constraints.," Proceedings of IEEE
this information to choose their Bidding Strategy. International Symposium on Modelling, Analysis & Simulation of
Computer and Telecommunication Systems (MASCOTS), pp. 257--
266, 2010.
VI. CONCLUSION [13] B. Javadi, R. Thulasiram and R. Buyya, "Statistical Modeling of Spot
Instance Prices in Public Cloud Environments.," Proceedings of
In this paper we have modeled the bidding strategies of Fourth IEE International Conference on Utility and Cloud Computing
spot users as a normal form game. We have then shown that , pp. 219-228, 2011.
for a band of bid values the game is equivalent to the [14] S. Wee, "Debunking Real-Time Pricing in Cloud Computing.,"
Proceedings of 11th IEEE/ACM International Symposium on Cluster,
prisoner dilemma game. We then analyze the real-time Cloud and Grid Computing (CCGrid), pp. 585 -590, 2011.
bidding strategies of bidders to understand if they are [15] O. Agmon Ben-Yehuda, M. Ben-Yehuda, A. Schuster and D. Tsafrir,
already bidding strategically. Most bidders choose the "Deconstructing Amazon EC2 spot instance pricing," IEEE Third
Defection strategy which is the equilibrium strategy in a International Conference on Cloud Computing Technology and
single shot prisoner dilemma game. However, users of a Science (CloudCom), pp. 304-311, 2011.
spot market who typically have a non-negative discount [16] Y. Shoham and K. Leyton-Brown, Multi Agent Systems, 2009.
[17] R. Axelrod, The Evolution of Cooperation, Basic Books, 1984.
factor will need to look at the game as an iterated prisoner
dilemma, in which Co-operation has shown to be a
collectively stable strategy. Hence a bidder will benefit in
the long run by cooperating rather than defecting.
As part of future work we intend to look at
generalizing the PD factor as a function of mean. The
perspective of vendor in determining the spot prices by
observing the strategic bidding behavior of bidders is
another potential area for future research. Bidding strategies
in the presence of irrational bidders could be a potential
future research area.
REFERENCES

[1] P. Mell and T. Grance, "Effectively and Securely Using the Cloud
Computing Paradigm," NIST, Information Technology Laboratory,
2009.
[2] Gartner Predicts, "Top Predictions for IT Organizations and Users for
2012 and Beyond,," Gartner.
[3] J. Weinman, "The future of Cloud Computing.," Proceedings of IEEE
Technology Time Machine Symposium on Technologies Beyond
2020 (TTM) , pp. 1-2, 2011.
[4] O. Regev and N. Nisan, "The POPCORN market. Online markets for
computational resources," vol. (28:1), no. 177--189., 2000.
[5] C. Weinhardt, A. Anandasivam, B. Blau and J. Stößer, "Business
models in the service world.," IEEE IT Professional, Special Issue on
Cloud Computing, p. 28–33, 2009.
[6] "Amazon Simple Storage Service (Amazon S3) Last accessed on July
13th, 2012.," [Online]. Available: http://aws.amazon.com/s3/.
[Accessed 13 July 2012].

30