Research Article

# Competitive Analysis of Two Special Bahncard Replacement Problem

Lili Ding, Xinmin Liu and Wanglin Kang

ABSTRACT

This study provides a new competitive analysis framework for the Bahncard problem through introducing the two-stage discount rate and the risk management. For the online decision-makers, who have not any information about future demand, a new online algorithm is present to help them choose an optimal replacement strategy. Furthermore, when the online decision-makers are willing to increase their risk for some reward, an optimal online risk algorithm is developed, which help them manage risk based on their risk tolerance and forecast.

 Services Related Articles in ASCI Similar Articles in this Journal Search in Google Scholar View Citation Report Citation Science Alert

 How to cite this article: Lili Ding, Xinmin Liu and Wanglin Kang, 2009. Competitive Analysis of Two Special Bahncard Replacement Problem. Journal of Applied Sciences, 9: 1185-1189. DOI: 10.3923/jas.2009.1185.1189 URL: https://scialert.net/abstract/?doi=jas.2009.1185.1189

INTRODUCTION

Suppose that there is a discount card, which costs C and entitles its holder to β price reduction of goods for the time of T. For the common decision-maker, the decision at which time to buy a discount card is a typical online problem, because he usually does not know when to go shopping and how many he will buy. This problem, called the Bahncard problem, was proposed by Fleischer (2001) in the computer science field. In his study two optimal deterministic online algorithms which achieve an optimal competitive ratio of 2-β were present. Fujiwara and Iwama (2005) integrated a possibility distribution assumption into the traditional competitive analysis, where they assume that the input sequences were subject to an exponential distribution. Ding et al. (2005) pointed out that the decision-maker was often confronted with the interest rate, which may be an essential feature of any reasonable economic models and gave the optimal deterministic online algorithm. The above Bahncard problem has various interesting applications. In all of these applications the basic question is when to switch from one activity to another more rewarding one. For example, when β = 0 and the rental is equal, the Bahncard problem is of course precisely Ski-rental problem. There are many extensible researches for this problem. Karlin et al. (2003) gave a randomized algorithm with a competitive ratio of e/e-1. Xu et al. (2007) considered the discrete and continuous model, respectively and present the optimal strategies. If the discount rate becomes the weight of packets, then this problem also can be considered as the TCP problem. Albers and Bals (2003) investigated a new objective function for TCP problem and achieve a deterministic 1.644-competitive online algorithm. Edmonds et al. (2003) present the competitive analysis against limited adversary and gave the optimal competitive ratios of some special cases.

A systematic study of online algorithms was given by Sleator and Tarjan (1985), who compared the performance of an online algorithm with that of an optimal offline algorithm. Karlin et al. (1988) introduced the notion of a competitive ratio. Note that the use of the competitive ratio for the evaluation of online algorithm is called competitive analysis. An online algorithm is said to be r-competitive (r≥1), if, given any instance of the problem denoted by σ, the cost of the solution given by the online algorithm is no more than r multiplied by that of an optimal offline algorithm: Costonline (σ)≤ r Costoptimal (σ). The infimum over all r such that an online algorithm is r-competitive is called the competitive ratio of the online algorithm. An online algorithm is said to be best-possible if there does not exist another online algorithm with a strictly smaller competitive ratio.

In this study, our purpose is to improve the performance measurement of competitive analysis to allow the decision-maker to provide and benefit from a forecast but also allow him to control his risk of performing too poorly. In addition to providing more realism, the introduction of this advanced information is a natural mechanism to increase the power of online decision-maker against all-knowing adversaries in a competitive analysis framework. Note, also, that these risk behaviors provide a natural bridge between online Bahncard problems and their offline versions. It is found that with the introduction of competitive risk analysis, the valuable information in decision-making helps the optimal purchasing chance advance as long as the input sequences confirm to the forecast.

COMPETITIVE ANALYSIS WITHOUT RISK

In this study we propose a two-stage Bahncard replacement model that is motivated by the more complex decision in the real life. For example, the Swiss Federal Railways offers two kinds of Half-Fare cards (cost CHF 150 and CHF 250, respectively) with different discount rates to attract more travelers. Suppose that the online decision-maker wishes to buy a new Bahncard B2 with a greater discount of β2, after he has hold a Bahncard B1 with a smaller discount of β1. However, the greater discount, the more cost of a Bahncard. One has to decide whether and when to buy this more expensive Bahncard based on his owning information.

Optimal offline algorithm: An optimal offline algorithm which knows the entire shopping requests is evident, due to the following observation:

Let σ be a shopping request sequence and OPT be an optimal algorithm for σ. Then we can assume that (a) Never buy the first Bahncard B1 at a discount request. (b) OPT buys the second Bahncard B2 either immediately or never.

Proof: (a) At a discount request with discount rate β1, OPT would postpone purchasing the same card until it expires without the coming of B2. At a discount request with discount rate β2, OPT would never buy B1 for β21.

(b) Assume that OPT buys the second Bahncard with the cost of C2 at time T. It is clear that β21, otherwise there is no reason to buy B2. But it would be advantageous to buy B2 more early, because the price C2 is the same and β12 discount cost of shopping could be saved. This contradicts optimality.

Let R1 be the accumulative regular cost after purchasing the first Bahncard. Suppose that R2 denotes the total regular cost after Bahncard B2 is issued. According to the observation, the optimal offline cost is

 (1)

where, Rcrit = (C212) is the critical cost before to buy the second B2 and the break-even point for any algorithm.

Optimal online algorithm: In reality, there are two common algorithms for the decision-makers. One is never to buy the second Bahncard. However, such Never-buy Algorithm has the competitive ratio of β12. The other is immediately to buy B2 only if it appears, denoted by the Immediately-buy Algorithm. It is evidenced that the competitive ratio of the Immediately-buy Algorithm is C2. Both of these two algorithms can not safeguard against a sequence of several expensive requests or cheap ones, respectively. We consider the following online strategy, hereafter called the critical-sum-shopping (CSS) algorithm.

Algorithm CSS

 • Set the critical total regular cost to be after the appearance of B2 • If R2<, then decision-maker never buys B2 • If R2≥, then he waits the total regular cost up to and buys one

We now show how the optimal algorithm CSS can be derived. Let ALG be the any online algorithm and rALG be the competitive ratio of ALG. The optimal competitive ratio for an online problem is r* = infALG (rALG). The following proposition generates the optimal competitive ratio and the optimal online strategy.

Proposition: The optimal competitive ratio obtained by algorithm CSS is:

Proof: Without loss of generality, assume that the Bahncard B2 is available at time t. Suppose that the decision-maker does not buy the second Bahncard until the total regular cost after t is equal to . Thus, ALG pays:

 (2)

For some <Rcrit and consider online algorithm ALG. It is clear that the optimal choice by the offline decision-maker against ALG would not buy B2. For this instance, the competitive ratio (online/offline) is:

 (3)

Note that which is always negative. Therefore, the online decision-maker will take the maximum possible value of , such that = Rcrit. The offline decision-maker would input such shopping request sequences that R2- = 0 to make the online decision-maker in the worst case. Having assumed ε to be an arbitrarily small constant and = Rcrit-ε. We obtain:

 (4)

Next we consider ALG with ≥Rcrit. There are two mutually exclusive cases.

In the first case, if the choice of R2 is such that R2< , then for R2<Rcrit the online and offline costs are equal and achieve the competitive ratio of 1. For any other choice of R2 with Rcrit<R2< , the online ALG will not buy B2, incurring a cost of C11 (R1+R2). Without loss of generality, assume that R2 = -ε. Thus, for this case the best attainable cost ratio is:

 (5)

In the second case, the offline decision-maker chooses R2. Without loss of generality assume that R2 = . Thus, the best attainable ratio for this case is:

 (6)

It is found that r3 = r2. Therefore, the offline decision-maker will choose R2 = , enforcing the larger ratio of r3. We can get derivatives . It follows that r3 is a increasing function of . Therefore, for this case, the best attainable ratio is obtained by setting = Rcrit. Thus, we obtain:

 (7)

Based on the above analysis, it is evident that r1>r3. Hence, the online decision-maker chooses = Rcrit and the best attainable competitive ratio is r3, which is achieved by the optimal algorithm CSS. Namely, if at some time is at least Rcrit, then the decision-maker buys the second Bahncard; otherwise, never buys B2.

Proposition: The optimal competitive ratio obtained is 2-(β21), when η→0.

Proof: Set C11R1 = η. when η→0, substituting η into the function of r3 and the optimal competitive ratio is at most 2-(β21). This analysis provides a smooth generalization of Fleischer’s results, which are the special cases obtained with β1 = 1.

COMPETITIVE ANALYSIS WITH RISK

The above competitive analysis is the most fundamental and significant approach, yet it has been criticized as making too conservative assumption about future input sequences. Especially in the economic issues, many decision-makers do not seek to minimize risk, but to manage it. MacCrimmon et al. (1986) introduce a basic risk paradigm as the basis for studying risk. Al-Binali (1999) takes a risk by assuming that input sequence will obey some constraints. We provide the following online risk algorithm displayed in their manners.

Online risk algorithm: Given any online deterministic algorithm ALG, define the risk of ALG to be Risk (ALG) = rALG/r* and a forecast be F as any subset of the allowable input sequences. It is clear that the risk of any online algorithm is ≥1 and the lower the risk is, the better its performance guarantees. Next, define a forecast denoted by F as any subset of the allowable input sequences. The online decision-maker specifies a risk tolerance λ. This means that the decision-maker is willing to use the restricted algorithms in ξ = {ALG: Risk (ALG)≤λ}. Each of the algorithms in ξ thus has a competitive ratio of at most λr*. Fix any forecast F. An optimal risk algorithm, according to this risk management framework, is an algorithm from ξ that minimizes the competitive ratio, restricted to input sequences from F. Formally, the restricted competitive ratio of any online risk algorithm can be parameterized by the constrains of the total input sequences from F such that:

 (8)

Thus, the optimal restricted competitive ratio by ALG* with respect to a forecast F can be achieved from:

The reward of the optimal online risk algorithm ALG* denoted by gALG is measured by the ratio of the optimal competitive ratio to the restricted ratio. The optimal risk algorithm ALG* with respect to a forecast F satisfies:

 (9)

The steps to use this algorithm can be described as follows:

 Step 1: Initialize the forecast, σεF Step 2: Set the risk tolerance level to be λ Step 3: According to definition of Eq. 8, compute the restricted competitive ratio ALG, where ALGεξ and ξ = {ALG: Risk (ALG)≤λ} Step 4: Compare the restricted competitive ratio with the optimal competitive ratio and achieve the reward gALG Step 5: Solve the model Eq. 9 to obtain the optimal online risk algorithm ALG*

We analyze two-stage Bahncard problem in the competitive risk analysis framework based on the two possible forecasts of R2<Rcrit and R2≥Rcrit. For the case of R2<Rcrit, the two-stage Bahncard problem has the optimal competitive ratio such that * = 1. It is because that both the offline and online decision-maker will never purchase the second Bahncard with this forecast. For the case of R2≥Rcrit, we present the following strategy:

Optimal risk tolerance strategy: Given η, λ, a new Bahncard B2 and a forecast of R2≥Rcrit, the online decision-maker would not buy B2 until the total regular cost of is up to:

otherwise, never purchase B2.

We present the following proposition to show that the risk tolerance strategy is optimal according to the above analysis. The result shows that the introduction of forecast improves the competitive analysis performance of the algorithm CSS, if R2≥Rcrit is correct.

Proposition: If the forecast of R2≥Rcrit is correct, the optimal restricted competitive is:

Proof: If R2≥Rcrit is correct, then the online decision-maker would choose an optimal risk algorithm from ξ to obtain the more reward based on his tolerance. The offline decision-maker would buy the second Bahncard as soon as it appears. Therefore, the restricted competitive ratio of the online risk algorithm is:

 (10)

Since, we want to minimize , we want R2 as small as possible subject to ≤λr3 from the following two cases.

Case 1: R2<Rcrit According to the preceding risk definition, the online decision-maker can obtain the inequality:

If C2-(λr3-1)η>0, then we obtain:

 (11)

Case 2: R2≥Rcrit. It is shown that the restricted competitive ratio in the false forecast satisfies:

from the above competitive risk analysis framework. Thus we get the following result:

 (12)

For the online decision-maker, he knows the function of in case 2 is monotonically increasing with . The less , the smaller .Therefore, substituting the lower bound of Eq. 11 into the function of restricted competitive ratio, we obtain the optimal restricted competitive ratio.

Proposition: The optimal restricted competitive ratio is at most:

for η→0.

NUMERICAL EXAMPLE

In general, it is shown that competitive risk analysis can improve the decision-maker’s performance significantly. We provide the numerical examples to develop a more intuitive understanding about present analysis and the effect on the competitive ratio when the parameters in this model are varying.

In Table 1, the numerical matters are about the two kinds of Half-Fare cards problem offered by Swiss Federal Railways. Set C1 = 150 CHF, β1 = 80% and C2 = 250 CHF, β2 = 50%. According the above results, the optimal deterministic online algorithm CSS chooses the total regular cost of up to 833 CHF to buy the second card and obtain the competitive ratio of 1.375. Using the optimal risk tolerance strategy, the traveler can benefit from his correct forecast to achieve the less ratio of 1.2654 based on λ = 1.10.

 Table 1: Values of (β1, β2) for different combinations

It means if the traveler would take a risk of achieving ratio of 1% larger than optimal one, then he can get a performance improvement of about 57%. It is also found that r* decreases with β2 and increases with β1.

CONCLUSIONS

The classical competitive analysis is the most fundamental and important approach to study online problems. But it is not very flexible since it avoids making assumptions about future inputs. In this study, we provide an online risk algorithm, which allows the decision-makers to manage their risk and utilize their forecasts. But how to improve the performance of the competitive algorithm by other methods, such as probability statistics, is a direction. Another direction is the competitive analysis about more discount activities, for example three or more discount cards.

REFERENCES
1:  Albers, S. and H. Bals, 2003. Dynamic TCP acknowledgement: Penalizing long delays. Proceedings of the 14th Annual ACM-SIAM symposium on Discrete Algorithms, January 12-14, 2003, Philadelphia, PA., USA., pp: 47-55.

2:  Al-Binali, S., 1999. A risk-reward framework for the competitive analysis of financial games. Algorithmica, 25: 99-115.

3:  Ding, L.L., Y.F. Xu and S.H. Hu, 2005. The Bahncard Problem with Interest Rate and Risk. In: Internet and Network Economics, Xiaotie, D. and Y. Yinyu (Eds.). Springer-Verlag, Germany, Berlin, Heidelberg, ISBN: 978-3-540-30900-0, pp:307-314.

4:  Edmonds, J., S. Datta and P. Dymond, 2003. TCP is competitive against a limited adversary. Proceedings of the 15h Annual ACM Symposium on Parallel Algorithms and Architectures, June 7-9, 2003, ACM, New York, USA., pp:174-183.

5:  Fleischer, R., 2001. On the bahncard problem. Theor. Comput. Sci., 268: 161-174.

6:  Fujiwara, H. and K. Iwama, 2005. Average-case competitive analysis for ski-rental problems. Algorithmica, 42: 95-107.

7:  Karlin, A., M. Manasse, L. Rudolph and D. Sleator, 1988. Competitive snoopy caching. Algorithmica, 3: 79-119.