Ski-Rental-Problem

Das Ski-Rental-Problem (Skiverleihproblem) beschreibt die Problemstellung, die beim Design von Online-Algorithmen entsteht. In dem konkreten Problem geht es darum, zu einem passenden Zeitpunkt zu entscheiden, Skier einmalig zu kaufen oder für jeden Skilauf zu leihen, und zwar unter der Maßgabe, dass die Gesamtkosten minimal sind. Das Ski-Rental-Problem steht stellvertretend für eine Reihe von Problemen, in denen jeweils ein Konsument etwas einmalig kauft zu einem festen Preis oder leihweise für die genutzte Zeit bezahlt. Dabei ist stets unklar, wie lang das Problem läuft, das heißt es muss jeden Tag neu entschieden werden, ob es sich nun lohnt zu kaufen oder weiter zu leihen.

Problembeschreibung

Wir nehmen an, eine Person ohne Ski möchte Ski fahren gehen. Sie hat die Wahl zwischen dem (einmaligen) Kauf eines Paares Skier (Kaufpreis z. B. 200 Euro) und der Miete (Tagesmiete z. B. 20 Euro). Entscheidend ist, dass die Person nicht weiß, wie lange sie Skifahren wird, sondern jeden Tag neu entscheiden kann, ob es sich nun lohnt zu kaufen oder weiter zu mieten. Daher ist zu Beginn des Algorithmus noch nicht bekannt, welches die wirtschaftlich bessere Methode ist. Dies modelliert ein typisches Online-Problem, bei dem der Input (Wie viele Tage fahre ich Ski?) erst mit der Zeit bekannt wird.

Der Offline-Fall dagegen beschreibt das Problem, wenn die Person schon weiß, dass sie nur eine feste Zahl Tage fahren will. In diesem Fall ist einfach auszurechnen, ob kaufen oder mieten billiger ist. Wenn beispielsweise fünf Tage Ski fahren geplant sind, kommt die Miete von $5\cdot 20=100$ Euro günstiger als ein Kauf von $200$ Euro. Sind hingegen zwölf Tage Ski fahren geplant, ist es billiger, gleich am ersten Tag das Paar Skier zu kaufen, da der Kauf für $200$ Euro günstiger ist als die Miete von $12\cdot 20=240$ Euro.

Gesucht ist nun eine Handlungsvorschrift für den Fall, dass man die Anzahl Skitage am Anfang nicht kennt. Für den einzelnen Fall muss jede beliebige Vorschrift versagen. Sollte es jedoch eine größere Anzahl von Buchungen geben, bietet die Versicherungsmathematik sichere Methoden zum Umgang mit solchen Buchungen. Je größer die Anzahl der Buchungen wird, desto genauer lassen sich Bedarf und Nachfrage abbilden. Diese Methoden sind stochastisch hinterlegt und werden in vielen Fällen schon angewendet.

Problemlösung

Sei $P$ der Gesamtpreis der Skier (in Euro), welcher beim Kauf zu bezahlen wäre. Dagegen sei im Folgenden angenommen, dass die Mietkosten pro Tag bei $1$€ liegen.

deterministischer Algorithmus

Angenommen die Person befindet sich am Beginn des $P.$ Tages. Entscheidet sie sich nun, die Skier einen weiteren Tag verwenden zu wollen, so wäre es besser die Skier zu kaufen, da, wenn sie diese weiter mieten würde, hätte sie bereits den vollen Preis $P$ der Skier bezahlt, müsste jedoch am $P+1.$ Tag, an dem sie die Skier verwendet, erneut die Miete zahlen. Dieser einfache Algorithmus bietet eine Lösung des Problems, allerdings sind die Kosten sehr hoch, wenn die Person am $P+1.$ Tag entscheidet, die Skier nicht mehr zu verwenden. Wäre bereits zu Beginn bekannt gewesen, dass die Skier nur $P+1$ Tage verwendet werden, so wären die Mietkosten $P+1$€ gewesen, wohingegen wir im Online-Beispiel $P-1+P$€ bezahlen mussten, da die Person die Skier zuvor noch $P-1$ Tage mietete. Dieser Fall beschreibt den Worst Case für diesen Algorithmus. Daher ist, gegenüber dem optimalen Fall, der Worst Case um den Faktor $2-{\frac {1}{P}}$ ineffizienter, da die Person die Skier preislich fast zweimal kaufen muss, minus den Preis, welchen die Person sich durch den Kauf am $P.$ Tag in der Miete erspart hat (bis zum $P-1.$ Tag bezahlte die Person die Miete und kaufte dann am $P.$ Tag die Skier, der Subtrahend ${\frac {1}{P}}$ beschreibt den einen Tag Miete, den die Person sparte).

Für jede Zahl $A$ an Tagen der Verwendung der Skier gilt somit:

$E(A)\leq (2-{\frac {1}{P}})\cdot O\left(A\right)$

Dabei soll $E$ den Gesamtpreis (nach dem hier genannten Algorithmus) für $A$ Tage darstellen sowie $O$ die optimale Lösung für den Offline-Fall.

zufälliger Algorithmus

Nun wird angenommen, dass die Skier nicht immer strikt am $P.$ Tag gekauft werden, sondern, dass der Algorithmus beispielsweise am ${\frac {1}{2}}P.$ Tag ein Zufallsexperiment durchführt (hier: das Werfen einer Münze, welche nicht auf dem Rand landen kann) und, basierend auf dem Ausgang dieses Experiments, bereits am ${\frac {1}{2}}P.$ Tag die Skier kauft oder erst am $P.$ Tag. Damit ergibt sich für das Beispiel folgende Effizienz gegenüber dem Optimalwert:

$E(A)\leq c\cdot O(A)$, wobei für $c$ gilt:

$c={\begin{cases}1,&{\text{wobei }}A<{\frac {1}{2}}P\\3,&{\text{wobei }}{\frac {1}{2}}P\leq A<P\\{\frac {7}{4}},&{\text{wobei }}A\geq P\end{cases}}$

Für den Fall $A<{\frac {1}{2}}P$ wählt der Algorithmus somit immer den Optimalfall (mieten statt kaufen). Ist $A\in [0,5\cdot P;P)$, so ist $c=3$, der Algorithmus somit ineffizienter, als der deterministische Fall. Im letzten Fall, $A\geq P$, ist der Algorithmus maximal ${\frac {7}{4}}$ mal schlechter als der Optimalwert. Diese Zahlenwerte ergeben sich aus dem Zusammenhang:

$E(A)={\frac {1}{2}}(A)+{\frac {1}{2}}\left({\frac {1}{2}}P-1+P\right)\leq {\frac {1}{2}}(A)+{\frac {1}{2}}(A+2A)=3\cdot A=3O(A)$ (für ${\frac {1}{2}}P\leq A<P$, der Optimalwert beträgt hier $A$), bzw.

$E(A)={\frac {1}{2}}(P-1+P)+{\frac {1}{2}}\left({\frac {1}{2}}P-1+P\right)\leq {\frac {7}{4}}P={\frac {7}{4}}O(A)$ (für $A\geq P$, der Optimalwert beträgt hier $P$).

Algorithmen, welche eine Zufallsexperiment beinhalten, sind im Allgemeinen effizienter bei der Lösung dieses Problems. So lässt sich in Quelle folgende effizientere Lösung des Problems finden:

$p_{A}=\left\{{\begin{array}{ll}({\frac {P-1}{P}})^{P-A}{\frac {1}{P(1-(1-(1/P))^{P})}}&A\leq P\\0&A>P\end{array}}\right.,$

wobei hier ein zufälliger Tag $A$ ausgewählt wird, an welchem die Skier gekauft werden. Dieser Algorithmus ist der beste zufällige Algorithmus zur Lösung dieses Problems, dabei betragen die Kosten im Worst Case nur ca. 1,58 mal soviel wie die optimale Offline-Lösung.

Siehe auch

• Sekretärinnenproblem

Literatur

• Mark S. Manasse: Ski Rental Problem. In: Ming-Yang Kao (Hg.): Encyclopedia of Algorithms. Springer, Berlin/Heidelberg/New York 2008, ISBN 978-0-387-30162-4, Teil 18.
• Anna R. Karlin: On the Performance of Competitive Algorithms in Practice. In: Amos Fiat, Gerhard J. Woeginger (Hg.): Online Algorithms. The State of the Art. Lecture Notes in Computer Science 1442, Springer, Berlin/Heidelberg/New York 2008, ISBN 3-540-64917-4, Kap. 16, S. 373 ff.