Design and analysis of online conversion algorithms for financial trading

Abstract

In an online trading problem, an online player (trader/investor) wants to trade an asset in hand with a desired asset with the goal of maximizing the profit by the end of a trading period. Online trading algorithms are classified as non-pre-emptive and pre-emptive algorithms. Non-pre-emptive algorithms (also known as Reservation Price Algorithms) restrict the trader to invest all or nothing at any time point. In contrast, pre-emptive algorithms allow the trader to trade any amount as she desires. The online currency conversion is a form of online trading where a trader looks for converting a currency in hand to another desired currency, e.g., (Dollars to Yens). The performance analysis of online trading and conversion algorithms is majorly done under the worst-case competitive analysis paradigm. Although a variety of algorithms are proposed in the literature for online conversion problems, the intrinsic problem settings and the inherent assumption of the underlying models are unrealistic and far from real-world scenarios. For instance, online algorithms for conversion problems assume a-priori knowledge about the lower and upper bounds of future price quotations. Although, this is a key requirement for the design of an optimal algorithm, under real-world settings such assumptions might not hold and can render the algorithms ineffective. Likewise, the algorithms also treat every input sequence as worst-case and consequently the decision making is based on a pessimistic approach. The pessimistic approach, in turn leads to lack of risk management for investors, which is a key component for real-world practical usability of such algorithms. Our research focus is the design of new online trading algorithms and models with the objective of profit maximization (or cost minimization), while considering the real-world settings. We propose an algorithm 〖RP〗^* using novel update model with realistic price bounds. The key feature of the proposed model is to regularly update the price bounds based on inter day price fluctuation. The experimental competitive ratio c^e (〖RP〗^*) is compared with the benchmark algorithm, where 〖RP〗^* outperforms the benchmark algorithm for all 120 data subsets. Next, we consider the k-Min search problem of buying k units of assets with the objective of minimizing the total buying cost and propose a risk aware policy using risk and reward framework for better returns. The competitive ratio c_ω of the proposed k-Min-RR is bounded by c_ω∈[c^* \/ω,c^* ω], i.e., c_ω improves if the forecast is true and c_ω never goes beyond c^* ω if the forecast is false. Further, we model the realistic worst-case sequences for a set of algorithms and analyse the performance gap between theoretical and practical worst-cases. The effectiveness of our proposed solutions is evaluated under theoretical analysis model to assure the worst-case performance bounds. To show the practical significance, we also perform the experimental simulations over the real-world stock exchange data. The maximum observed performance gap between c_ec and c_wc is 85.5%. The results of analytical and experimental measures highlight the success guarantee of our designed policies. The thesis work is concluded by open questions and new directions for future work.