Ski Rental Problem - Can You Do Better Than Break-even?

Can You Do Better Than Break-even?

Yes. For example, you can flip a coin. If it comes up head, you buy skis on day 8; otherwise, you buy skis on day 10. This is an instance of a randomized algorithm. It is easy to see that the expected cost is at most 80% more than what you would pay if you had known the number of days you would go skiing, regardless of how many days you ski. In particular, if you ski for 10 days, then your expected cost is 1/2 + 1/2 = 18 dollars, only 80% excess instead of 90%.

The best randomized algorithm against an oblivious adversary is to choose some day i at random according to the following distribution p, rent for i-1 days and buy skis on the morning of day i if you are still up for skiing. Karlin et al. first presented this algorithm with distribution 
p_i = \left \{
\begin{array}{ll}
(\frac{b-1}{b})^{b-i} \frac{1}{b(1-(1-(1/b))^b)} & i \leq b \\
0 & i > b
\end{array} \right . ,
where buying skis costs $b and renting costs $1. Its expected cost is at most e/(e-1) 1.58 times what you would pay if you had known the number of days you would go skiing. No randomized algorithm can do better.

Read more about this topic:  Ski Rental Problem