Introduction

You arrive at a ski resort. Renting skis costs $1 a day. Buying a pair costs $10, once, and then you ski for free forever. The catch: you have no idea how many days you'll ski. The weather, your knee, your budget — any day could be your last.

If you knew you'd ski 20 days, you'd buy on day one. If you knew you'd ski 3 days, you'd just rent. But you don't know. Every morning you must commit money before the future reveals itself.

This tiny dilemma is the ski-rental problem, and it is the friendliest gateway to online algorithms: making irreversible decisions as data arrives, one piece at a time, with no peek at what comes next. The surprise is that a one-line rule does almost as well as a fortune teller.

Play the Decision

Below, each day costs $1 to rent and you can buy for $10 at any moment. You don't know when the season ends — but a hidden adversary does, and it will pick the ending that makes your choice look worst.

<p class="hint">Renting costs <b>$1/day</b>; buying costs <b>$10</b> once, then you ski free. Pick the day you'll buy (or never). A hidden <b>adversary</b> then ends the season on the worst day for you. The break-even rule — buy on day 10 — keeps your cost within <b>2×</b> the perfect-hindsight optimum, no matter what.</p>
<div class="ctrl">
  <label>Buy on day: <b id="dayLabel">10</b></label>
  <input id="day" type="range" min="1" max="20" value="10">
  <button id="never" type="button" class="ghost">Never buy (rent forever)</button>
</div>
<div class="btns">
  <button id="run" type="button">Let the adversary choose the ending</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status">Pick a strategy, then run.</div>
<div id="bars" class="bars"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.ctrl { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .6rem; }
.ctrl label { font-size: .95rem; }
input[type=range] { flex: 1; min-width: 140px; accent-color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.bars { display: grid; gap: .5rem; margin-top: .6rem; }
.row { display: grid; grid-template-columns: 110px 1fr 90px; align-items: center; gap: .5rem; font-size: .85rem; }
.track { background: #e8eef3; border-radius: 6px; height: 22px; overflow: hidden; }
.fill { height: 100%; border-radius: 6px; }
.fill.you { background: #1d3557; }
.fill.opt { background: #0a7d33; }
.num { font-weight: 700; text-align: right; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Ski-rental. Rent = $1/day, Buy = $10 (B). A deterministic online strategy
// picks a day d to buy (or never). The optimal OFFLINE cost for a season of
// n days is min(n, B). We let an adversary choose the n in [1..20] that
// MAXIMIZES the ratio (your cost / optimal). The break-even rule d = B is
// provably 2-competitive: your cost never exceeds 2B - 1 while OPT = B.
const B = 10, MAXDAYS = 20;
let buyDay = 10, never = false;

// Your cost if you planned to buy on day `d` (1-indexed) and the season lasts n days.
// You rent days 1..min(n, d-1); if n >= d you also pay B once on day d.
function youCost(d, n){
  if (d === Infinity) return n;          // never buy: rent every day
  if (n < d) return n;                    // season ended before you bought
  return (d - 1) + B;                     // rented d-1 days, then bought
}
const optCost = (n) => Math.min(n, B);    // best in hindsight

function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + (cls||''); }

function run(){
  const d = never ? Infinity : buyDay;
  // Adversary maximizes ratio over all possible season lengths.
  let worstN = 1, worstRatio = 0;
  for (let n = 1; n <= MAXDAYS; n++){
    const r = youCost(d, n) / optCost(n);
    if (r > worstRatio + 1e-9){ worstRatio = r; worstN = n; }
  }
  const yc = youCost(d, worstN), oc = optCost(worstN);
  drawBars(yc, oc, worstN);
  const label = never ? 'rent forever' : (fmt('buy on day %buyDay%', { buyDay: buyDay }));
  const ratioTxt = worstRatio.toFixed(2);
  if (worstRatio <= 2 + 1e-9)
    setStatus(fmt('Worst ending: %worstN% day(s)..  You paid $%yc% vs optimal $%oc% — ratio %ratioTxt% ≤ 2. Within the guarantee (%label%).', { worstN: worstN, yc: yc, oc: oc, ratioTxt: ratioTxt, label: label }), 'ok');
  else
    setStatus(fmt('Worst ending: %worstN% day(s)..  You paid $%yc% vs optimal $%oc% — ratio %ratioTxt% > 2! (%label%)', { worstN: worstN, yc: yc, oc: oc, ratioTxt: ratioTxt, label: label }), 'bad');
  console.log('strategy', label, fmt('worst n=%worstN%', { worstN: worstN }), fmt('you=$%yc%', { yc: yc }), fmt('opt=$%oc%', { oc: oc }), fmt('ratio=%ratioTxt%', { ratioTxt: ratioTxt }));
}

function drawBars(yc, oc, n){
  const max = Math.max(yc, oc, 1);
  const bars = document.getElementById('bars');
  bars.innerHTML =
    fmt('<div class="row"><span>Your cost</span><div class="track"><div class="fill you" style="width:%v%%"></div></div><span class="num">$%yc%</span></div><div class="row"><span>Optimal (hindsight)</span><div class="track"><div class="fill opt" style="width:%v2%%"></div></div><span class="num">$%oc%</span></div>', { v: 100*yc/max, yc: yc, v2: 100*oc/max, oc: oc });
}

const slider = document.getElementById('day');
slider.addEventListener('input', () => {
  never = false; buyDay = +slider.value;
  document.getElementById('dayLabel').textContent = buyDay;
  setStatus(fmt('Strategy: buy on day %buyDay%. Run to see the worst ending.', { buyDay: buyDay }), '');
});
document.getElementById('never').addEventListener('click', () => {
  never = true;
  document.getElementById('dayLabel').textContent = '—';
  setStatus('Strategy: rent forever. Run to see the worst ending.', '');
});
document.getElementById('run').addEventListener('click', run);
document.getElementById('reset').addEventListener('click', () => {
  never = false; buyDay = 10; slider.value = 10;
  document.getElementById('dayLabel').textContent = 10;
  document.getElementById('bars').innerHTML = '';
  setStatus('Pick a strategy, then run.', '');
});
Result
Console

Try buying immediately, try renting forever, then try the break-even rule: keep renting until your rental spending would equal the purchase price, then buy. Against every ending the adversary throws at you, your total never exceeds twice what a perfect crystal ball would have paid. That factor of two is the famous competitive ratio.

The Real Complexity

What does it mean for a strategy to be "good" when you can't see the future? We compare against the optimal offline cost — what you'd pay if you'd known the number of days in advance — and ask how much worse the online choice is in the worst case. That worst-case ratio is the competitive ratio.

  • The break-even rule is 2-competitive. Rent until accumulated rental cost reaches the buy price BB, then buy. If the season ends early, you only ever rented — you paid the optimum. If it runs long, you paid at most 2B−12B - 1 while the optimum was BB. So you never pay more than about twice the best-in-hindsight cost. This is a proven bound, not a heuristic.
  • No deterministic strategy does better. An adversary can always end the season exactly when your fixed plan looks worst, forcing the ratio arbitrarily close to 2. So 2 is optimal for deterministic play — it's a matching lower bound.
  • Randomization breaks the barrier. If you flip a biased coin to decide when to buy, the expected competitive ratio drops to ee−1≈1.58\frac{e}{e-1} \approx 1.58, and that too is provably optimal (Karlin, Manasse, McGeoch, Owicki, 1990s). You can't beat the adversary every time, but on average you can do strictly better.

This is the heart of online algorithms: the question isn't "can we compute the answer?" — that's easy — but "how badly does not knowing the future cost us?"

Where It Matters

"Pay a little repeatedly, or pay a lot once" is one of the most common decisions in computing — and almost always under uncertainty:

  • Cloud costs: keep paying for on-demand instances (rent) or commit to a reserved/savings plan (buy)? The break-even rule is the textbook starting point.
  • Power management: should a laptop keep a device spinning (rent energy) or power it down and pay the restart cost later (buy)? Spin-down timers are ski-rental in disguise.
  • Caching and connections: hold a TCP connection or cache entry open (rent memory) versus tearing it down and re-establishing it (buy). The same trade-off sets keep-alive timeouts.
  • Snow-removal and leasing: the original metaphor — lease equipment per use or purchase it — recurs across operations research.

Wherever a system must commit now without seeing demand, the ski-rental rule is the first thing engineers reach for. It also shares its DNA with the broader world of decision-under-uncertainty problems like P vs NP-flavored optimization.

Conclusion

The ski-rental problem is small enough to explain on a chairlift, yet it captures something profound: you can make smart, provably near-optimal choices without ever seeing the future. Rent until your spending equals the purchase price, then buy — and no matter how the season ends, you pay at most twice what perfect hindsight would have.

That factor of two isn't a lucky number; it's the price of not knowing, and it can't be beaten by any deterministic strategy. Flip a coin and you can shave it to about 1.58. The next time you face a "commit now or pay as you go" choice — a cloud plan, a gym membership, a subscription — remember the skier: the break-even line is already the best guess you can make against a future that's allowed to be cruel.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/ski-rental/Content licensed under CC BY-NC 4.0.