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

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 (1982) 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 this 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 problem are provided.optimal stopping secretary problem ranking and selection