Problème de la location de skis
# Problème de la location de skis

En informatique, le problème de la location de skis est un problème algorithmique qui modélise la prise de décisions sans connaissance sur le futur, et en particulier de la décision location VS achat présent dans les algorithmes online.

## Description du problème

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.

## Meilleur algorithme online déterministe

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.

## Meilleur algorithme online aléatoire

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. consiste à choisir le jour i avec la probabilité $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) $\approx$ 1.58 fois plus que l'algorithme offline qui connait le nombre de jours passés.

## Extensions

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

