Ski Rental Online Competitive Ratio
Compare an online rent-or-buy rule with an offline decision that knows the season length.
By Riano · Published · Updated · Report a correction
Ski Rental Online Competitive Ratio
The ski rental problem illustrates the challenge of online decision-making where future demand is entirely unknown. A deterministic policy dictates renting skis until the accumulated rental cost equals the purchase price minus one, and then buying the skis on the next day.
Problem Statement
Consider a skier deciding whether to rent skis at a cost of 1 unit per day or buy them at a cost of B units. Without knowing the total number of ski days, the skier uses a deterministic strategy: rent for B-1 days, and if they ski on day B, buy the skis. The table below demonstrates the calculation of daily costs for 4 ski days when the buy price is 4.
| Day | Decision | Daily Cost | Total Online Cost | Optimal Offline Cost |
|---|---|---|---|---|
| 1 | Rent | 1 | 1 | 1 |
| 2 | Rent | 1 | 2 | 2 |
| 3 | Rent | 1 | 3 | 3 |
| 4 | Buy | 4 | 7 | 4 |
Interactive Experiment
Try adjusting the Buy price and Ski days in the interactive model at https://riano.app/module/ski-rental-online-competitive-ratio.
- Set Buy price to 4.
- Set Ski days to 4 and observe the Online cost.
Limitations
The competitive ratio analysis assumes an adversarial, worst-case scenario. It does not leverage any probabilistic distributions of ski trip lengths, which could lead to better expected costs if statistical patterns of behavior were known.
References
For more detailed mathematical proofs and alternative deterministic/randomized strategies, see the Lecture Notes on Competitive Analysis.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Ski Rental Online Competitive Ratio module.
Try Ski Rental Online Competitive Ratio on Riano →