The Unified Approach for the Best Choice Problem Applied to Alternative-Choice Selection Problems

Abstract

The objective of this paper is to show that the so-called unified approach to stopping problems with unknown cardinality introduced in Bruss (1984) proves to be efficient for solving other types of best-choice problems. We show that what we will call the alternative-choice stopping problem, which will be exemplified right away in Section 1, can be seen as a "two-sided" Secretary problem. This problem is instigated by a former problem of R. R. Weber (Cambridge University). Our approach yields for unknown cardinality the sharp lower bound $1/2$ for the probability of success. This problem is, at the same time, a special case of a model more generally based on $k\ge 2$ linearly ordered subsets. We shall also give the solution for such problems for k independent streams of arrivals. Our approach is elementary and self-contained.

arXiv comment9 pages