Introduction

Imagine you're considering ski lessons and pondering the necessary equipment. You’re uncertain if skiing will capture your interest or how busy your schedule will be, leaving you torn between purchasing skis or opting for rentals for each lesson until you gauge your commitment.

Every ski rental costs 1 dollar, while buying a pair of skis amounts to 10 dollars. This raises the critical question: how can you decide between renting and buying without overspending, especially when the total number of skiing days is uncertain?

To gain insight, let’s first assume that the total number of days, denoted as T, is known. In that scenario, the best strategy is clear. For instance, if T = 5, renting skis would only cost 5 dollars (5 x 1), while buying them would cost 10 dollars. Conversely, if T = 15, purchasing skis ahead of time for 10 dollars is the optimal choice. Renting in this case would total 15 dollars, exceeding the purchase price. Generalizing, if the rental cost per day is X dollars, and buying costs Y dollars, the decision-making process becomes more complex when T is unknown.

The ski rental problem exemplifies a broader category known as rent-or-buy problems. To tackle this, we seek to create an online algorithm—one that must make decisions based on limited information that unfolds over time. Here, the input consists of daily decisions to ski or not.

Optimal Offline Strategy

In a scenario where T is known, the strategy can be summarized as follows:

• If T * X > Y, buy the skis upfront.
• Otherwise, rent each time.

This strategy is optimal because if T * X > Y*, it’s clear that renting each time would result in a higher total cost. Thus, purchasing beforehand is advisable. If T * X < Y*, renting continuously is the cheaper option. If T * X = Y*, either choice yields the same expenditure, with the minimum cost being min{Y, T * X}.

Yet, without foreknowledge of T, and given the unpredictability of preferences or circumstances, what should be the approach?

The Break-even Algorithm

A straightforward strategy emerges: start renting, and each time you consider renting, apply the following:

The Break-even Algorithm - Let S represent the total amount spent so far. - If S + X < Y, rent that day. - Otherwise, buy the skis.

The performance of this strategy is evaluated against the optimal offline cost. The worst-case ratio of our strategy’s cost to that of the optimal offline strategy is termed the competitive ratio—a key metric in analyzing online algorithms. The lower the competitive ratio, the more effective the algorithm.

Let’s analyze the competitive ratio of our break-even algorithm through various cases:

1. Case T * X < Y: Here, we rent, resulting in a total cost of T * X*, matching the optimal offline cost.
2. Case T * X ? Y: In this scenario, we pay k * X + Y*, where k is the largest integer satisfying k * X < Y*. Our overall cost is higher than the optimal offline cost, which is Y.

Theorem

The competitive ratio of the break-even algorithm is at most 2. In fact, this analysis is precise; there are scenarios where the competitive ratio approaches 2. For example, if X = 1, Y = M, and T = M + 1, we find that our costs lead to a ratio of 2. Thus, we conclude that the break-even algorithm is exactly 2-competitive.

We’ve established that the break-even algorithm achieves a competitive ratio of 2. However, it also stands as the best deterministic approach; no algorithm can achieve a competitive ratio better than 2 for any constant ? > 0.

Can Randomness Help?

Given the limitations of deterministic algorithms, one might presume that a competitive ratio of 2 is the best achievable. However, utilizing randomness allows us to surpass this threshold.

For instance, with X = 1, Y = 10, and thus k = 9, we can adopt the following randomized strategy until a purchase is made:

1. Let S be the total spent, starting at S = 0.
2. If S < 7, rent.
3. If S = 7, with a 50% chance, either rent or buy.
4. If S = 8, rent.
5. If S = 9, buy.

By evaluating this randomized approach across various values of T, we can derive competitive ratios lower than 2, demonstrating the effectiveness of incorporating randomness into our strategy.

In summary, while the break-even algorithm proves robust, randomness can yield even more favorable outcomes, achieving a competitive ratio of e/(e - 1), approximately 1.5819.

References

• https://en.wikipedia.org/wiki/Ski_rental_problem
• https://en.wikipedia.org/wiki/Online_algorithm
• https://en.wikipedia.org/wiki/Competitive_analysis_(online_algorithm)