Optimal search and one-way trading online algorithms

This paper is concerned with the time series search and one-way trading pro blems. In the (time series) search problem a player is searching for the ma ximum (or minimum) price in a sequence that unfolds sequentially, one price at a time. Once during this game the player can decide to accept the curre nt price p in which case the game ends and the player's payoff is p. In the one-way trading problem a trader is given the task of trading dollars to y en. Each day, a new exchange rate is announced and the trader must decide h ow many dollars to convert to yen according to the current rate. The game e nds when the trader trades his entire dollar wealth to yen and his payoff i s the number of yen acquired. The search and one-way trading are intimately related. Any (deterministic o r randomized) one-way trading algorithm can be viewed as a randomized searc h algorithm. Using the competitive ratio as a performance measure we determ ine the optimal competitive performance for several variants of these probl ems. In particular, we show that a simple threat-based strategy is optimal and we determine its competitive ratio which yields, for realistic values o f the problem parameters, surprisingly low competitive ratios. We also consider and analyze a one-way trading game played against an adver sary called Nature where the online player knows the probability distributi on of the maximum exchange rate and that distribution has been chosen by Na ture. Finally, we consider some applications for a Special case of portfoli o selection called two-way trading in which the trader may trade back and f orth between cash and one asset.