A Nonparametric Predictive Approach to Sequential Acceptance Problems

Abstract

Sequential acceptance problems are considered with the aim to select candidates from a group, with the candidates observed sequentially, either per individual or in subgroups, and with the ordering of an individual compared to previous candidates and those in the same subgroup available. For given total group size, this problem can in principle be solved by dynamic programming, but the computational effort required makes this not feasible for problems once the number of candidates to be selected and the total group size are not small. We present a new heuristic approach to such problems, based on the principles of nonparametric predictive inference, and we study its performance via simulations, which are also used to compare the method with some alternatives. The approach is easy to implement and computationally straightforward.

Keywords:

• 60A99
• 62G99
• 62P30

Keywords:

• Acceptance decisions
• Dynamic programming
• Heuristics
• Marriage problem
• Nonparametric predictive inference
• Secretary problem
• Sequential decisions

Acknowledgments

We gratefully acknowledge supportive comments and suggestions by two anonymous reviewers.

Notes

¹This paper presents the main results of our study; further results are given by Elsaeiti (2012).

²See also www.npi-statistics.com

³The statistical software R was used.

⁴Throughout the paper (unless where explicitly stated differently), box plots of simulation results are presented in figures for different values of the threshold parameter p, which are the values on the horizontal axis.