Ski Rental Problem - The Problem

The Problem

Many online problems have a sub-problem called the rent/buy problem. We need to decide whether to stay in the current state and pay a certain amount of cost per time unit, or switch to another state and pay some fixed large cost with no further payment. Ski rental is one classical toy example, where the rent/buy is the entire problem. Its basic version is as follows:

You are going skiing for an unknown number of days (you do not know the exact number due to various reasons, e.g., loss of interest, accidents that break your legs, or extremely bad weather). Assume that renting skis costs $1 per day and buying skis costs $10. Every day you have to decide whether to continue renting skis for one more day or buy a pair of skis. If you know in advance how many days you will go skiing, you can decide your minimum cost. For example, if you will be skiing for more than 10 days it will be cheaper to buy skis, while if you will be skiing for fewer than 10 days it will be cheaper to rent. (If you will ski for exactly 10 days you are indifferent.) The question is what to do when you do not know in advance how many days you will ski.

Formally, the problem can be set up as follows. There is a number of days d (unknown to you) that you will ski. We are looking for an algorithm that minimizes the ratio between what you pay using the algorithm (that does not know d) and what you would pay optimally if you knew d in advance. The problem is generally analyzed in the worst case, where the algorithm is fixed and then we look at the worst-case performance of the algorithm over all possible d. In particular, no assumptions are made regarding the distribution of d (and it is easy to see that, with knowledge of the distribution of d, a different analysis as well as different solutions would be preferred).