Online algorithms for conversion problems : an approach to conjoin worst-case analysis and empirical-case analysis

Abstract

A conversion problem deals with the scenario of converting an asset into another asset and possibly back. This work considers financial assets and investigates online algorithms to perform the conversion. When analyzing the performance of online conversion algorithms, as yet the common approach is to analyze heuristic conversion algorithms from an experimental perspective, and to analyze guaranteeing conversion algorithms from an analytical perspective. This work conjoins these two approaches in order to verify an algorithms' applicability to practical problems. We focus on the analysis of preemptive and non-preemptive online conversion problems from the literature. We derive both, empirical-case as well as worst-case results. Competitive analysis is done by considering worst-case scenarios. First, the question whether the applicability of heuristic conversion algorithms can be verified through competitive analysis is to be answered. The competitive ratio of selected heuristic algorithms is derived using competitive analysis. Second, the question whether the applicability of guaranteeing conversion algorithms can be verified through experiments is to be answered. Empirical-case results of selected guaranteeing algorithms are derived using exploratory data analysis. Backtesting is done assuming uncertainty about asset prices, and the results are analyzed statistically. Empirical-case analysis quantifies the return to be expected based on historical data. In contrast, the worst-case competitive analysis approach minimizes the maximum regret based on worst-case scenarios. Hence the results, presented in the form of research papers, show that combining this optimistic view with this pessimistic view provides an insight into the applicability of online conversion algorithms to practical problems. The work concludes giving directions for future work.

Ein Conversion Problem befasst sich mit dem Eintausch eines Vermögenswertes in einen anderen Vermögenswert unter Berücksichtigung eines möglichen Rücktausches. Diese Arbeit untersucht Online-Algorithmen, die diesen Eintausch vornehmen. Der klassische Ansatz zur Performanceanalyse von Online Conversion Algorithmen ist, heuristische Algorithmen aus einer experimentellen Perspektive zu untersuchen; garantierende Algorithmen jedoch aus einer analytischen. Die vorliegende Arbeit verbindet diese beiden Ansätze mit dem Ziel, die praktische Anwendbarkeit der Algorithmen zu überprüfen. Wir konzentrieren uns auf die Analyse des präemtiven und des nicht-präemtiven Online Conversion Problems aus der Literatur und ermitteln empirische sowie analytische Ergebnisse. Kompetitive Analyse wird unter Berücksichtigung von worst-case Szenarien durchgeführt. Erstens soll die Frage beantwortet werden, ob die Anwendbarkeit heuristischer Algorithmen durch Kompetitive Analyse verifiziert werden kann. Dazu wird der kompetitive Faktor von ausgewählten heuristischen Algorithmen mittels worst-case Analyse abgeleitet. Zweitens soll die Frage beantwortet werden, ob die Anwendbarkeit garantierender Algorithmen durch Experimente überprüft werden kann. Empirische Ergebnisse ausgewählter Algorithmen werden mit Hilfe der Explorativen Datenanalyse ermittelt. Backtesting wird unter der Annahme der Unsicherheit über zukünftige Preise der Vermögenswerte durchgeführt und die Ergebnisse statistisch ausgewertet. Die empirische Analyse quantifiziert die zu erwartende Rendite auf Basis historischer Daten. Im Gegensatz dazu, minimiert die Kompetitive Analyse das maximale Bedauern auf Basis von worst-case Szenarien. Die Ergebnisse, welche in Form von Publikationen präsentiert werden, zeigen, dass die Kombination der optimistischen mit der pessimistischen Sichtweise einen Rückschluss auf die praktische Anwendbarkeit der untersuchten Online-Algorithmen zulässt. Abschließend werden offene Forschungsfragen genannt.