Motivation
An offline optimizer knows the entire input before acting. An online algorithm must make choices as information arrives, and a choice may become expensive when the future differs from what it expected. Comparing the online cost with the optimum for the same completed input gives a precise way to measure that disadvantage. The ski-rental problem isolates the issue: rent while the activity continues, or pay once to buy without knowing when the last day will arrive.
A competitive guarantee is a worst-case statement over possible input lengths. It does not predict the actual number of days and does not assume a probability distribution over them. This unit uses a discrete version with integer purchase cost; other timing and cost conventions give different constants.
Definitions
Definition 7.1.1
(Discrete ski rental)
Fix an integer . There are days, where the horizon is unknown to the online algorithm. At the beginning of each day that occurs, the algorithm learns that this day exists and, if it has not purchased, either rents for cost for that day or buys for cost . After purchase there is no further cost. The horizon can end after any day. An offline algorithm knows in advance.
Definition 7.1.2
(Offline optimum and competitive ratio)
For this model, the offline optimum is : rent all days or buy on the first day. Buying later cannot improve on buying on the first day if the horizon is known, since it adds rental cost. For an online algorithm , its competitive ratio is the supremum of over all positive integer horizons. No additive term is allowed in this definition.
Definition 7.1.3
(Threshold algorithm)
The threshold algorithm rents for the first days, if they occur, and buys at the start of day if that day occurs. When , it buys immediately. The algorithm learns that day exists before paying for it, but does not learn whether another day will follow.
Theorems
Theorem 7.1.4
(Threshold algorithm)
For every integer , the threshold algorithm has competitive ratio in the stated model.
Theorem 7.1.5
(Matching deterministic lower bound)
Every deterministic online algorithm in this model has competitive ratio at least . Thus the threshold algorithm is optimal among deterministic algorithms for this definition of ratio.
Proof sketch or proof idea
Proof
(Ratio of the threshold algorithm)
If , the threshold algorithm rents on every day and pays . If , it pays in rent and then to buy, for total . The offline optimum is , so the ratio is . The horizon attains this value, so it is the exact worst-case ratio.
Proof
(A purchase day forces a bad horizon)
For the lower bound fix any deterministic algorithm. Its actions on an indefinitely continuing input determine the first day on which it buys, if it ever does. Before that day it must rent. If it never buys, its cost is for arbitrarily large while the offline optimum is ; its ratio is unbounded. Otherwise consider the fixed horizon . The algorithm buys on that day because its observed history is the same as on the indefinitely continuing input. It pays .
If , then and the ratio is . If , the offline optimum is and the ratio is . This includes . Thus every deterministic choice of purchase day has a horizon attaining at least the claimed ratio. The lower bound constructs a horizon after inspecting the deterministic algorithm; it is a worst-case existence argument, not a claim that the algorithm knows its horizon.
Proof X-ray
Reading the purchase day off an endless input
The lower-bound proof has one non-obvious move: it reads the purchase day off the algorithm's behavior on an input that never ends, and only then chooses the horizon. This is legitimate because a deterministic algorithm that has seen days acts identically whether the season stops after day or continues. The proof then needs a case split at , because the offline optimum changes form there: renting throughout is optimal for , buying at once for . In both cases the ratio is at least , with equality only at . An algorithm that never buys is handled separately: its ratio is unbounded. The argument establishes one direction only. It exhibits a bad horizon for an arbitrary algorithm, whereas the upper bound for the threshold rule must hold for every horizon.
Worked examples
Worked example 7.1.6
(The horizon ends before purchase)
Let and . The threshold rule rents three times for cost . The offline optimum is , so the ratio is one. No purchase is made merely because the algorithm has planned to buy on day five; that day must actually occur.
Worked example 7.1.7
(The threshold day is the last day)
Let and . The algorithm rents four days and buys on day five, paying . An offline optimizer buys immediately or rents all five days, paying either way. The ratio is , which is the worst case for this rule. The algorithm knows day five has arrived but cannot know it is the last day when making that day's decision.
Worked example 7.1.8
(Buying too early or too late)
For , an algorithm that buys on day pays when , while the offline optimum is ; the ratio is . An algorithm that buys on day pays when , while the offline optimum is ; the ratio is . Both exceed the threshold ratio .
Common mistakes
Counterexample mode
Knowing the current day is not knowing the horizon
At the start of day five the histories of horizons and are identical. An online algorithm cannot condition its day-five action on which of those horizons will eventually occur. Giving it that information silently turns the decision into an offline one.
Common mistake
(Comparing costs on different horizons)
A competitive ratio compares costs on the same horizon. Dividing the online cost for a long horizon by the offline cost for a different, short horizon is meaningless.
Common mistake
(Reading a ratio bound as optimality on every input)
A ratio bound does not say that the algorithm is optimal on every input: on the threshold day the gap is real, although it is bounded. For and the algorithm pays against an optimum of .
Why the threshold balances two risks
Suppose a deterministic rule plans to buy on day . For a horizon ending on that very day, the rule pays for all preceding rentals and the purchase. If , the offline optimum would instead have rented throughout, so the ratio is . As increases toward , this expression decreases. If , the offline optimizer would have bought immediately, and the ratio becomes , which increases with . The two expressions meet at . This explains the rule: buying too early risks paying the purchase price just before the horizon ends, while buying too late accumulates unnecessary rent.
This argument uses the horizon to derive a lower bound for each purchase day. To establish the threshold rule's exact ratio, one must still analyze all horizons, as the first theorem does. The value at one carefully chosen horizon alone gives only a lower bound on a particular algorithm's worst-case ratio. Conversely, checking many sample horizons cannot establish a universal upper bound; the case split at covers every positive integer horizon.
Worked example 7.1.9
(Compare every deterministic threshold for a small purchase price)
Take . Buying on day one has ratio when . Buying on day two gives ratio when . Buying on day three gives ratio for every , and ratio one for shorter horizons. Buying on any day gives ratio at least when . Never buying has unbounded ratio. Thus day three is the best deterministic threshold, and its ratio matches the theorem.
The explorer below lets you vary the purchase price and the purchase day , and shows the exact worst ratio for every , with its minimum at .
What the lower-bound adversary knows
For a deterministic algorithm, the action on a given history is fixed. On an indefinitely continuing input the algorithm either buys on some day or rents forever. This hypothetical input is a convenient way to identify its purchase day; the finite horizon used to witness the lower bound is chosen afterward. Up to that day the finite and indefinite inputs have identical histories, so the algorithm acts identically. The lower-bound input is a valid fixed finite sequence for that particular deterministic algorithm.
The argument does not assume that a real adversary can see a future random seed. In fact, it does not establish a matching lower bound for randomized algorithms. A randomized algorithm may choose different purchase days on different random outcomes, so there need not be one deterministic that describes all of its runs. An analysis must state whether the input is fixed independently of the random choices, what expectation is taken, and what benchmark is used. Reusing the deterministic proof without those qualifications would conflate distinct models.
Nor is the competitive ratio an average over horizons. A horizon distribution might make one strategy attractive in expectation, but that would be a different objective. For instance, if a decision maker knows with certainty that and , renting is optimal; if it knows with certainty that is very large, buying immediately is optimal. The competitive rule makes no such distributional assumption and controls its loss on both kinds of horizon.
Timing and modeling choices
The order of events determines the theorem. In our model the algorithm first learns that the current day exists, then chooses rent or buy, and only later learns whether a further day exists. Therefore it does not pay for a nonexistent day, but it may buy on the last actual day. If the rule had to commit before learning whether the current day exists, or if a purchase applied only from the following day, the cost expressions would change. A proof written for one convention must not be transferred to another without rechecking the event order.
The integer assumption also matters. The threshold day is literally here. With noninteger purchase cost, one must choose an integer day and compare nearby possibilities; replacing by a noninteger day is not a valid algorithm. More generally, a per-day rental price can be normalized by dividing all costs by , but the resulting purchase-to-rental ratio need not be an integer. The explicit integer hypothesis avoids a rounding issue rather than resolving it silently.
The model permits buying at most once and makes ownership free thereafter. If a purchased item wears out, has a daily operating cost, or can be resold, both the online algorithm and the offline optimum change. Such variants may still be useful online problems, but the formula would need a new justification. A benchmark must represent the same rules and costs as the algorithm, except that it knows the horizon.
A certificate for a proposed ratio
To verify an upper bound , compute the online and offline costs on each possible class of inputs and prove in every class. For the threshold rule, the split at is sufficient because both formulas become constant or simple on either side. To show that is also necessary for that particular algorithm, exhibit a horizon where equality holds. Here any attains .
The lower bound for all deterministic algorithms is stronger: it must start with an arbitrary algorithm, not just another threshold chosen in advance. In this simple problem, before purchase the only possible action is renting, and the algorithm observes only the passage of days. Thus its deterministic behavior on a continuing input determines a purchase day or never-purchase behavior. That observation justifies reducing an arbitrary deterministic strategy to the cases in the theorem. In richer online problems the history contains more information, so a single threshold may not describe every strategy.
Summary
Renting delays commitment and buying caps future cost. In this discrete model the balance occurs at day , giving exact ratio . An adversary can use the algorithm's deterministic purchase day to construct a matching lower-bound horizon.
Exercises
Quick check
(For , compute the threshold algorithm's cost and ratio when and when .)
Solution · Answer
When , it pays and the optimum is , giving ratio one. When , it pays and the optimum is , giving ratio .
Quick check
(What happens when ?)
Solution · Answer
The threshold is day one, so it buys immediately for cost one. The offline optimum is one for every positive horizon; the ratio is one.
Quick check
(A deterministic algorithm buys on day with . Use horizon to calculate its ratio.)
Solution · Answer
It pays and the optimum is , so the ratio is .
Quick check
(Why does an algorithm that never buys have no finite competitive ratio?)
Solution · Answer
Its cost on horizon is while the optimum is for . The ratio grows without bound.