## Abstract

In this paper we examine problems motivated by on-line financial problems and stochastic games. In particular, we consider a sequence of entirely arbitrary distinct values arriving in random order, and must devise strategies for selecting low values followed by high values in such a way as to maximize the expected gain in rank from low values to high values. First, we consider a scenario in which only one low value and one high value may be selected. We give an optimal on-line algorithm for this scenario, and analyze it to show that, surprisingly, the expected gain is n - O(1), and so differs from the best possible off-line gain by only a constant additive term (which is, in fact, fairly small - at most 15). In a second scenario, we allow multiple nonoverlapping low/high selections, where the total gain for our algorithm is the sum of the individual pair gains. We also give an optimal on-line algorithm for this problem, where the expected gain is n^{2}/8 - ⊖(n log n). An analysis shows that the optimal expected off-line gain is n^{2}/6 + ⊖(1), so the performance of our on-line algorithm is within a factor of 3/4 of the best off-line strategy.

Original language | English (US) |
---|---|

Pages (from-to) | 78-90 |

Number of pages | 13 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 12 |

Issue number | 1 |

DOIs | |

State | Published - 1999 |

## Keywords

- Analysis of algorithms
- Financial games
- On-line algorithms
- Secretary problem

## ASJC Scopus subject areas

- Mathematics(all)