Problème de la location de skis

Un skieur part faire du ski pour un nombre inconnu de jours (le nombre de jours est inconnu car peut-être il va se casser une jambe, ou va devoir rentrer à cause d'une urgence familiale, etc.). Chaque jour, il doit décider s'il loue ses skis à 1€ par jour ou alors s'il achète ses skis une fois pour toutes à 10 €.

S'il reste strictement moins de 10 jours, il est plus avantageux de louer. S'il reste 10 jours ou plus, il vaut mieux les acheter. C'est l'algorithme offline. Le problème est de faire le bon choix sans connaître le nombre de jours, autrement dit on s'intéresse à un algorithme online.

Le meilleur algorithme online déterministe est de louer les 9 premier jours, puis d'acheter le jour n° 10. Si le séjour est de 10 jours, l'algorithme online déterministe paie 9€ + 10€ au lieu de 10€ pour l'algorithme offline. Dans le cas général, où le prix d'achat est b, on paie 2b - 1 au lieu de b. On a (2b - 1)/b majoré par 2. Le ratio compétitif majoré par 2 -- c'est le rapport entre les performances de l'algorithme online et de l'algorithme offline.

L'idée de l'algorithme consiste à choisir le jour au hasard à partir duquel on décide d'acheter. Ce jour i est choisi selon une loi de probabilité entre le premier jour et le jour n° 10. L'algorithme décrit par Karlin et al.[1] consiste à choisir le jour i avec la probabilité ${\displaystyle p_{i}=\left\{{\begin{array}{ll}({\frac {b-1}{b}})^{b-i}{\frac {1}{b(1-(1-(1/b))^{b})}}&i\leq b\\0&i>b\end{array}}\right.,}$ où b est le prix de l'achat. Le ratio compétitif est alors défini comme une espérance. Le ratio compétitif est de e(e-1) ${\displaystyle \approx }$ 1.58 fois plus que l'algorithme offline qui connait le nombre de jours passés.

Le problème a été généralisé à plusieurs options dans un magasin[2] ou plusieurs magasins[3].