Duration problem with multiple exchanges

Pages: 333 - 355, Volume 2, Issue 2, June 2012

doi:10.3934/naco.2012.2.333       Abstract        References        Full Text (342.6K)       Related Articles

Charles E. M. Pearce - The University of Adelaide, Department of Applied Mathathematics, Adelaide, South Australia 5005, Australia (email)
Krzysztof Szajowski - Institute of Mathematics and Computer Science, Wrocław University of Techechnology, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland (email)
Mitsushi Tamaki - Department of Business Administration, Aichi University, Nagoya Campus, Hiraike 4-60-6, Nakamura, Nagoya, Aichi 453-8777, Japan (email)

Abstract: We treat a version of the multiple-choice secretary problem called the multiple-choice duration problem, in which the objective is to maximize the time of possession of relatively best objects. It is shown that, for the $m$--choice duration problem, there exists a sequence $(s_1,s_2,\ldots,s_m)$ of critical numbers such that, whenever there remain $k$ choices yet to be made, then the optimal strategy immediately selects a relatively best object if it appears at or after time $s_k$ ($1\leq k\leq m$). We also exhibit an equivalence between the duration problem and the classical best-choice secretary problem. A simple recursive formula is given for calculating the critical numbers when the number of objects tends to infinity. Extensions are made to models involving an acquisition or replacement cost.

Keywords:  Optimal stopping, relative ranks, best-choice problem, dynamic programming, one-step look ahead rule.
Mathematics Subject Classification:  Primary: 60G40, 90A46; Secondary: 62L15, 60K99

Received: October 2011;      Revised: May 2012;      Published: May 2012.

 References