pipette
ESEspañol

Ski Rental with Uniform Stochastic Signals

Tudor Cardas, Lucas Perotin, Bertrand Simon

Preprint

In the authors' words

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 after which the instance terminates, hence leading to strong competitive ratio lower bounds of 2 (deterministic) and (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 . 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 (deterministic) and (randomized). Surprisingly, simplistic deterministic strategies already achieve a performance of .

Main resultLimitation the authors admit

Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.