Ski Rental with Uniform Stochastic Signals

Overview & Synopsis

Ski rental is one of the most fundamental online problems, where an agent repeatedly decides whether it should continue renting for a service, or buy it at a one-time fixed cost. In classic online analysis, an adversary may freely select any arbitrary time horizon $t$ after which the instance terminates, hence leading to strong competitive ratio lower bounds of 2 (deterministic) and $e/(e-1)$ (randomized). We consider a novel but natural model aiming at limiting the adversary's power without degrading its flexibility. A stochastic signal, containing no information apart from its arrival time, is transmitted to the algorithm at a time drawn from a known distribution scaled to $[0,t]$. This framework allows us to account for visible effects of the adversary's choice to the algorithm. Focusing as a first step on uniform distributions, we show that the best possible competitive ratios are approximately $1.478$ (deterministic) and $1.438$ (randomized). Surprisingly, simplistic deterministic strategies already achieve a performance of $1.489$.