# Controlling Tail Risk in Online Ski-Rental

arXiv: https://arxiv.org/abs/2308.05067 · HTML: https://mlsanity.com/paper/2308.05067/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2023.

## Built on by (most cited first, 2 of 2)

- [Competitive Algorithms for Multi-Agent Ski-Rental Problems](https://mlsanity.com/paper/2507.15727/) (2025)
- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)

## Abstract (arXiv)

The classical ski-rental problem admits a textbook 2-competitive deterministic algorithm, and a simple randomized algorithm that is fracee-1-competitive in expectation. The randomized algorithm, while optimal in expectation, has a large variance in its performance: it has more than a 37% chance of competitive ratio exceeding 2, and a Theta(1/n) chance of the competitive ratio exceeding n! We ask what happens to the optimal solution if we insist that the tail risk, i.e., the chance of the competitive ratio exceeding a specific value, is bounded by some constant δ. We find that this additional modification significantly changes the structure of the optimal solution. The probability of purchasing skis on a given day becomes non-monotone, discontinuous, and arbitrarily large (for sufficiently small tail risk δ and large purchase cost n).