Analysis of algorithms for online uni-directional conversion problems

In an online uni-directional conversion problem, an online player wants to convert an asset $D$ to a desired asset $Y$. The objective of the player is to obtain the maximum amount of the desired asset. Competitive analysis is used as a tool for the design, and analysis of online algorithms for conversion problems. Although widely used, competitive analysis has its own set of drawbacks when the applicability of online algorithms in real world is considered. In this work, we investigate online uni- directional conversion problems with the objective to suggest measures for improving the applicability of online conversion algorithms in real world. First, we study competitive ratio as a coherent measure of risk and conclude that as it satisfies all the desirable axioms of coherence, competitive ratio can be used in practice. Secondly, we evaluate a selected set of online algorithms on real world as well bootstrap data to highlight the gap between theoretically guaranteed and experimentally achieved competitive ratio. The third aspect of the study deals with generating synthetic data that truly represents all possible scenarios such as market crashes. We suggest the use of Extreme Value Theory (EVT) approach. Using EVT approach, we generate synthetic data and execute a selected set of non-preemptive uni-directional online algorithms on it. The fourth contribution of the thesis includes the design and analysis of risk-aware reservation price algorithms for conversion problems. The proposed algorithms are flexible to accommodate the risk level of the online player whereas guaranteeing a bounded worst case competitive ratio as well. We evaluate our algorithms using the competitive analysis approach as well as testing the algorithms on the real world data. The results will help to improve the applicability of online conversion algorithms in real world. We conclude the work by discussing a number of open questions that will provide new directions for future research.In einem Online-uni-directional-conversion-Problem, möchte ein Online-Spieler ein Asset $D$ in ein gewünschtes Asset $Y$ konvertieren. Das Ziel des Spielers ist es, den maximalen Wert des gewünschten Assets zu erhalten. Die competitive analysis wird als Hilfsmittel verwendet, um Online-Algorithmen für Conversion-Probleme zu entwerfen und zu analysieren. Obwohl die competitve analysis weit verbreitet ist, besitzt sie mehrere Nachteile wenn ihre Anwendbarkeit auf Online-Algorithmen in der realen Welt betrachtet wird. In dieser Arbeit werden wir online Uni-directional-conversion-Probleme betrachten, mit dem Ziel, Kennzahlen zu erarbeiten, um die Anwendbarkeit von Online-Conversion-Algorithmen in der realen Welt zu verbessern. In einem ersten Schritt untersuchen wir die competitive ratio als kohärentes Risikomaß und schließen, wenn es alle notwendigen Kohärenzaxiome erfüllt wurden, dass die competitive ratio in der Praxis eingesetzt werden kann. In einem zweiten Schritt evaluieren wir eine ausgewählte Menge an Online-Algorithmen in der realen Welt. Außerdem werden die Daten gebootstrapped, um den Unterschied zwischen der theoretisch garantierten und empirisch erreichten competitive ratio. Der dritte Aspekt dieser Arbeit betrachtet das Generieren von synthetischen Daten, welche alle möglichen Szenarien, wie beispielsweise einen Marktcrash, repräsentieren. Wir empfehlen dafür den Einsatz der Extreme-Value-Theorie (EVT). Mit der EVT generieren wir synthetische Daten und führen eine ausgewählte Menge an nicht-präemptiven Uni-directionalen-Online-Algorithmen über diesen aus. Der vierte Beitrag dieser Arbeit beinhaltet das Design und die Analyse von risk-aware Reservationspreis-Algorithmen für Conversion-Probleme. Die vorgeschlagenen Algorithmen können das Risikoniveau des Online-Spielers aufnehmen und garantieren eine begrenzte Worst-Case-Competitive-Ratio. Wir evaluieren unsere Algorithmen mit Hilfe des competitive-analysis-Ansatzes sowie dem Testen der Algorithmen auf realen Daten. Die Resultate werden in Form von Forschungsarbeiten präsentiert und helfen, die Anwendbarkeit von Online-Conversion-Algorithmen in der realen Welt zu verbessern. Wir schließen die Arbeit mit einer Diskussion über eine Reihe offener Fragen, welche neue Forschungsrichtungen für die Zukunft eröffnen