Selection procedures are used in a variety of applications to select the best of a finite set of alternatives. 'Best' is defined with respect to the largest mean, but the mean is inferred with statistical sampling, as in simulation optimization. There are a wide variety of procedures, which begs the question of which selection procedure to select. The main contribution of this paper is to identify, through extensive experimentation, the most effective selection procedures when samples are independent and normally distributed. We also (a) summarize the main structural approaches to deriving selection procedures, (b) formalize new sampling allocations and stopping rules, (c) identify strengths and weaknesses of the procedures, (d) identify some theoretical links between them, (e) and present an innovative empirical test bed with the most extensive numerical comparison of selection procedures to date. The most efficient and easiest to control procedures allocate samples with a Bayesian model for uncertainty about the means, and use new adaptive stopping rules proposed here. Selection procedures are intended to select the best of a finite set of alternatives, where best is determined with respect to the largest mean, but the mean must be inferred via statistical sampling (Bechhofer et al. 1995) . Selection procedures can inform managers how to select the best of a small set of alternative actions whose effects are evaluated with simulation , and have been implemented in commercial simulation products. Selection procedures have also attracted interest in combination with tools like multiple attribute utility theory (Butler et al. 2001) , evolutionary algorithms (Branke and Schmidt 2004) , and discrete optimization via simulation (Boesel et al. 2003) . Three main approaches to solving the selection problem are distinguished by their assumptions about how the evidence for correct selection is described and sampling allocations are made: the indifference zone (IZ, Kim and Nelson 2006), the expected value of information procedure (VIP, Chick and Inoue 2001a), and the optimal computing budget allocation (OCBA, Chen 1996) approaches. IZ procedures typically allocate samples in order to provide a guaranteed lower bound for the frequentist probability of correct selection (PCS), with respect to the sampling distribution, for selection problems in a specific class (e.g., the mean of the best is at least a prespecified amount better than each alternative). The VIP approach describes the evidence for correct selection with Bayesian posterior distributions, and allocates further samples using decision-theory tools to maximize the expected value of information in those samples. The OCBA is a heuristic that uses a normal distribution approximation for the Bayesian posterior distribution of the unknown mean performance of each alternative in order to sequentially allocate further samples. Each approach stipulates a number of different sampling assumptions, approximations, stopping rules and parameters that combine to define a procedure. With so many variations, the question of which selection procedure to select arises. The question is important because the demands that are being placed upon simulation optimization algorithms are increasing. The answer may also provide new insights about differences in the empirical performance of three distinct approaches to statistical decision making (classical, or frequentist, statistics; Bayesian decision theory; and heuristic models about the probability of correct selection). * Institute AIFB, University of Karlsruhe, Germany {branke,csc}@aifb.uni-karlsruhe. A thorough comparison of these three approaches has not previously been done. Initial work shows that special cases of the VIP outperform specific IZ and OCBA procedures (in a comparison of two-stage procedures), and specific sequential VIP and OCBA procedures are more efficient than two-stage procedures (Inoue et al. 1999) . The KN family of procedures is effective among IZ procedures (Kim and Nelson 2006) . No paper has studied more than a limited set of procedures with respect to a moderate experimental test bed. This paper addresses the unmet need for an extensive comparison of IZ, VIP and OCBA procedures. §1 summarizes the main approaches to selection procedures, derives new variants and formalizes new stopping rules for the VIP and OCBA procedures. Each procedure makes approximations, and none provides an optimal solution, so it is important to understand the strengths and weaknesses of each approach. §2 describes new measurements to evaluate each with respect to: • Efficiency: The mean evidence for correct selection as a function of the mean number of samples. • Controllability: The ease of setting a procedure's parameters to achieve a targeted evidence level. • Robustness: The dependency of a procedure's effectiveness on the underlying problem characteristics. • Sensitivity: The effect of the parameters on the mean number of samples needed. Some practitioners desire a (statistically conservative) lower bound for the targeted evidence level, such as a frequentist PCS IZ guarantee, but this may lead to excessive sampling. Together, efficiency and controllability indicate how close to the desired evidence level a procedure gets while avoiding excess sampling. The procedures are compared empirically on a large variety of selection problems described in §3. The test bed is unique not only because of its size, but also by its inclusion of randomized problem instances, in addition to structured problem instances that are usually studied, but that are unlikely to be found in practice. The focus is on applications where the samples are jointly independent and normally distributed with unknown and potentially different variances, or nearly so as is the case in stochastic simulation with batching (Law and Kelton 2000) . Branke et al. (2005) presented a subset of preliminary empirical results, and assessed additional stopping rules that were somewhat less efficient than those considered below. §4 empirically compares the different selection procedures on a variety of test problems. The results show that a leading IZ procedure, called KN++ (described below), is more efficient than the original VIP and OCBA procedures, but is statistically conservative which may result in excessive sampling. In combination with the new stopping rules, the VIP and OCBA procedures are most efficient. They also tend to be more controllable and robust in the experiments below. §5 recommends those procedures, and discusses key issues for selecting a selection procedure. Appendices in the Online Companion generalize an OCBA procedure, give structural results that suggest why certain VIP and OCBA procedures perform similarly, describe the implementation, and display and interpret additional numerical results. We first formalize the problem, summarize assumptions and establish notation. §1.1 describes measures of the evidence of correct selection and, based thereon, introduces new stopping rules that improve efficiency. §1.2-1.4 describe existing and new procedures from the IZ, VIP and OCBA approaches. [k] be the ordered means. In practice, the ordering [·] is unknown, and the best system, system [k], is to be identified with simulation. The procedures considered below are derived from the assumption that simulation output is independent and normally distributed, conditional on w i and σ 2 i , for i = 1, . . . , k. Although the normality assumption is not always valid, it is often possible to batch a number of outputs so that normality is approximately satisfied. Vectors are written in boldface, such as w = (w 1 , . . . , w k ) and A problem instance (configuration) is denoted by χ = (w, σ 2 ). Let n i be the number of replications for system i run so far. be the ordering of the sample means based on all replications seen so far. Equality occurs with probability 0 in contexts of interest here. The quantities n i ,x i ,σ 2 i and (i) are updated as more replications are observed. Each selection procedure generates estimatesŵ i of w i , for i = 1, . . . , k. For the procedures studied here, w i =x i , and a correct selection occurs when the selected system, system D, is the best system, [k]. Usually If T ν is a random variable with standard t distribution with ν degrees of freedom, we denote (as do Bernardo and Smith 1994) the distribution of µ+ If κ = ∞ or 1/0, then St (µ, κ, ν) denotes a point mass at µ. Denote the cumulative distribution function (cdf) of the standard t distribution (µ = 0, κ = 1) by Φ ν () and probability density function (pdf) by φ ν (). This section provides a unified framework for describing both frequentist and Bayesian measures of selection procedure effectiveness and the evidence of correct selection. They are required to derive and compare the procedures below. They are also used within the Bayesian procedures (VIP and OCBA) to decide when the evidence of correct selection is sufficient to stop sampling. The measures are defined in terms of loss functions. The zero-one loss function, L 0−1 (D, w) = 1 1 w D = w [k] , equals 1 if the best system is not correctly selected, and is 0 otherwise. The opportunity cost L oc (D, w) = w [k] − w D is 0 if the best system is correctly selected, and is otherwise the difference between the best and selected system. The opportunity cost makes more sense in business applications. The IZ procedures take a frequentist perspective. The frequentist probability of correct selection (PCS IZ ) is the probability that the mean of the system selected as best, system D equals the mean of the system with the highest mean, system [k], conditional on the problem instance (this allows for ties). The probability is with respect to the simulation output X ij generated by the procedure (the realizations x ij determine D). Indifference zone procedures attempt to guarantee a lower bound on PCS IZ , subject to the indifference-zone constraint that the best system is at least δ * > 0 better than the others, A selected system within δ * of the best is called good. Some IZ procedures satisfy frequentist probability of good selection guarantees, PGS IZ,δ * (χ)  Bayesian procedures assume that parameters whose values are unknown are random variables (such as the unknown means W), and use the posterior distributions of the unknown parameters to measure the quality of a selection. Given the data E seen so far, two measures of selection quality are the expectation taken over both D (which is determined by the random X ij ) and the posterior distribution of W, given E. Assuming a noninformative prior distribution for the unknown mean and variance, the posterior marginal distribution for the unknown mean Groot 1970) . Each Bayesian procedure below selects the system with the best sample mean after all sampling is done, D = (k). Approximations in the form of bounds on the above losses are useful to derive sampling allocations and to define stopping rules. Slepian's inequality (e.g., see Kim and Nelson 2006) implies that the posterior evidence that system (k) is best satisfies The right hand side of Inequality (3) is approximately where d * jk is the normalized distance for systems (j) and (k), and ν (j)(k) comes from Welch's approximation for the difference W (k) − W (j) of two shifted and scaled t random variables (Law and Kelton 2000, p. 559): . We found that the Welch approximation outperformed another approximation in earlier comparisons of selection procedures (Branke et al. 2005) . The Bayesian posterior probability of a good selection, where the selected system is within δ * of the best, can be approximated in a similar manner by The term EOC Bayes may be expensive to compute if k > 2. Summing the losses from (k − 1) pairwise comparisons between the current best and each other system gives an easily computed upper bound Inoue 2001a, 2002). Let f (j)(k) (·) be the posterior pdf for the difference We denote the standardized EOC function by Chick and Inoue's upper bound for EOC Bayes is easy to approximate, using Bonferroni's inequality, by EOC Bonf , where The VIP and OCBA procedures defined below can use the values of EOC Bonf and PGS Slep,δ * to decide when to stop sampling. In particular, the following stopping rules are used: 1. Sequential (S): Repeat sampling while k i=1 n i < B for some specified total budget B. 2. Probability of good selection (PGS Slep,δ * ): Repeat while PGS Slep,δ * < 1 − α * for a specified probability target 1 − α * and given δ * ≥ 0. 3. Expected opportunity cost (EOC Bonf ): Repeat while EOC Bonf > β * , for a specified EOC target β * . Prior work for sequential VIP and OCBA procedures used the S stopping rule. The other stopping rules provide the flexibility to stop earlier if the evidence for correct selection is sufficiently high, and allow for additional sampling when the evidence is not sufficiently high. The IZ requires δ * > 0. The VIP and OCBA permit δ * = 0 to obtain a pure PCS-based stopping condition. We use PCS Slep to denote PGS Slep,0 . The IZ approach (Bechhofer et al. 1995; Kim and Nelson 2006) seeks to guarantee PCS IZ ≥ 1 − α * > 1/k, whenever the best system is at least δ * better than the other systems. The indifference-zone parameter δ * is typically elicited as the smallest difference in mean performance that is significant to the decision-maker. Some KN procedures, including KN++, can handle the more general case of correlated simulation output. Here we specialize Procedure KN++ for independent output. The procedure screens out some systems as runs are observed, and each noneliminated system is simulated the same number of times. We used ξ = 1 replication per stage per noneliminated system, and updated the sample variance in every stage. Procedure KN++ (independent samples) 1. Specify a confidence level 1 − α * > 1/k, an indifference-zone parameter δ * > 0, a first-stage sample size n 0 > 2, and a number ξ of samples to run per noneliminated system per subsequent stage. 2. Initialize the set of noneliminated systems, 4. Return remaining system, system D, as best. VIPs allocate samples to each alternative in order to maximize the expected value of information (EVI) of those samples. Some balance the cost of sampling with the EVI, and some maximize EVI subject to a sampling This section recalls those procedures, and adapts them to permit the use of the stopping rules in §1.1. Procedure 0-1. 1. Specify a first-stage sample size n 0 > 2, and a total number of samples τ > 0 to allocate per subsequent stage. Specify stopping rule parameters. 2. Run independent replications X i1 , . . . , X in 0 , and initialize the number of replications n i ← n 0 run so far for each system, i = 1, . . . , k.  and the normalized distance d * ik is as in (4) Procedure LL is a variant of 0-1 where sampling allocations seek to minimize EOC Bonf . Procedure LL. Same as Procedure 0-1, except set γ (i) in Step 4c to The OCBA is a class of procedures that was initially proposed by Chen (1996) and that has several variations (e.g. Chen et al. 2000; Chen et al. 2006) . The variations involve different approximations for PCS Bayes , and heuristics for how additional samples might improve the probability of correct selection. Here we specify the idea behind the OCBA and the variations used for this paper. The OCBA assumes that if an additional τ replications are allocated for system i, but none are allocated for the other systems, then the standard error for the estimated mean of system i is scaled back accordingly. The usual OCBA assumes normal distributions to approximate the effect, but we use Student distributions, for consistency with a Bayesian assumption for the unknown σ 2 i . Chen et al. (2006) The effect of allocating an additional τ replications to system i, but no replications to the others, leads to an estimated approximate probability of correct selection (EAPCS) evaluated with respect to the distribution ofW = (W 1 , . . . ,W k ), and withW (j) −W (k) approximated using Welch's approximation. where 1 1 {·} is 1 if the argument is true, and 0 otherwise. These approximations result in a sequential OCBA algorithm that greedily allocates samples to systems that most increase EAPCS i − PCS Slep at each stage. An innovation for the OCBA here is that sampling continues until a stopping rule from §1.1 is satisfied. Procedure OCBA. 1. Specify a first-stage sample size n 0 > 2, a number q of systems to simulate per stage, a sampling increment τ > 0 to allocate per subsequent stage, and stopping rule parameters. 2. Run independent replications X i1 , . . . , X in 0 , and initialize the number of replications n i ← n 0 run so far for each system, i = 1, . . . , k. 3. Determine the sample statisticsx i andσ 2 i and the sample mean ordering, so thatx (  He, Chick, and Chen (2006) proposed an OCBA variation, OCBA LL , that accounts for the expected opportunity cost, and showed that the original OCBA procedure, the new OCBA LL and LL perform better than some other procedures in several empirical tests. By analogy with EAPCS i above, set Procedure OCBA LL is a variation of OCBA that allocates replications to systems that maximize the improvement in expected opportunity cost (linear loss), EOC Bonf − EEOCS i , in Step 4b. All OCBA variations above were implemented as fully sequential procedures here (q = 1 and τ = 1). The OCBA heuristics in the literature to date assume normally distributed samples. Nonetheless, only the asymptotic normality of the posterior distribution of the mean is needed to justify the OCBA heuristic. In fact, posterior distributions converge to a normal distribution under relatively general sampling assumptions (Bernardo and Smith 1994, Theorem 5.14). That result can be used to asymptotically justify the OCBA heuristic under those relatively general sampling assumptions too, not just for normally distributed samples. (2005) reports preliminary results for other allocations and stopping rules that turned out to be less effective than those considered in this paper. We also tested the effect of including prior information about the means and variances in the VIP and OCBA configurations, as discussed in §3 below. At each iteration, the time to compute an allocation is proportional to the square of the number of noneliminated systems for KN++, to k 2 in the worst case for the VIP (to k if τ is large); and to k for the OCBA. For most practical applications, the time to compute the allocation is much shorter than the duration of a typical simulation. Each procedure can allocate multiple samples at a time if that is not the case. procedures have lower efficiency curves. Efficiency curves ignore the question of how to set a procedure's parameters to achieve a particular PCS IZ or EOC IZ . As a practical matter, one expects some deviation between a stopping rule target, say PCS ≥ 1 − α * > 1/k, and the actual PCS IZ achieved. The deviation between the desired and realized performance is measured with target curves that plot (log α * , log(1 − PCS IZ )) for PCS-based targets 1 − α * , and (log β * , log EOC IZ ) for opportunity cost targets β * . Procedures whose target curves follow the diagonal y = x over a range of problems are 'controllable' in that it is possible to set parameter values to obtain a desired level of correct selection. 'Conservative' procedures have target curves that tend to be below y = x, and are said to 'overdeliver' because the frequentist measure for correct selection exceeds the desired target. A procedure that is conservative may have a desirable frequentist guarantee for PCS IZ , but strong overdelivery results in excessive sampling. A controllable procedure may not have a PCS IZ guarantee if the target curve varies slightly above and below the diagonal. We say that a procedure is highly effective, if it is both efficient and controllable. Target curves can also assess whether Bayesian PCS goals map well to PCS IZ or not (the VIP and OCBA do not yet claim PCS IZ guarantees). A large number of problem instances assessed the strengths and weaknesses of each procedure. We literally explored many thousands of combinations of the number of systems, the first stage sampling size, specific configurations, allocations, stopping rules and their parameters, performance measures, etc. We tested random problem instances and the ability to use prior information about the unknown means. Design settings were chosen to explore first-order effects of the stopping rules and each parameter of the configurations and allocations, but not interactions. Appendix D gives further details about the structure of the experiments. In a slippage configuration (SC), the means of all systems except the best are tied for second best. A SC is identified by the number of systems, the difference in means of the best and each other system, and the variances of each system. The parameters δ, ρ describe the configurations we tested. If ρ = 1, then all systems have the same variance, and ρ < 1 means that the best system has a smaller variance. We set σ 2 1 = 2ρ/(1 + ρ) so that Var[X 1j − X ij ] is constant for all ρ > 0. In a monotone decreasing means (MDM) configuration, the means of all systems are equally spaced out so that some systems are quite a bit inferior to the best. The parameters δ and ρ describe the configurations that we tested. The outputs were jointly independent, and we set σ 2 1 like in SC. Values of ρ < 1 mean that better systems have a smaller variance. For sufficiently small ρ, the probability that the worst system has the best observed mean is higher than the probability for the second best system. For the SC and MDM configurations we tested hundreds, but not all, of the following combinations: Assessments of selection procedures in the literature usually apply procedures to a specific set of structured problems, as above. Such structured problem instances are atypical in practice. A problem found in practice may be considered "random". Random problem instance (RPI) configurations sample the problem instance χ prior to applying a selection procedure. In each RPI configuration below, the output is jointly independent, . . , k, conditional on the problem instance. There is no objectively best distribution for sampling problem instances, so we make arbitrary choices and identify the biases of each. The first RPI configuration (RPI1) samples χ from the normal-inverse gamma family. A random χ is generated by sampling the σ 2 i independently, then sampling the Increasing η makes the means more similar and therefore the problem harder. We set c = b − 1 > 0 to standardize the mean of the variance to be 1, and set µ 0 = 0 . Increasing b reduces the difference between the variances. We tested many combinations out of k ∈ {2, 5, 10, 20}, η ∈ {0.354, 0.5, . . . , 4} (ratios of √ 2), b ∈ {2.5, 100}, and n 0 ∈ {4, 6, 10}. The derivations of the VIP and OCBA procedures assume η → 0. The RPI1 configuration permits a test of whether the VIP and OCBA procedures can benefit from using the sampling distribution of χ in (10) to describe prior judgement about the means and variances of each system. §1 does not allow for this directly, but the mathematical development to do so was provided elsewhere 1998, 2001a). In summary, the posterior distribution of W i , given the prior distribution in (10) and data , and η = η + n i . To apply that result to all VIP procedures in §1.3, substitute eachx i with µ 0 ; replace eachσ 2 i with c /b ; and replace each n i with η , except in the degrees of freedom, where n i − 1 should be replaced with 2b . To date, the OCBA has always assumed a noninformative prior distribution. Nonetheless, analogous substitutions allow OCBA and OCBA LL to use other prior distributions for the unknown means and variances. A second RPI configuration (RPI2) samples problem instances from a distribution other than normalinverted gamma to reduce any potential advantage for the VIP and OCBA approaches. We chose RPI2 to independently sample from: The SC favors IZ procedures in that IZ procedures provide a minimal target performance with respect to a least favorable configuration (LFC). For many IZ procedures, the SC with δ = δ * is a LFC. Although the LFC of the KN family has not been proven, empirical studies of KN -type procedures often assess that configuration. The RPI1 (η near 0) favors the VIP and OCBA, as the derivation of those procedures assumes prior probability models that are similar to the sampling distribution of the problem instances. The MDM, RPI1 (larger η) and RPI2 configurations do not appear to favor any procedure in this paper. It is impossible to present all of the numerical results in one short article. This section summarizes the main qualitative observations from the analysis. Appendix A provides more numerical results. Appendix C describes the implementation. In the following analysis, each point that defines each efficiency and target curve (one for each combination of problem instance, procedure, and choice of parameters) was estimated with 10 5 samples (applications of a procedure). To sharpen the contrasts between different procedures, common random numbers (CRN) were used to generate common RPI configurations, and to synchronize the samples observed across procedures. Samples were independent within each procedure. The notation KN++ δ * specifies the choice of δ * for KN++. By default, n 0 = 6 unless specified otherwise. . In addition, we note that the efficiency curves for KN++ and Equal(S) are straighter than for the PCS or EOC stopping rules. Those Bayesian stopping rules cause a slight curvature that is linked to the choice of n 0 (a smaller n 0 gives more curvature, more on n 0 below). For a higher PICS, Equal(EOC Bonf ) is more efficient than KN++, while for a very low PICS, KN++ beats Equal(EOC Bonf ). A target plot can show by how much a procedure deviates from the desired goal (overdelivery and underdelivery). The SC configuration for the target plot in Figure 2 is the same configuration that was used for the efficiency plot in Figure 1 . The target line for the PCS-based stopping rule is below the diagonal, which means that the obtained PICS IZ is smaller than the desired goal α * . For example, for a desired α * = 0.02, a PICS IZ = 0.005 is obtained with Equal(PICS IZ ). As δ * increases for the PGS IZ,δ * stopping rule, the target curve shifts upward (the target is not obtained for δ * > 0.5). The target plot for KN++ 0.5 follows the diagonal well, meaning that the obtained PICS IZ matches the desired goal α * well for this configuration (this was observed for KN++ with all SC configurations that had k ≥ 2 and δ * = δ). As δ * is reduced, the line tilts downward, meaning that KN++ becomes extremely conservative. The consequences of conservativeness can be derived by looking at the efficiency and target plots together. For example, the x-axis intercept for the target plot of KN++ 0.3 is 0.025, meaning that a goal of α * = 0.025 resulted in an actual PICS IZ = 0.001 (overdelivers PCS). In Figure 1 , the mean number of replications for . This shows that a procedure with good efficiency curves can require much more sampling than is required to achieve a given level of evidence for correct selection, if that procedure is conservative. On the other hand, the PGS stopping rule has the risk of delivering a PICS IZ higher than desired (for Equal(PGS Slep,0.5 ), the PCS target is not met). Another aid to interpreting efficiency and target curves comes from noting that the efficiency curve for KN++ 0.7 in Figure 1 terminates near the level of PICS IZ = 0.009. That is symptomatic of an underdelivery of PICS IZ , as we tested values of α * down to 0.001. Figure 2 corroborates this underdelivery, as the target plot for KN++ 0.7 in Figure 2 is above the diagonal. This particular case of underdelivery is fully consistent with the IZ approach, since the indifference zone parameter exceeds the difference in means (δ * = 0.7 > δ = 0.5). Figure 4 shows how different sampling allocations compare for a given stopping rule (here, for EOC Bonf ). Equal performs most efficiently (it is optimal for this particular setting), with 0-1 and OCBA following. LL performs identically to 0-1 for this problem (not shown, to avoid cluttering the figure) . A similar precedence is observed for the PCS Slep and PGS Slep,δ * stopping rules. For the S stopping rule, all VIP and OCBA allocations perform about the same as Equal (not shown, to avoid clutter). With adaptive stopping rules (EOC Bonf , PCS Slep , PGS Slep,δ * ), a large number of initial samples per system, n 0 , limits the opportunity to make an early selection, but a small n 0 increases the probability of poor estimates of the output mean and variance. For the posterior marginal distributions of the unknown means to have a finite variance, we require n 0 ≥ 4. Figure 5 shows that increasing n 0 in Procedure Equal(EOC Bonf ) increases the number of samples required to reach relatively low levels of evidence for correct selection, but increases the efficiency of the procedure to reach high levels of evidence for correct selection. The differences in the curves are predominantly attributed to output that causes sampling to stop after very few samples due to misleadingly low variance and PICS estimates. The OCBA and VIP procedures behave similar to Equal in this respect for each stopping rule. With the nonadaptive stopping rule (S), they seem insensitive to n 0 . Figure 5 also shows that KN++ is insensitive to n 0 , an observation that held in general. The EOC Bonf stopping rule is sensitive to the difference between the two systems, δ (see Figure 6 ). It slightly underdelivers EOC IZ for small δ, and significantly overdelivers for large δ. Overall, for SC with k = 2 and common variances (ρ = 1), Equal(EOC Bonf ) and KN++ are the most efficient. No procedure is fully controllable for SC, k = 2. The Online Companion also argues that we could not find a general way to "trick" the procedure by setting δ * and α * to nontraditional values in order to achieve some actually desired level of PCS IZ . The remarks so far presume a common variance (ρ = 1). When ρ = 1, the equal allocation is not optimal, and more samples should be distributed to the system with a higher variance. We observed that KN++ and Equal become less efficient than the Bayesian allocations as ρ is changed away from 1 (Online Appendix). SC with k > 2 systems. It is not optimal to sample each system equally often if k > 2, so KN++ and Equal are no longer optimal in this setting, even if the variances are equal. A comparison of the efficiency of the different allocation rules, for the EOC Bonf stopping rule and k = 10 systems, is illustrated in Figure 7 . The settings are comparable to Figure 4 , which had k = 2 systems. While Equal is optimal for k = 2, it performs worst for k = 10. The most efficient allocations are OCBA LL and OCBA, then LL closely behind. KN++ is much less efficient than OCBA LL , OCBA and LL (each with EOC Bonf as a stopping rule). The difference between the efficiency of the Bayesian procedures relative to the Equal and KN++ procedures increases with k (tested k = 2, 5, 10, 20), presumably because they can allocate more samples to the most relevant (best) system from the beginning. The qualitative nature of this claim does not change as δ and ρ are individually varied from the values used for the plot. Other observations for k = 2 that also hold for k = 5, 10 and 20 include: the precedence of the effectiveness of stopping rules (EOC Bonf beats PCS Slep which beats S); the importance of a sufficiently large n 0 for the VIP and OCBA procedures; the sensitivity of KN++ to δ * but not n 0 . Monotone Decreasing Means add the complication that EOC IZ is not proportional to PCS IZ when k > 2. However, the VIP and OCBA allocations with the new EOC Bonf stopping rule are more efficient than KN++, due to the flexibility of EOC Bonf to stop when, and only when, sufficient evidence for correct selection is obtained. For each MDM configuration tested, LL(EOC Bonf ) and OCBA LL (EOC Bonf ) are not statistically different for efficiency, and they were the most efficient allocations, as in Figure 8 . Those two procedures also perform roughly similar in target plots for most configurations. OCBA δ * and 0-1 performed similar to those procedures when EOC Bonf was used. With the S stopping rule, however, 0-1 performed poorly. Figure 9 illustrates that the target performance of KN++ is again very sensitive to the parameter δ * . While KN++ adheres to the target quite well for SC when δ * = δ, it significantly overdelivers even for this setting for the MDM configuration. Procedure OCBA LL (PGS Slep,δ * ) is also sensitive to the parameter δ * , and fails to obtain the desired PICS IZ for δ * > 0.2 even though δ = 0.5. While the target curves for OCBA LL (PGS Slep,δ * ) shift roughly parallel to the diagonal, the target curves of KN++ change in slope. This means that KN++ becomes more conservative as more extreme levels of evidence (α * ) are sought, if δ * < δ, but OCBA LL (PGS Slep,δ * ) tends to be conservative by the same amount, on a log scale. Overall, as for SC, KN++ and PGS Slep,δ * are very sensitive to δ * and thus not controllable in the sense defined above. samples for all procedures, but particularly deteriorates the efficiency of KN++ (in far right of efficiency plot) relative to the PCS Slep procedures. KN++ also overdelivers more than some other procedures (right panel). The reason is that KN++ samples all noneliminated systems, even those whose means have been estimated with high precision, until a system is selected as best. The target curves for all procedures are relatively insensitive to ρ (the target curve depends primarily on the difference between the two systems competing most for best, so efficiency is affected more than the target curve). For all SC and MDM configurations and almost all sampling procedures, the efficiency curves exhibit some curvature. We found several explanations for curved efficiency lines for the OCBA and VIP procedures. One, a small n 0 leads to poor initial estimates of the variance, with a potential for either (a) early stopping if PICS is strongly underestimated, or (b) a massive number of samples being required if an extremely low PICS or EOC is desired, initial estimates suggest that the best system is worst, and the procedure then tries to distinguish between the equal systems in the SC. Both cases are alleviated by increasing n 0 . Two, the test bed pushed the procedures to new limits for numerical stability. Preliminary efficiency plots for some procedures were somewhat more curved than those presented here. Appendix C describes computational techniques that we used to reduce that curvature. We believe that this cause was eliminated. Three, exponential convergence results for ordinal comparisons are asymptotic and available for only some procedures, so straight lines should not be expected at all levels of PICS IZ and EOC IZ for all procedures. Random Problem Instances 1. For all RPI configurations, the metrics for the evidence for correct selection in the efficiency and target plots are generalized to be expectations over the sampling distribution of the problem instances, e.g. PCS IZ = E χ [PCS IZ (χ)]. One must choose δ * > 0 for the PGS Slep,δ * stopping rule because there is a reasonable probability that the two best systems have very similar means, in which case δ * = 0 results in excessive sampling (so δ * = 0 is to be avoided in practice). For the same reason, we measure efficiency by the probability of a bad selection, PBS IZ,δ * , instead of PICS IZ , in this section. A bad selection has a mean that is at least δ * worse than the mean of the best system. Procedures that use an indifference zone parameter δ * can conceivably have their efficiency measured with a PGS δ * * that use an indifference zone value δ * * = δ * , but philosophically this seems inconsistent. We therefore use the same "matching" indifference zone parameter δ * for both allocations and empirical measurements, unless otherwise specified (see also Figure 30 in the Online Companion). For basically all RPI settings, the LL, OCBA LL and OCBA δ * allocation rules are more or less equally efficient. The 0-1 allocation is generally less efficient (it is derived with more approximations, and wastes samples trying to distinguish between two very close competitors in the RPI) and Equal is worst. Figure 11 makes this point for the S stopping rule. While the difference in efficiency among the allocation rules is rather small for RPI, the performance of the stopping rules varies widely. Figure 12 compares different stopping rules in combination with Equal allocation based on PGS IZ,δ * efficiency. Clearly, the PGS Slep,δ * stopping rule with a matching δ * is the most efficient (and the target curve is also good in this setting). For EOC IZ efficiency, settings for δ * exist so that PGS Slep,δ * is more efficient than the EOC Bonf stopping rule, see Figure 13 (left panel (the right panel shows a lack of controllability if one were to try to control EOC IZ by setting β * = δ * α * , which is the expected opportunity cost for the LFC with respect to PCS for a number of IZ procedures). Several efficiency curves, in particular Equal(S) in Figure 12 and Figure 13 , are more curved for the RPI1 results than for the SC and MDM results. That curvature is largely due to a very large number of samples for a few very "hard" configurations (the best two systems have very close means and large variances). For the RPI1 configurations, LL, OCBA LL and OCBA δ * , each with the PGS Slep,δ * stopping rule, typically outperform KN++ for efficiency and controllability. Figure 14 illustrates this observation by depicting the effect of different δ * and α * on the number of samples required by KN++ and OCBA LL (PGS Slep,δ * ), and the ability to deliver the desired PGS (the δ * parameter of the procedure is also used to measure PGS IZ,δ * ). For this figure, with k = 50, the number of macroreplications was reduced to 10 4 to keep simulation time reasonable. The left panel shows that OCBA LL (PGS Slep,δ * ) follows the target much better than KN++ (which is barely visible at the lower right of the figure) . The right panel shows that the penalty for conservativeness is a significantly higher sampling effort for a given desired α * . For example, for α * = 0.01 and δ * = 0. Figure 15 : Influence of η on efficiency and target for PCS-based procedures (RPI1, k = 5, b = 100). As can be seen in Figure 15 , the sensitivity with respect to η in the RPI configurations is much smaller than the sensitivity with respect to δ observed for the SC and MDM configurations in Figure 6 . Note that the difference between the best and second best system is proportional to η −2 . For efficiency (left panel), If prior knowledge on the distribution of means and variances is available, this can be integrated into the Bayesian procedures, as described in §3. The benefit of doing so, when possible, is apparent in Figure 16 (left panel). The top line shows the efficiency of the standard Equal allocation with the budget (S) stopping rule. This can be improved stepwise by switching to a flexible allocation (OCBA LL (S)), then using an adaptive stopping rule (OCBA LL (EOC Bonf )), and finally using prior information (OCBA prior LL (EOC prior Bonf )). These changes reduce the mean number of samples required to achieve a loss of 0.01 from 291 for Equal (S) to 164 for OCBA LL (S), then to 94 for OCBA LL (EOC Bonf ), and finally to 79 for OCBA prior LL (EOC prior Bonf ). Controllability is only slightly affected by using prior information in this test (right panel). Random Problem Instances 2. The RPI2 configuration samples random problem instances with a distribution that does not match the underlying assumptions of the derivations of the VIP and OCBA procedures. Still, Procedure LL and OCBA LL again perform almost identically for efficiency and controllability, so only the latter is shown in plots. Figure 16 : Effect of allocation, stopping rule and prior information (RPI1, k = 5, η = 1, b = 100). so it is not surprising that results are very similar. Appendix A.6 has more graphs. On the whole, OCBA LL and LL perform very well for RPI2 even though the problem instances do not have the normal-inverted gamma distribution that is implicit in their derivation. A small degradation in efficiency relative to KN++ may be expected if there are multiple very good systems, but controllability remains with PGS Slep,δ * . Procedure 0-1 is less efficient and not more controllable. The choice of the selection procedure and its parameters can have a tremendous effect on the effort spent to select the best system, and the probability of making a correct decision. The new experimental setup (including random problem instances) and measurement displays (efficiency and target curves, as opposed to tables), proved useful for identifying strengths and weaknesses of both existing and new procedures. Strengths of KN++ include a low sensitivity to the number of first stage samples (n 0 ), and its natural ability to account for correlated output. It is the only method tested here with a proven asymptotic lower bound for PCS IZ ≥ 1 − α * > 1/k. The cost of preferring a lower bound for PCS is the potential for highly excessive sampling. Although we only tested moderate numbers of systems, KN++ seems to lose efficiency relative to the Bayesian procedures as the number of systems increases. We recommend combining the Bayesian allocation procedures with an adaptive stopping rule to substantially improve efficiency. Independent of the stopping rule, the loss-based allocations LL and OCBA LL are among the most efficient allocations. The Online Companion suggests theoretical reasons why OCBA LL and LL perform so similarly. The most efficient and controllable stopping rule depends on the desired goal (EOC Bonf or PGS Slep,δ * ). The strong efficiency is relatively robust to different configurations, and controllability is relatively robust for RPI. These procedures also allow for the incorporation of prior information about problem instances when that is available. Other strengths include the ability (i) to allocate samples in order to optimize the total CPU time even if the CPU times of each system are different (Chick and Inoue 2001a, and Appendix B), (ii) to run with a time constraint with the S stopping rule, and (iii) to run as a two-stage procedure if needed (e.g., the EOC Bonf stopping rule can be adapted to two stages by finding a second-stage sampling budget that achieves a desired predicted EOC Bonf ). Weak points of those procedures are a dependency on the initial number of samples for each system, n 0 (we recommend n 0 ≥ 6), and the potential for a small degradation in performance if there are many systems that are close to the best. Procedures Equal and 0-1 are not recommended for general use. We did not assess output from steady-state simulations. KN++ uses batching to estimate variances, a standard technique for the handling the autocorrelation from such simulations, but can take observations one-at-a-time. We do not see why batching might affect the different Bayesian procedures differently. We therefore select OCBA δ * (PGS Slep,δ * ), with δ * > 0, for further work to integrate selection procedures into discrete optimization via simulation environments where PGS is of interest. The clear winners for applications where the simulation output represents economic value are LL(EOC Bonf ) and OCBA LL (EOC Bonf ). Acknowledgment. We thank Seong-hee Kim and Demet Batur for very helpful discussions about KN++.
There are many selection procedures and we refer to REF for a good review of related works in this subject.
Selecting a Selection Procedure
Management Science
Management Science
Mathematics Computer Science