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 decisionmaker,
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 decisionmaker
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 Skirental problem. There
are many extensible researches for this problem. Karlin et
al. (2003) gave a randomized algorithm with a competitive ratio of e/e1.
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.644competitive 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 rcompetitive (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: Cost_{online} (σ)≤ r Cost_{optimal} (σ).
The infimum over all r such that an online algorithm is rcompetitive is called
the competitive ratio of the online algorithm. An online algorithm is said to
be bestpossible 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 decisionmaker 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 decisionmaker against allknowing
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 decisionmaking 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 twostage 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 HalfFare cards (cost CHF 150 and CHF 250, respectively) with different discount rates to attract more travelers. Suppose that the online decisionmaker wishes to buy a new Bahncard B_{2} with a greater discount of β_{2}, after he has hold a Bahncard B_{1} 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 B_{1} at a discount request. (b) OPT buys the second Bahncard B_{2} 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 B_{2}. At a discount request with discount rate β_{2}, OPT would never buy B_{1} for β_{2}<β_{1}.
(b) Assume that OPT buys the second Bahncard with the cost of C_{2} at time T. It is clear that β_{2}<β_{1}, otherwise there is no reason to buy B_{2}. But it would be advantageous to buy B_{2} more early, because the price C_{2} is the same and β_{1}β_{2} discount cost of shopping could be saved. This contradicts optimality.
Let R_{1} be the accumulative regular cost after purchasing the first
Bahncard. Suppose that R_{2} denotes the total regular cost after Bahncard
B_{2} is issued. According to the observation, the optimal offline cost
is
where, R_{crit} = (C_{2}/β_{1}β_{2})
is the critical cost before to buy the second B_{2} and the breakeven
point for any algorithm.
Optimal online algorithm: In reality, there are two common algorithms
for the decisionmakers. One is never to buy the second Bahncard. However, such
Neverbuy Algorithm has the competitive ratio of β_{1}/β_{2}.
The other is immediately to buy B_{2} only if it appears, denoted by
the Immediatelybuy Algorithm. It is evidenced that the competitive ratio of
the Immediatelybuy Algorithm is C_{2}. 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 criticalsumshopping (CSS) algorithm.
Algorithm CSS
• 
Set the critical total regular cost to be after
the appearance of B_{2} 
• 
If R_{2}<,
then decisionmaker never buys B_{2} 
• 
If R_{2}≥,
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 r_{ALG} be the competitive ratio of ALG. The optimal
competitive ratio for an online problem is r* = inf_{ALG} (r_{ALG}).
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 B_{2}
is available at time t. Suppose that the decisionmaker does not buy the second
Bahncard until the total regular cost after t is equal to .
Thus, ALG pays:
For some
<R_{crit} and consider online algorithm ALG. It is clear that the
optimal choice by the offline decisionmaker against ALG would not buy B_{2}.
For this instance, the competitive ratio (online/offline) is:
Note that which
is always negative. Therefore, the online decisionmaker will take the maximum
possible value of ,
such that
= R_{crit}. The offline decisionmaker would input such shopping request
sequences that R_{2}
= 0 to make the online decisionmaker in the worst case. Having assumed ε
to be an arbitrarily small constant and
= R_{crit}ε. We obtain:
Next we consider ALG with
≥R_{crit}. There are two mutually exclusive cases.
In the first case, if the choice of R_{2} is such that R_{2}<
,
then for R_{2}<R_{crit} the online and offline costs are
equal and achieve the competitive ratio of 1. For any other choice of R_{2}
with R_{crit}<R_{2}< ,
the online ALG will not buy B_{2}, incurring a cost of C_{1}+β_{1}
(R_{1}+R_{2}). Without loss of generality, assume that R_{2}
=
ε. Thus, for this case the best attainable cost ratio is:
In the second case, the offline decisionmaker chooses R_{2}≥ .
Without loss of generality assume that R_{2} = .
Thus, the best attainable ratio for this case is:
It is found that r_{3} = r_{2}. Therefore, the offline decisionmaker
will choose R_{2} = ,
enforcing the larger ratio of r_{3}. We can get derivatives .
It follows that r_{3} is a increasing function of .
Therefore, for this case, the best attainable ratio is obtained by setting
= R_{crit}. Thus, we obtain:
Based on the above analysis, it is evident that r_{1}>r_{3}.
Hence, the online decisionmaker chooses
= R_{crit} and the best attainable competitive ratio is r_{3},
which is achieved by the optimal algorithm CSS. Namely, if
at some time is at least R_{crit}, then the decisionmaker buys the
second Bahncard; otherwise, never buys B_{2}.
Proposition: The optimal competitive ratio obtained is 2(β_{2}/β_{1}), when η→0.
Proof: Set C_{1}+β_{1}R_{1} = η. when η→0, substituting η into the function of r_{3} and the optimal competitive ratio is at most 2(β_{2}/β_{1}). 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 decisionmakers 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. AlBinali (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) = r_{ALG}/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 decisionmaker specifies a risk tolerance λ.
This means that the decisionmaker 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:
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 g_{ALG}
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:
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 g_{ALG} 
Step 5: 
Solve the model Eq. 9 to obtain the optimal online
risk algorithm ALG* 
We analyze twostage Bahncard problem in the competitive risk analysis framework
based on the two possible forecasts of R_{2}<R_{crit} and
R_{2}≥R_{crit}. For the case of R_{2}<R_{crit},
the twostage Bahncard problem has the optimal competitive ratio such that *
= 1. It is because that both the offline and online decisionmaker will never
purchase the second Bahncard with this forecast. For the case of R_{2}≥R_{crit},
we present the following strategy:
Optimal risk tolerance strategy: Given η, λ, a new Bahncard
B_{2} and a forecast of R_{2}≥R_{crit}, the online
decisionmaker would not buy B_{2} until the total regular cost of
is up to:
otherwise, never purchase B_{2}.
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 R_{2}≥R_{crit} is correct.
Proposition: If the forecast of R_{2}≥R_{crit} is
correct, the optimal restricted competitive is:
Proof: If R_{2}≥R_{crit} is correct, then the online
decisionmaker would choose an optimal risk algorithm from ξ to obtain
the more reward based on his tolerance. The offline decisionmaker would buy
the second Bahncard as soon as it appears. Therefore, the restricted competitive
ratio of the online risk algorithm is:
Since, we want to minimize ,
we want R_{2} as small as possible subject to ≤λr^{3}
from the following two cases.
Case 1: R_{2}<R_{crit} According to the preceding
risk definition, the online decisionmaker can obtain the inequality:
If C_{2}(λr_{3}1)η>0, then we obtain:
Case 2: R_{2}≥R_{crit}. 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:
For the online decisionmaker, 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 decisionmaker’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 HalfFare cards problem offered by Swiss Federal Railways. Set C_{1}
= 150 CHF, β_{1} = 80% and C_{2} = 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 decisionmakers 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.