Knockout-Tournament Procedures for Large-Scale Ranking and Selection in Parallel Computing Environments

On one hand, large-scale ranking and selection (R&S) problems require a large amount of computation. On the other hand, parallel computing environments that provide a large capacity for computation are becoming prevalent today, and they are accessible by ordinary users. Therefore, solving large-scale R&S problems in parallel computing environments has emerged as an important research topic in recent years. However, directly implementing traditional stagewise procedures and fully sequential procedures in parallel computing environments may encounter problems because either the procedures require too many simulation observations or the procedures’ selection structures induce too many comparisons and too frequent communications among the processors. In this paper, inspired by the knockout-tournament arrangement of tennis Grand Slam tournaments, we develop new R&S procedures to solve large-scale problems in parallel computing environments. We show that no matter whether the variances of the alternatives are known or not, our procedures can theoretically achieve the lowest growth rate on the expected total sample size with respect to the number of alternatives and thus, are optimal in rate. Moreover, common random numbers can be easily adopted in our procedures to further reduce the total sample size. Meanwhile, the comparison time in our procedures is negligible compared with the simulation time, and our procedures barely request for communications among the processors.