Optimal Algorithms for <Emphasis Type="Italic">k</Emphasis>-Search with Application in Option Pricing

In the k-search problem, a player is searching for the k highest (respectively, lowest) prices in a sequence, which is revealed to her sequentially. At each quotation, the player has to decide immediately whether to accept the price or not. Using the competitive ratio as a performance measure, we give optimal deterministic and randomized algorithms for both the maximization and minimization problems, and discover that the problems behave substantially different in the worst-case. As an application of our results, we use these algorithms to price “lookback options”, a particular class of financial derivatives. We derive bounds for the price of these securities under a no-arbitrage assumption, and compare this to classical option pricing. J. Lorenz is partially supported by UBS AG. K. Panagiotou is partially supported by the SNF, grant number: 200021-107880/1.