# Competitive Analysis for Online Leasing Problem with Compound Interest Rate

Authors: Xingyu Yang; Weiguo Zhang; Weijun Xu; Yong Zhang
Journal: Abstract and Applied Analysis
 (2011)

---

## Abstract

We introduce the compound interest rate into the continuous version of the online leasing problem and discuss the generalized model by competitive analysis. On the one hand, the optimal deterministic strategy and its competitive ratio are obtained; on the other hand, a nearly optimal randomized strategy is constructed and a lower bound for the randomized competitive ratios is proved by Yao's principle. With the help of numerical examples, the theoretical results show that the interest rate puts off the purchase date and diminishes the uncertainty involved in the decision making.


---

## Body

## 1. Introduction

In this paper, we consider the continuous version of the online leasing problem in a market with compound interest rate. In this problem, an online player needs some equipment (e.g., a computer, a car) for an initially unknown amount of time. To use the equipment, he may choose from the following two options: to lease it for a leasing feea per unit of time (the leasing option) or to buy it for a larger amount P (the buying option). Once the player has bought the equipment, he no longer has to pay leasing fees. For each moment that he has not bought the equipment and still needs it, he must decide whether to go on leasing or to buy. The player's goal is to minimize his total cost, including leasing fees and perhaps one purchase fee. The issue of the problem is to determine when to switch from the leasing option to the buying one without the future information.Online leasing problem is one of the fundamental problems in financial decision making and has been widely concerned using the theory of competitive analysis. In the context of competitive analysis, an online algorithm, which has no knowledge of the future events, is measured by the ratio of its performance to the performance of an optimal offline algorithm, which has full knowledge of the future events. Competitive analysis was explicitly formulated by Sleator and Tarjan [1] and then has been extensively used to evaluate and design online algorithms for many online optimization problems arising in computer systems [2–5]. Since financial transactions are often carried out without knowing the future events, it can be said that the nature of most financial problems is inherently online. Therefore, it is natural to extend competitive analysis to study financial games [6], such as portfolio selections [7], replacement problems [8], Bahncard problem [9], and one-way trading [10].Now, we illustrate the theory of competitive analysis using the cost minimization problem. Letℐ denote the set of all the inputs for the problem and A an online algorithm. For a given input I, denote by Coston(I;A) and Costoff(I) the costs incurred by A and an optimal offline algorithm, respectively. Online algorithm A is called (strictly) c-competitive if, for each input I,
(1.1)Coston⁡(I;A)≤c⋅Costoff⁡(I).
Thus, a c-competitive algorithm guarantees that its cost is not more than c times the cost incurred by an optimal offline algorithm on each input. The smallest c such that A is c-competitive is called A’s competitive ratio, denoted by cA. The smaller the competitive ratio, the better the algorithm. The smallest one is called the optimal competitive ratio, and an algorithm achieving the optimal competitive ratio is called an optimal competitive algorithm.From the definitions above, we have that(1.2)cA=sup⁡I∈ICoston⁡(I;A)Costoff⁡(I).
It can be seen that an online algorithm is adjudged good only if it performs well compared with an optimal offline algorithm on each input. Therefore, competitive ratio is a worst case performance measure. It is sometimes convenient to view an online problem as a two-person zero-sum game. The first player is the online player, whose payoff is defined as the reciprocal of the competitive ratio for the online algorithm he adopts, and the adversary is the optimal offline player, whose payoff is defined as the respective (additive) inverse of the online player's payoff [11]. In this game, the online player adopts some online algorithm and makes it known to the adversary, and then the adversary chooses an input so as to make the competitive ratio as large as possible. The online player's objective is to minimize the competitive ratio. In the above analysis, the adversary knows the online player's exact action before the game begins. Therefore, it is often criticized as the adversary possesses too much power, while the online player has too little power. Randomization is often used to offer the online player significantly more power and improve his performance. A randomized online algorithm can be defined as a probability distribution on the set consisted of all deterministic algorithms. Various adversary models have been defined in the context of randomized algorithms, and in this paper we only concern the model of the oblivious adversary, which is the most usual. For other types of adversary such as adaptive online adversary and adaptive offline adversary, we refer the readers to [12]. An oblivious adversary knows the probability distribution of the randomized algorithm but does not know which action the online player will adopt exactly, and he must predetermine the input before the game begins and pays for it optimally. That is, he is oblivious to the random choices made by the online player. The competitive ratio for randomized algorithm A with respect to an oblivious adversary is defined the same as (1.1) with Coston(I;A) replaced by E[Coston(I;A)], which is the expected value of A's cost on input I.The online leasing problem has been investigated by many authors [13–15]. For the continuous version, the optimal deterministic and randomized competitive ratios are 2 and e/(e-1)≈1.582, respectively [2, 3]. When considering alternative financial decisions, an agent must consider their net present value. That is, accounting for the market interest rate is an essential feature of any reasonable financial model. El-Yaniv et al. [13] introduced the market interest rate into the discrete model and obtained the optimal deterministic and randomized competitive ratios. However, there are no results on the continuous version of the online leasing problem with interest rate. Naturally, we introduce the compound interest rate into the continuous version of the leasing problem. In this paper, we pursuit optimal deterministic and randomized strategies for the generalized model.The rest of this paper is arranged as follows. In Section2, we prove the optimal deterministic strategy and its competitive ratio. In Section 3, we construct a nearly optimal randomized strategy. In Section 4, we obtain a lower bound for the randomized competitive ratios. In Section 5, we analyze the results thanks to numerical examples. Section 6 concludes this paper.


## 2. Deterministic Strategy

In this section, we introduce the compound interest rate in the market into the traditional online leasing problem of continuous version and discuss its optimal deterministic strategy and optimal competitive ratio.Leti>0 be the compound interest rate in the market. Then, the future value of the starting principal A at time t is Aeit. Alternatively, the net present value of A units of money transferred at time t is Ae-it. Remind that a denotes the leasing fee per unit of time and P the purchase fee. Set k=P/a. Suppose that the online player continuously uses the equipment for some time and then never uses it again. Without loss of generality, we assume that the cost of purchasing initially is less than the cost of leasing forever; that is,
(2.1)P<∫0∞ae-isds=ai.
Otherwise, the player can attain a competitive ratio of 1 just by taking the strategy of leasing all the time. From (2.1), we obtain that ki<1.The net present value of leasing forT units of time is
(2.2)∫0Tae-isds=ai(1-e-iT).
The net present value of leasing for t units of time followed by a purchase is
(2.3)∫0tae-isds+Pe-it=ai(1-e-it)+Pe-it.Fromki<1, we obtain
(2.4)P<∫0tae-isds+Pe-it,
for all t>0, which indicates that the offline player will never take the strategy of purchasing the equipment after leasing it for some time. Therefore, the offline player either buys the equipment in the beginning or leases all the time until he never uses it again.Suppose thatT* is the root of the following equation:
(2.5)ai(1-e-iT)=P,
then
(2.6)T*=1iln⁡11-ki.WhenT<T*, the offline player will lease all the time, incurring a cost of (a/i)(1-e-iT). Otherwise, he will buy in the beginning, incurring a cost of P. Therefore, the cost of the optimal offline strategy is
(2.7)Costoff⁡(T)={ai(1-e-iT),T<T*,P,T≥T*.
The online player has no knowledge of T. Denote by S(t) the strategy that the online player will lease for t units of time and then buy. The cost of the online strategy is
(2.8)Coston⁡(T;t)={ai(1-e-iT),T<t,Pe-it+ai(1-e-it),T≥t.Based on competitive analysis, we can obtain the optimal deterministic strategy and its competitive ratio.Theorem 2.1.
For the online leasing problem in a market with compound interest ratei>0, the optimal deterministic strategy is  S(T*): if  T<T*, then always lease; otherwise, lease for  T* units of time and then buy, where  T* is defined in  (2.6). Moreover, the optimal deterministic competitive ratio is  2-ki.Proof.
We prove the theorem by worst-case analysis. The worst case for the problem is that the offline player ends the game immediately when the online player buys the equipment. That is, the inputT is slightly larger than t. We split the analysis into two cases: t<T* and t≥T*.
Case 1.
t<T*. In this case, the worst input T belongs to (t,T*). Hence, the optimal offline strategy will always lease and thus the offline cost is (a/i)(1-e-iT), while the online strategy S(t) will lease first and then buy at time t, incurring a cost of Pe-it+(a/i)(1-e-it). Thus, in this case, the competitive ratio for S(t) is
(2.9)c(t)=sup⁡t<T<T*Coston⁡(T;t)Costoff⁡(T)=sup⁡t<T<T*Pe-it+(a/i)(1-e-it)(a/i)(1-e-iT)=1+ki1eit-1.Case 2.
t≥T*. In this case, the worst input T belongs to (t,∞). Hence, the optimal offline player will buy the equipment in the beginning and thus the offline cost is P, while online strategy S(t) will still lease first and then buy at time t, incurring the same cost of Pe-it+(a/i)(1-e-it). Thus, in this case, the competitive ratio for S(t) is
(2.10)c(t)=sup⁡T>tCoston⁡(T;t)Costoff⁡(T)=sup⁡T>tPe-it+(a/i)(1-e-it)P=1ki+(1-1ki)e-it.
Noticing ki<1, c(·) decreases in (0,T*) and increases in [T*,∞) and thus it attains its infimum at t=T*. Therefore, the optimal competitive ratio is
(2.11)c(T*)=2-ki.
The corresponding optimal strategy is S(T*).Remark 2.2.
Notice thatT*→k and 2-ki→2, as i→0. Therefore, for the online leasing problem in a market without interest rate, the optimal deterministic competitive strategy is S(k) and its competitive ratio is 2, which coincides with the previous results [2].


## 3. A Randomized Strategy

In this section, we aim to construct a randomized competitive strategy, which is illustrated to be nearly optimal later. Letp={p(t)}t≥0 be a randomized strategy, where p(t) is the probability that the online player has bought the equipment until time t. Then, 1-p(t) is the probability that the online player has not bought the equipment until time t. And we have that p(·) increases with time t and p(0)=0.On the time interval[t,t+dt], the leasing fee is ae-it(1-p(t))dt and the purchase fee is Pe-itp′(t)dt and thus the total fee of randomized strategy p until time T is
(3.1)Coston⁡(T;p)=∫0T[ae-it(1-p(t))+Pe-itp′(t)]dt.
In the following, we plan to construct a randomized strategy p, such that
(3.2)Coston⁡(T;p)=c⋅Costoff⁡(T),
for all T>0, where c is a constant to be determined.WhenT<T*, (3.2) is
(3.3)∫0T[ae-it(1-p(t))+Pe-itp′(t)]dt=c⋅ai(1-e-iT).Differentiating (3.3), we have
(3.4)ae-it(1-p(t))+Pe-itp′(t)=c⋅ae-it;
that is,
(3.5)p′(t)=1kp(t)+c-1k.
Solving (3.5) with initial condition p(0)=0 by the method of constant variation, we get
(3.6)p(t)=(c-1)et/k-(c-1),0≤t<T*.
In particular,
(3.7)p(T*)=(c-1)eT*/k-(c-1).WhenT≥T*, (3.2) is
(3.8)∫0T[ae-it(1-p(t))+Pe-itp′(t)]dt=c⋅P.
Similarly, solving (3.8) with initial condition (3.7), we get
(3.9)p(t)=[(c-1)-ce-T*/k]et/k+1,t≥T*.
On the one hand, since p(·) increases on [0,∞), we have (c-1)-ce-T*/k≥0; on the other hand, since p(t)≤1 for all t≥T*, we have (c-1)-ce-T*/k≤0. Therefore, (c-1)-ce-T*/k=0; that is,
(3.10)c=eT*/keT*/k-1=e(1/ki)ln⁡(1/(1-ki))e(1/ki)ln⁡(1/(1-ki))-1.Now we have constructed a randomized strategyp={p(t)}t≥0 satisfying (3.2), where
(3.11)p(t)={et/k-1eT*/k-1,t<T*,1,t≥T*,
and its competitive ratio is given by (3.10). The strategy p with i=0 and 0.03 is exhibited in Figure 1.Figure 1
The effect of the interest ratei on the randomized strategy p.


## 4. A Lower Bound for the Randomized Competitive Ratios

In this section, we pursuit the lower bound for the randomized competitive ratios by Yao's principle (see, e.g., [11]). To obtain the lower bound of c, it is sufficient to choose any probability distribution F over inputs and show that the ratio of the expected cost (in respect to F) of any online deterministic strategy to that of an optimal offline strategy is bounded from below by c. Consider the input T as a random variable, and assume that F is any distribution of T. By Yao's principle, the competitive ratio for any randomized strategy p satisfies
(4.1)c(p)≥inf⁡t≥0EF[Coston⁡(⋅;t)]EF[Costoff⁡(⋅)],
where EF[Coston(·;t)] and EF[Costoff(·)] denote the expected costs of online strategy S(t) and an optimal offline strategy, respectively. The issue is to construct a probability distribution F to make the right-hand-side of (4.1) as large as possible.Theorem 4.1.
For the leasing problem in a market with compound interest ratei>0, a lower bound for the randomized competitive ratios is
(4.2)e(1/ki)ln⁡(1/(1-ki))+ki(1-ki)e(1/ki)ln⁡(1/(1-ki))-1+ki.Proof.
Construct a probability distribution over inputs as follows:(4.3)F(T)={1-1eT/k,0<T<T*,1-e-(1/ki)ln⁡(1/(1-ki)),T*≤T<2T*,1,T≥2T*,
which is of mixed type. It is of continuous type in (0,T*], and its density function is
(4.4)f(T)=1ke-T/k,0<T≤T*,
while it is of discrete type at T=2T* and the probability that T takes value 2T* is e-(1/ki)ln(1/(1-ki)). Therefore, the expected cost of the optimal offline strategy is
(4.5)EF[Costoff⁡(⋅)]=∫0T*ai(1-e-iT)1ke-T/kdT+Pe-(1/ki)ln⁡(1/(1-ki))=ai(1-e-(1/ki)ln⁡(1/(1-ki)))-ai(1+ki)(1-e-(1+1/ki)ln⁡(1/(1-ki)))+Pe-(1/ki)ln⁡(1/(1-ki))=P1+ki-a(1-ki)i(1+ki)e-(1/ki)ln⁡(1/(1-ki))+Pe-(1/ki)ln⁡(1/(1-ki))=P1+ki-2P1+kie-(1/ki)ln⁡(1/(1-ki))+Pe-(1/ki)ln⁡(1/(1-ki))=P1+ki(1-(1-ki)e-(1/ki)ln⁡(1/(1-ki))).
In the following, we compute the expected cost of online strategy S(t) in three cases.
Case 1.
0≤t≤T*. In this case, the expected cost of online strategy S(t) is
(4.6)EF[Coston⁡(⋅;t)]=∫0tai(1-e-iT)1ke-T/kdT+∫tT*[Pe-it+ai(1-e-it)]1ke-T/kdT+[Pe-it+ai(1-e-it)]e-(1/ki)ln⁡(1/(1-ki))=ai(1-e-t/k)-ai(1+ki)(1-e-(i+1/k)t)+[Pe-it+ai(1-e-it)][e-t/k-e-(1/ki)ln⁡(1/(1-ki))]+[Pe-it+ai(1-e-it)]e-(1/ki)ln⁡(1/(1-ki))=P1+ki+Pki1+kie-(i+1/k)t≥P1+ki[1+kie-(i+1/k)T*]=P1+ki(1+ki(1-ki)e-(1/ki)ln⁡(1/(1-ki))).Case 2.
T*<t<2T*. In this case, the expected cost of online strategy S(t) is
(4.7)EF[Coston⁡(⋅;t)]=∫0T*ai(1-e-iT)1ke-T/kdT+[Pe-it+ai(1-e-it)]e-(1/ki)ln⁡(1/(1-ki))=P1+ki-2P1+kie-(1/ki)ln⁡(1/(1-ki))+[(P-ai)e-it+ai]e-(1/ki)ln⁡(1/(1-ki))≥P1+ki-2P1+kie-(1/ki)ln⁡(1/(1-ki))+[(P-ai)e-iT*+ai]e-(1/ki)ln⁡(1/(1-ki))=P1+ki(1+ki(1-ki)e-(1/ki)ln⁡(1/(1-ki))),
where the inequality is owed to ki<1.Case 3.
t≥2T*. In this case, the expected cost of online strategy S(t) is
(4.8)EF[Coston⁡(⋅;t)]=∫0T*ai(1-e-iT)1ke-T/kdT+ai(1-e-2iT*)e-(1/ki)ln⁡(1/(1-ki))=P1+ki-2P1+kie-(1/ki)ln⁡(1/(1-ki))+ai(1-(1-ki)2)e-(1/ki)ln⁡(1/(1-ki))=P1+ki+Pki(1-ki)1+kie-(1/ki)ln⁡(1/(1-ki))=P1+ki(1+ki(1-ki)e-(1/ki)ln⁡(1/(1-ki))).
Therefore, the competitive ratio for any randomized strategy satisfies
(4.9)c(p)≥inf⁡t≥0EF[Coston⁡(⋅;t)]EF[Costoff⁡(⋅)]=(P/(1+ki))(1+ki(1-ki)e-(1/ki)ln⁡(1/(1-ki)))(P/(1+ki))(1-(1-ki)e-(1/ki)ln⁡(1/(1-ki)))=e(1/ki)ln⁡(1/(1-ki))+ki(1-ki)e(1/ki)ln⁡(1/(1-ki))-1+ki.Remark 4.2.
It naturally holds that the lower bound for the competitive ratios is less than the upper bound obtained in Section3; that is,
(4.10)e(1/ki)ln⁡(1/(1-ki))+ki(1-ki)e(1/ki)ln⁡(1/(1-ki))-1+ki<e(1/ki)ln⁡(1/(1-ki))e(1/ki)ln⁡(1/(1-ki))-1<ee-1,
for i∈(0,1/k), which can be verified by direct calculation.Remark 4.3.
As the interest rate tends to 0, the lower and upper bounds for the randomized competitive ratios tend to the same limit; that is,(4.11)lim⁡i→0e(1/ki)ln⁡(1/(1-ki))+ki(1-ki)e(1/ki)ln⁡(1/(1-ki))-1+ki=lim⁡i→0e(1/ki)ln⁡(1/(1-ki))e(1/ki)ln⁡(1/(1-ki))-1=ee-1.
That is, when i=0, the limit e/(e-1) is just the optimal randomized competitive ratio, and the corresponding randomized strategy is
(4.12)p(t)={et/k-1e-1,t<k,1,t≥k.


## 5. Numerical Analysis

In this section, we provide some numerical examples for exploiting the effect of the interest ratei on the competitive strategies and competitive ratios we obtained above. Assume P=10000,a=1000, and thus k=10. Denote the optimal deterministic competitive ratio, the upper and lower bounds for the randomized competitive ratios by cdet, cup and clow, respectively; that is,
(5.1)cdet⁡=2-ki,cup=e(1/ki)ln⁡(1/(1-ki))e(1/ki)ln⁡(1/(1-ki))-1,clow=e(1/ki)ln⁡(1/(1-ki))+ki(1-ki)e(1/ki)ln⁡(1/(1-ki))-1+ki.First, we consider the effect of the interest rate on deterministic and randomized strategies. In Table1, we can see that the larger i is, the larger T* is. In fact, T* increases with i, which can be derived from (2.6). In Figure 1, we can see that, for fixed time t, the larger i is, the smaller p(t) is. In fact, p(t) decreases with i. We can conclude that the interest rate puts off the purchase dates of both the optimal deterministic strategy and the randomized strategy we obtained above. The reason is that it may be worthwhile to delay a purchase and increase the value of the capital over time in a market with interest rate.Table 1
Values ofT*,cdet,cup,clow for different i’s (P=10000,a=1000).
iT*cdetcupclow010.02.01.5821.5820.0110.51.91.5351.5030.0211.21.81.4811.4260.0311.91.71.4381.3520.0412.81.61.3871.2810.0513.91.51.3331.214Next, we consider the effect of the interest rate on competitive ratios. In Table1, we see that the larger i is, the smaller cdet,cup, and clow are. In fact, by direct calculation, we have that cdet,cup, and clow all decrease with i. It indicates that the interest rate diminishes the uncertainty involved in online decision making. If i=0, then we have cup=clow, which is exactly the optimal randomized competitive ratio. Even if i>0, there is no evident difference between cup and clow. So, we can say that the randomized competitive strategy we obtained in Section 3 is nearly optimal. For example, when i=0.03, the percentage of the achieved competitive ratio cup beyond the optimal one is not more than (1.438-1.352)/1.352≈6.361%.


## 6. Conclusions

In this paper, we have generalized the continuous version of the online leasing problem by introducing the compound interest rate. On the one hand, we obtained the optimal deterministic strategy and its competitive ratio; on the other hand, we constructed a nearly optimal randomized strategy and obtained a lower bound for the randomized competitive ratios. Moreover, thanks to numerical examples, we realized that the market interest rate postpones the purchase date and diminishes the uncertainty involved in the decision making. However, we fail to obtain the optimal randomized competitive ratio but its upper and lower bounds. We conjecture that the randomized competitive strategy we have obtained is exactly optimal, which will be verified in our future research.



---

*Source: 156254-2011-09-04.xml*