Motivation. At a ski resort you are trying to decide whether to buy a ski or rent:

  • You will be there for days
  • It costs \1$B$ to buy the ski
  • On day you will wake up and say: “I don’t want to ski anymore” and go home What should be your strategy? An online algorithm answers this question. The OPT algorithm is our benchmark, and it has information that we don’t have. The OPT algorithm for this problem is:

def. Optimal Ski Rental Algorithm.

Deterministic Ski Renter Algorithm

Example. Suppose our strategy is to rent days, and buy on the th day. Then:

  1. if then we will have rented for days, and bought on the -th day so the total cost is
  2. if then we end up just renting for days, so the total cost is

So even in the worst case, the algorithm will be less than .

thm. (Deterministic Algorithm Bound) Let a algorithm denote a deterministic algorithm that rents for days, and buys the ski at day . For any :

Proof. Knowing from the algorithm design, adversarial input will be . The deterministic algorithm is to rent until th day, and buy on the -th day. The worst case adversarial situation for is because this will force the user to rent for the maximum days, and then to buy as well.

  • Therefore:

So even the best deterministic algorithm pays . This is devastating; we can’t get past two-times better than the optimal. Instead, we should mix our strategies to overcome the adversary.

Probabilistic Ski Rental Algorithm

Example. Let us imagine a probabilistic rental algorithm that:

  • With probability , stops renting and buys at day
  • With probability , stops renting and buys at day This algorithm behaves differently depending on the true day you stop skiing, :
  1. Case :
  2. Case :
  3. Case :
    1. Therefore we have the worst of these cases bound:

Which is slightly better than deterministic. This is, however, nowhere close to how good we can be:

def. Optimal Probabilistic Ski Algorithm. The optimal algorithm is to, on waking up every day:

This algorithm will have:

(We won’t prove this)