Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-17T14:55:31.618Z Has data issue: false hasContentIssue false
  • English
  • Français

A best-choice problem with multiple selectors

Part of: Stochastic processes Sequential methods

Published online by Cambridge University Press:  14 July 2016

Hagit Glickman
Hagit Glickman*
Affiliation:
The Hebrew University of Jerusalem
*
∗Postal address: Department of Statistics, Hebrew University, Jerusalem 91905, Israel. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Consider a situation where a known number, n, of objects appear sequentially in a random order. At each stage, the present object is presented to d ≥ 2 different selectors, who must jointly decide whether to select or reject it, irrevocably. Exactly one object must be chosen. The observation at stage j is a d-dimensional vector R(j) = (R1(j),…, Rd(j)), where Ri(j) is the relative rank of the jth object, by the criterion of the ith selector. The decision whether to stop or not at time j is based on the d-dimensional random vectors R(1),…, R(j). The criteria according to which each selector ranks the objects can either be dependent or independent. Although the goal of each selector is to maximize the probability of choosing the best object from his/her point of view, all d selectors must cooperate and chose the same object. The objective studied here is the maximization of the minimum over the d individual probabilities of choosing the best object. We exhibit the structure of the optimal rule. For independent criteria we give a full description of the rule and show that the optimal value tends to d-d/(d-1), as n → ∞. Furthermore, we show that as n → ∞, the liminf of the values under negatively associated criteria is bounded below by d-d/(d-1).

Keywords

Secretary problemsbest-choicemultiple criteriamultiple chooserscooperative stopping rulesmultivariate stopping rules

MSC classification

Primary: 60G40: Stopping times; optimal stopping problems; gambling theory
Secondary: 62L15: Optimal stopping
Type
Research Papers
Information
Journal of Applied Probability , Volume 37 , Issue 3 , September 2000 , pp. 718 - 735
Copyright
Copyright © Applied Probability Trust 2000 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Assaf, D., and Samuel-Cahn, E. (1998). Optimal multivariate stopping rules. J. Appl. Prob. 35, 693–706.CrossRefGoogle Scholar
Chow, Y. S., Robbins, H., and Siegmund, D. (1971). Great Expectations: The Theory of Optimal Stopping. Houghton Mifflin, Boston.Google Scholar
Ferguson, T. S. (1989). Who solved the secretary problem? Statist. Sci. 4, 282–289.Google Scholar
Gilbert, J., and Mosteller, F. (1966). Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61, 35–73.CrossRefGoogle Scholar
Glickman, H. (1999). Cooperative stopping rules in multivariate problems. Submitted.Google Scholar
Gnedin, A. V. (1982). Multicriterial problem of optimum stopping of the selection process (translated from Russian). Automat. Remote Control 42, 981–986.Google Scholar
Joag-Dev, K., and Proschan, F. (1983). Negative association of random variables, with applications. Ann. Statist. 11, 286–295.CrossRefGoogle Scholar
Lehmann, E. L. (1966). Some concepts of dependence. Ann. Math. Statist. 43, 1137–1153.CrossRefGoogle Scholar
Presman, E. L., and Sonin, I. M. (1975). Equilibrium points in a game related to the best choice problem. Theory Prob. Appl. 20, 770–781.Google Scholar
Rinott, Y., and Samuel-Cahn, E. (1987). Comparisons of optimal stopping values and prophet inequalities for negatively dependent random variables. Ann. Statist. 15, 1482–1490.Google Scholar
Rinott, Y., and Samuel-Cahn, E. (1991). Orderings of optimal stopping values and prophet inequalities for certain multivariate distributions. Multivariate Anal. 37, 104–114.Google Scholar
Sakaguchi, M. (1980). Non-zero-sum games related to the secretary problem. J. Operat. Res. Soc. Japan 23, 287–293.Google Scholar
Samuels, S. M. (1991). Secretary problems. In Handbook of Sequential Analysis, eds Ghosh, B. K. and Sen, P. K. Marcel Dekker, New York, pp. 381–405.Google Scholar
Samuels, S. M., and Chotlos, B. (1986). A multiple criteria optimal selection problem. In Adaptive Statistical Procedures and Related Topics (IMS Lecture Notes–-Monograph Series 8), ed. Van Ryzin, J., pp. 62-78.Google Scholar
Stadje, W. (1980). Efficient stopping of a random series of partially ordered points. In Multiple Criteria Decision Making Theory and Applications (Lecture Notes in Econ. Math. Systems 177), eds Fandel, G. and Gal, T. Springer, New York, pp. 430–447.Google Scholar