Competitive Analysis for Multi-Commodity Ski-Rental Problem

1 Introduction

The classical ski-rental problem [Karlin et al., 2003] describes the dilemma where a customer trades off between two payment options for one commodity without the knowledge of the future: 1) renting, the customer only pays for an ondemand usage; 2) buying: the customer pays for lifetime usage at once, and no further payment will be incurred after that. Existing works have obtained the optimal online algorithm by minimizing the competitive ratio and extending the problem to adopt more complex payment options [Fujiwara et al., 2020; Patt-Shamir and Yadai, 2020; Wang et al., 2020; Wu et al., 2021].

However, literature performs sub-optimally when the customer uses a set of commodities altogether and each commodity is rented/brought individually. In this paper, we focus on this multi-commodity ski-rental problem. In this case, simply applying the classical ski-rental algorithm causes degraded performance in terms of competitive ratio. For example, we consider a ski-helmet-suit rental problem as follows:

When a customer goes skiing, he/she needs a pair of skis, a helmet, and a suit (three commodities) every time. Each commodity is rented or bought individually. Suppose the prices of buying each commodity are all $10, and the rental prices are all $0.1. If we employ the classical ski-rental algorithm on each commodity, the customer will buy all commodities when he/she goes skiing for the hundredth time. Then, the competitive ratio is (9.9+10)×3 10×3 = 1.99. (Note that by employing the classical ski-rental algorithm, 2 bounds the competitive ratio for all possible situations [Karlin et al., 2003], and 1.99 is the optimal competitive ratio in this example.) However, what out of the expectation is that 1.99 is no longer the optimal competitive ratio here. The customer can buy the three commodities at the 45th , 77th , and 100th time of use respectively. It surprisingly reduces the competitive ratio to 4.4+7.6+9.9+30 10+10+10 = 1.73. The ratio of 1.73 is reached when three commodities are used 100 times.

An online algorithm jointly considering multiple commodities can improve the competitive ratio, however, the problem then becomes more challenging due to the following reasons. First, arbitrary commodities can be involved in the system. We need to design an algorithm to systematically consider all involved commodities and their payment options, which produce a large solution space. Second, different commodities may have different rent-to-buy ratios. Such unbalanced commodities further complicate choices between renting and buying. Finally, although we may reduce the competitive ratio through the joint considerations of commodities, this reduction should have a limit. We also aim to answer how much the competitive ratio can be reduced.

Please note that besides the aforementioned ski-helmet-suit rental problem, there are many real-world examples of the multi-commodity ski-rental problem. Here are some more examples.

1. Bahncard problem [Fleischer, 2001] with bus and train. A customer takes the bus and train (two commodities) to go to work. For each type of transportation (commodity), he/she has two payment options. The first option is paying for a one-time ride (renting), and the other is purchasing a Bahncard to cover the monthly ride (buying). In the past, one could reliably estimate the times of commutes per month to decide whether to buy a Bahncard. However, due to the COVID-19 pandemic, people may work from home for a number of days in a month, and the number of commutes in one month is uncertain.

2. Cloud service acquisition problem with multiple service components [Wang et al., 2015]. The customer utilizes multiple service components (commodities) including virtual machines, storage, and serverless messaging to implement a cloud application. Every time the application is used, the customer must choose among payment options of each service component (commodity) to cover the usages. The payment options include 1) pay-as-you-go (PAYG): to pay for the on-demand usage of one service component (renting), and 2) reservation: to pay an up-front fee without further cost for one service component (buying). By convention, the literature assumes no prior statistics of the usages due to the high fluctuations [Guo et al., 2019] of the workloads and statistically non-stationary demands [Stewart et al., 2007]. Please note that we use this scenario in our trace-driven experiment in Section 6.2.

Our Contributions. In this paper, we investigate the multi-commodity ski-rental problem. Given a commodity set with multiple commodities and the corresponding renting/buying costs, our objective is to minimize the overall competitive ratio. To address this issue, we propose MultiObject Break-Even (MOBE) algorithm with N thresholds of cost corresponding to the N commodities. When the accumulated rental cost of a commodity reaches its threshold, the algorithm buys this commodity. Otherwise, the algorithm rents it to cover the usage. We prove an e e-1 tight lower bound for the competitive ratio of MOBE, and further show that this bound is optimal when all the commodities share the same rent-to-buy ratio. In addition, we propose an O(N 2 ) algorithm to obtain the N thresholds for the MOBE algorithm. We prove that the calculated thresholds lead to the optimal competitive ratio with the same rent-to-buy ratio commodities. Finally, we perform a trace-driven experiment to verify our theoretical analysis and compare the performance in a real-world scenario with benchmarks.

2 RelatedWork

The ski-rental problem [Karlin et al., 2003] deals with the trade-off between "renting" or "buying" without the knowledge of the future. It is a typical online scheme addressed by minimizing the competitive ratio. Recent works have investigated many variants of the classical ski-rental problem. [Fujiwara et al., 2020; Hu and Xu, 2017] studied the multi-slope ski-rental problem where the customer was provided with multiple extra payment options that charged both a one-shot up-front fee and per-use fees. [Ai et al., 2014; Wang et al., 2020] studied the multi-shop ski-rental problem where different shops had different rent/buy prices. [PattShamir and Yadai, 2020] analyzed the non-linear ski-rental problem where the pay-per-use cost is a continuous monotonic function of time. [Zhang and Conitzer, 2020] considered the system with multiple resources and the buying cost was a submodular function of the complementary set of what had been brought. [Wu et al., 2021] proposed the two-level ski-rental problem with multiple commodities. In addition to renting or buying a single commodity, all commodities could be brought together as a "combo purchase". However, when the "combo purchase" is disabled, their work is reduced to N independent classical ski-rentals for N commodities, which is essentially different from ours. [Fleischer, 2001] studied the Bahncard problem where the customer can buy a Bahncard to receive a discount on the rental cost.

The ski-rental problem is widely applied in real-world ICT systems where many problems can be modeled as the "rent or buy" predicament. [Wang et al., 2015] investigate the problem of reserving homogeneous infrastructure as a service (IaaS) instances. At each time, the user may request multiple instances, and the decision-maker must decide to rent or buy enough instances to satisfy the request. [Khanafer et al., 2013] studied the trade-off in web applications. For each query, a web application can choose whether to save (buy) the response in the cache, so as to avoid repeat computation (rent) in the future. [Saha et al., 2018] applied the ski-rental problem to the wireless channels leasing problem. The operator has to choose between better but paid channel quality and degraded channel quality with no charges without knowing the customer's demands and the channel availability. Their work proves that the competitive ratio's upper bound is strictly less than 4. Different from all the above works, this paper utilizes the characteristic that the customer uses multiple commodities altogether as a novel extension of the classical ski-rental problem.

3 ProblemFormulation

3.1 SystemOverview

The system is formulated by a commodity set S consisting of multiple commodities, which a customer will use unpredictably. Whenever the commodity set is used, all commodities si ∈ S, i = 1, 2, . . . , |S| are used once, and the decisionmaker (customer) needs to pay for the use of them all. There are two payment options for each usage of commodity si: (1) Renting: the user pays di for the on-demand usage. We assume that every time of use incurs the same cost di for si. (2) Buying: the customer immediately pays ci, and the commodity will not incur any further payment. Let the set of all possible commodity sets as S. In general, the commodities s1, s2, . . . , s|S| in S ∈ S can be either homogeneous (di = di′ and ci = ci′ , ∀i, i′ ∈ {1, 2, . . . , |S|}) or heterogeneous (not homogeneous).

Whenever the commodity set is used, the customer must choose between the two payment options to cover the usage cost of each commodity in S. Let δi(j) and γi(j) be the 0-1 decision on commodity si made by the customer at the j th use of the commodity set, where

For any given system, the input can be defined by the total times of use of the commodity set, so the input space is Z+ = {1, 2, 3, . . .}. For any feasible input x ∈ Z+, the cost of any given algorithm ALG is defined as the following:

Please note that for the j th use, it must be covered either by renting of the j th use or buying on or before the j th use.

3.2 Online Environment

In this paper, we assume no prior usage statistics. We apply an adaptive adversary who knows the algorithm taken by the customer, and it can decide whether there will be another use of the commodity set according to history decisions. It is the most general type of adversaries [Boyar et al., 2020].

Conventionally, in this environment, the performance of the customer's commodities acquisition algorithm is measured by the competitive ratio [Karlin et al., 2003]. To introduce this concept, we need to first introduce the offline optimal algorithm which serves as the performance benchmark. For each commodity, the offline optimal algorithm either buys it at the very beginning or rents it forever. Suppose x is the total number of uses chosen by the adversary and is also known by the offline optimal algorithm, the optimal algorithm can simply make decisions by taking the minimum between the renting cost and the buying cost. Formally, let OPT(x, S) be the cost of the offline optimal algorithm that knows x in advance, then we have

The notion of competition ratio is how close the performance of the online algorithm is to the performance of the offline optimal algorithm. As defined by (5), the competitive ratio is the maximum ratio between the online algorithm's cost and the offline optimal algorithm's cost among all possible inputs, which serves as the "worst" case performance guarantee. Since the online algorithm could not perform better than the offline optimal algorithm, R∗ (S) ≥ 1 for all S. The smaller the competitive ratio, the better the online algorithm.

Please note that if we consider all commodities in S as a whole with renting cost d = ∑si∈S di and buying cost c = ∑si∈S ci, the problem can be modeled by the classical ski-rental problem [Karlin et al., 2003]. It has been proved that the best possible competitive ratio for the classical skirental problem against the adaptive adversary approaches to 2. However, this method shrinks the solution space and ignores that the customer utilizes commodities altogether. On the contrary, we allow buying some commodities first while buying others later. In this case, the solution space is larger, and thus we have a chance to obtain a better competitive ratio.

4 MOBE Algorithm

4.1 Preliminaries

Suppose it is the J th time to use the commodity set. We define the typical cost for the commodity si as the following:

σi stands for the rental cost on commodity si until now (the J th usage). For the current usage, we let δi(j) = 1 to calculate the typical cost even though the algorithm has not made any decision.

Let Θ = {θ1, θ2, . . . , θ|S|} be the thresholds for commodities in S where

Whenever the typical cost of commodity si exceeds θi, we buy commodity si. At that time, the algorithm invests ci without incurring any further rental cost on si.

4.2 MOBE Algorithm

Algorithm 1 defines MOBE algorithm formally. The algorithm is awakened when the commodity set is used (Line 1). For each commodity, if it has been brought, then there is no further decision needed (Line 3). Otherwise, the algorithm computes the typical cost for the commodity (Line 4). If the typical cost σi of commodity si reaches θi, the algorithm buys si (Lines 5). Otherwise, when the typical cost is smaller than the threshold, the algorithm covers the payment by renting (Line 6).

MOBE algorithm buys a commodity if it has incurred enough costs by renting, which is defined by the corresponding threshold and measured by the typical cost. The performance of MOBE algorithm relies heavily on the thresholds. Our designed thresholds for MOBE algorithm are calculated by Algorithm 2. Please note that Algorithm 2 further calls Algorithm 3 to search for subsets of thresholds by binary search.

4.3 Discussion on Threshold Solver and Sub-Threshold Solver

To solve the thresholds for commodities, we need to consider two characterizing dimensions: (1) rent-to-buy ratio; (2) buying cost. The rent-to-buy ratio measures the relative price

Algorithm 1: Multi-Object Break-Even (MOBE) input: S = {s1, s2, . . . , sN}, Θ = {θ1, θ2, . . . , θN} (To be computed by Threshold Solver(S)) 1 if the commodity set S is used then 2 for i ← 1 to N do 3 if si has not been brought then 4 compute σi; 5 if σi ≥ θi then buy commodity si; 6 else rent commodity si;

between renting and buying. First, the rent-to-buy ratio influences the decision. For example, we are not urgent to buy a $100 commodity if the rental price is only $1. However, we may have to be decisive if the rental price is raised up to $80 because the cost of renting twice is more expensive than buying. Second, the buying cost influences the decision in another way. Suppose we have two commodities with the same rent-to-buy ratio, and the buying costs are $1 and $100. We tend to buy the cheaper one before the more expensive one because once we buy a commodity, the buying cost becomes our sunk cost, and we are more conservative to a larger sunk cost.

Algorithm 2 solves the thresholds for all S ∈ S. Following the above observation, Algorithm 2 first separates S into mutually exclusive subsets Sj ∀j = 1, 2, . . . , T by descending order of rent-to-buy ratio in Lines 1-2. Then, within each Sj , Algorithm 2 sorts commodities by the ascending order of the buying cost in Line 4.

In Line 7, we call Algorithm 3 to solve thresholds for commodities in each Sj . Please note that all the thresholds of commodities are computed exactly once since ⋃j=1,2,...,T Sj = S and Si ∩ Sj = ϕ ∀i ̸= j.

Define Sr ⊂ S by

Sr is the set of commodity sets where all commodities have the same rent-to-buy ratio. Please note that Sj ∈ Sr, ∀j = 1, 2, . . . , T .

Algorithm 3 is designed to solve sub-problems produced by Algorithm 2. The input is ∀S ∈ Sr, and it computes thresholds by performing a binary search on θ1. First, it initializes the maximum and minimum bounds of θ1 (Lines 12). In the loop, it iteratively computes θ2, θ3, . . . , θN according to the following formula in Line 6:

Algorithm 2: Threshold Solver

• 1 r1, r2, . . . , rT = all T different values of di ci in descending order ∀si ∈ S;

• 3 for j ← 1 to T do
• 4 sort Sj in ascending order of buying cost;

• 6 denote id(j,i) as the index of sji in set S, i.e. sji = sid(j,i);

7

θid(j,1), θid(j,2), . . . , θid(j,M) =

Sub Threshold Solver(Sj );

• 8 return Θ = {θ1, θ2, . . . , θN}

Algorithm 3: Sub Threshold Solver

input : S = {s1, s2, . . . , sN} output: Θ = {θ1, θ2, . . . , θN} 1 θ1,max = c1; 2 θ1,min = 0; 3 while true do 4 θ1 = (θ1,max + θ1,min)/2; 5 for i ← 2 to N do 6 compute θi according to (9); 7 if |θN - cN| < ϵ then break; 8 9 else θ1,min = θ1;

else if θN > cN then θ1,max = θ1; 10 return Θ = {θ1, θ2, . . . , θN}

If θN is close enough to cN , we stop the loop and return the results (Line 7). Otherwise, we update the upper/lower bound (Lines 8-9), and then update θ1 (Line 4) in the next iteration. Please note that the termination condition in Line 7 implies that thresholds are optimal when θN = cN.

5 Performance Analysis

As a specification of (3), we define ALG(x, S, Θ) as the cost of MOBE given input x ∈ Z+ on the commodity set S ∈ S with threshold Θ, and

as the competitive ratio of MOBE on the commodity set S with threshold Θ.

For any given input S ∈ S and the corresponding threshold Θ, we are interested in the competitive ratio R∗ (S,Θ). We have the following theorem to compute it numerically.

Theorem 1. Algorithm 2 solves the numerical competitive ratio for all S ∈ S for MOBE algorithm.

Given Theorem 1, we can compute the competitive ratio before the actual operation, so that we can have a clear expectation of how MOBE performs.

Beyond the numerical competitive ratio of a specific S, we can bound the competitive ratio for all possible commodity sets to develop an explicit frame of what performance we can expect fromMOBE algorithm. To show this bound, we have the following two theorems:

Theorem 2. The competitive ratio of MOBE algorithm is bounded by e

e-1 and 2, i.e. for all commodity sets S ∈ S e-1 , 2].

One step further, we also have Theorem 3 to show that this bound is tight.

It is neutral to see 2 serves as the upper bound, because |S| = 1 is the special case when it is reduced to the classical ski-rental problem and 2 is reached. e e-1 ≈ 1.582 is a neat lower bound of the competitive ratio. This bound is reached when S contains a large number of homogeneous commodities (same di and same ci for all si). When |S| = 10, 20, 50, and 100 (homogeneous commodities), numerical results show the competitive ratios are 1.631, 1.606, 1.592, and 1.587, respectively, approaching e e-1 .

In many real-world cases, the commodities in the commodity set have the same rent-to-buy ratio. For example, rent-tobuy ratios of AWS saving plans for nano, small, medium, and large EC2 are the same [AWS, 2021c]. In that case, there is a need to further investigate the performance of MOBE given the set of commodities with the same rent-to-buy ratio. First, we prove that for all deterministic online algorithms, e e-1 is the lowest possible competitive ratio by Theorem 4.

Theorem 4. ∀S ∈ Sr (same rent-to-buy ratio), e e-1 is the optimal competitive ratio lower bound for any deterministic online algorithm.

Further, we have Theorem 5 to show that the thresholds calculated by Algorithm 2 are optimal for all S ∈ Sr.

Theorem 5. ∀S ∈ Sr Algorithm 2 returns optimal thresholds.

Theorem 5 means that with the special case of S ∈ Sr, our algorithm is the best possible solution, and MOBE algorithm is the optimal algorithm.

In addition to the above performance bounds, an ideal algorithm should solve the problem efficiently. However, solving the competitive ratio can be very costly because the solution space grows exponentially with the number of commodities. We have the following theorem which ensures that Algorithm 2 works in polynomial time.

Theorem 6. Algorithm 2 operates in O(|S|2 ).

6 Evaluation

In this section, we first verify the theoretical performance of MOBE algorithm. Then we conduct a trace-driven experiment to compare the performance with benchmarks.

6.1 Competitive Ratio Verification

Define Sh ⊂ S as the set of all commodity sets with homogeneous commodities, i.e. ∀S ∈ Sh we have di = dj, and ci = cj, ∀si, sj ∈ S.

We show how (9) minimizes the competitive ratio for S ∈ Sh and S ∈ Sr by Fig. 1. In Fig. 1-(a), we adopt 5 homogeneous commodities with d = 1 and c = 100, and in Fig. 1(b), we adopt commodities with renting costs 1, 1.5, 1.5, 2, 3; and 1 100 as the rent-to-buy ratio. In both figures, we can see five peaks in the ratio between the MOBE's cost and the offline optimal algorithm's cost, which are caused by buying commodities as the number of uses grows. (9) ensures all the peaks have the same online/offline cost ratio, so it minimizes the maximum ratio between MOBE algorithm's cost and the optimal cost.

Fig. 2 verifies the numerical competitive ratio for nonuniform rent-to-buy ratio commodities. We demonstrate three groups of experiments by sub-figures (a), (b), and (c), and each group contains four rounds of experiments with different buying costs and rent-to-buy ratios. The yellow bar shows the numerical competitive ratio for MOBE algorithm, and the blue dots show experimental competitive ratios given random inputs. Each yellow bar (one round) contains 50 blue dots (experimental ratios). The detailed experiment parameters are shown in Table 1.

Figure 1: ALG/OPT ratio with different number of uses

As shown in Fig. 2, all the experimental ratios are less or equal to the numerical competitive ratio. All the groups have the experimental ratio equal to the numerical competitive ratio, which shows that the numerical competitive ratio can be reached and the bound is tight. Comparing Group 1 and Group 2, in the case of the same renting price, the more the rent-to-buy ratio tends to be the same, the better the competitive ratio. Comparing Group 1 with Group 3, when the rent-to-buy ratios of the two groups are equal, the more the renting costs within the group tend to be equal, the better the competitive ratio.

6.2 Trace-driven Experiment

In this subsection, we adopt our results in the cloud service acquisition problem with multiple service components (i.e., commodities) with a real-world data set [Kamal, 2019], as described by example 2 in the introduction. Our commodity set implements a flexible fire alarm web application. It consists of service components that aim to provide fire information when a forest fire happens. The web service utilizes the AWS Fargate and AWS SageMaker notebook xlarge serverless technologies. We set three typical configurations for Fargate instances: (1) web server: 8 vCPU and 16 GB memory; (2)

micro service server: 16 vCPU and 32 GB memory; (3) middle ware (e.g. zookeeper, kafka) 8 vCPU and 32 GB memory. The pricing information is given in Table 2 [AWS, 2021b; AWS, 2021a].

We added up the number of forest fires from 2008 to 2011 in the data set and obtained the number of forest fires in each state in 3 years as the input. We assume that our flexible fire alarm system needs to be on duty for 8 hours every time a forest fire occurs.

We conduct the experiment in three groups. Group 1 uses six web servers to simulate a small web application, Group 2 consists of 4 web servers, 8 micro services, and 6 middlewares to emulate a large web application, and Group 3 adds 4 SageMaker notebooks for fire forecasting upon Group 2. In each experiment, we randomly select a state's three-year total number of forest fires from the data set. The results are shown in Fig. 3. We evaluate the following algorithms and benchmarks. (1) OP: the offline optimal algorithm; (2) MB: MOBE algorithm; (3) SR: the classical ski-rental algorithm for each service component; (4) AP: always choose PAYG (rent); (5) AR: always reserve (buy).

The experiment is repeated 100 times for each group, and we add up the total PAYG costs, the total reservation costs, the total number of reserved service components, and the total number of service components that are not reserved.

In all three groups, the accumulated cost of MOBE algorithm is smaller than all online benchmarks. Compared to the classical ski-rental algorithm, MOBE algorithm may reserve a service component when the accumulated PAYG cost is less than its reservation cost, and the performance is improved by this early reservation. The number of service components reserved by the classic ski-rental algorithm and the number reserved by the offline optimal algorithm are always the same. Compared with both of them, MOBE algorithm usually reserves more service components. So the early reservation also brings risks of over-reservation. The power of MOBE algorithm is the ability to balance the under-reservation and the over-reservation. In sum, MOBE algorithm outperforms the benchmarks in the average performance.

7 Conclusion

In this paper, we investigate the multi-commodity ski-rental problem to resolve the dilemma of renting or buying a set of commodities. We address this problem with competitive analysis and extend the results of the classical ski-rental problem. We propose MOBE algorithm to compute the numerical competitive ratio, and show that the tight lower and upper bounds of MOBE algorithm's competitive ratios are e e-1 and 2 respectively. This bound neatly extends the 2 competitive ratio given by the classical ski-rental algorithm. Furthermore, we prove that the competitive ratio is minimized and MOBE is the optimal online algorithm when S ∈ Sr (same rent-to-buy ratio). The MOBE algorithm is also efficient as the threshold values can be derived in O(|S|2 ). Finally, we perform a trace-driven experiment to verify the theoretical competitive ratio and the results show that MOBE algorithm also outperforms benchmarks in terms of the average performance.