Optimal choice and assignment of the best m of n randomly arriving items

Optimal choice and assignment of the best m of n randomly arriving items

0.00 Avg rating0 Votes
Article ID: iaor19921124
Country: Netherlands
Volume: 39
Issue: 2
Start Page Number: 325
End Page Number: 343
Publication Date: Dec 1991
Journal: Stochastic Processes and Their Applications
Authors:
Keywords: decision theory
Abstract:

A total of n items arrive at random. The decision maker must either select or discard the current item. Ranks must be assigned to items as they are selected. The decision maker’s goal is to follow a procedure that maximises the probability of selecting the m best items and assigning them according to their rank order. For m=1 this is the classical secretary problem. Rose solved the m=2 case. Key mathematical properties for the general m out of n problem are developed: functional equations expressing the general problem in terms of lower dimensional problems and theorems regarding the structure of optimal strategies are provided. A key optimal stopping result for the general problem is provided. Using these results a procedure for solving the above problem for any given m and n is developed. Using the algorithm, explicit formulas-similar in form to those for the well known m=1 and m=2 cases-can be derived. As an example, explicit formulas for the previously unsolved m=3 finite secretary problems are provided.

Reviews

Required fields are marked *. Your email address will not be published.