Comparison among Some Optimal Policies in Rank-Based Selection Problems

Krzysztof Szajowski

Contributions to game theory and management, Tome 3 (2010), pp. 409-420.

Résumé

The paper deals with the sequential selection problem of the best object. Interviewers observe applicants or items and may decide to stop and hire the current applicant. He has some knowledge about the total number of applicant available. No recall of previously observed candidates is allowed. Knowledge about current applicant is restricted to his relative rank among interviewed so far. The graders have to select, each of them, exactly one item, when it appears, and receives a payoff which is a function of the unobserved realization of random variable assigned to the item or its rank. When there is only one grader the optimal strategy for wide class of payoff functions has a threshold form. It means that in optimal behavior the decision maker should observe the fixed number of items $k^*$, a learning sample, and to choose the first one after which is better than all those previously observed. The optimality of the strategy is shown by optimal stopping methods for the Markov sequences. The experimental results have shown that the decision makers in problems like choice of partner, the best real investment, try to accept the reasonable option earlier than the optimal strategy of mathematical models suggest. The main aim of the research is to investigate the assumptions of the mathematical model to show their influence on the optimal threshold.

Détail

Keywords: rank-based selection, mathematical models of choice, secretary problem, optimal stopping.

Bibliographie

[1] Bearden J. N., “A new secretary problem with rank-based selection and cardinal payoffs”, J. Math. Psychology, 50 (2006), 58–59 | DOI | MR | Zbl

[2] Corbin R. M., “The secretary problem as a model of choice”, J. Math. Psychol., 21 (1980), 1–29 | DOI | MR | Zbl

[3] Dynkin E., Yushkevich A., Theorems and Problems on Markov Processes, Plenum, New York, 1969 | MR

[4] Ferguson T. S., Who solved the secretary problem?, Statistical Science, 4 (1989), 282–296 | DOI | MR

[5] Ferguson T., “Selection by committee”, Advances in Dynamic Games: Applications to Economics, Finance, Optimization, and Stochastic Control, Annals of the International Society of Dynamic Games, 7, eds. A. S. Nowak, K. Szajowski, Birkhäuser, Boston, 2005, 203–209 | DOI | MR | Zbl

[6] Fushimi M., “The secretary problem in a competitive situation”, J. Oper. Res. Soc. Jap., 24 (1981), 350–358 | MR

[7] M. Gardner, “Mathematical games”, Scientific American, 202:1 (1960), 150–156 ; 3, 172–182 | DOI | MR

[8] Kurano M., Yasuda M., Nakagami J., “Multi-variate stopping problem with a majority rule”, J. Oper. Res. Soc. Jap., 23 (1980), 205–223 | MR | Zbl

[9] Mazalov V. V., Banin M. V., “$N$-person best-choice game with voting”, Game theory and applications, Papers from the workshop on networking games and resource allocation (Petrozavodsk, Russia, July 12–15, 2002), v. IX, eds. L. A. Petrosjan et al., Nova Science Publishers, Hauppauge, NY, 2003, 45–53 | MR | Zbl

[10] Móri T., “Hitting a small group of middle ranked candidates in the secretary problem”, Probability theory and mathematical statistics with applications (Visegrád, 1985), Reidel, Dordrecht, 1988, 155–169 | MR

[11] Presman E., Sonin I., “Equilibrium points in game related to the best choice problem”, Theory of Probab. and its Appl., 20 (1975), 770–781 | DOI | MR | Zbl

[12] Ramsey D., Szajowski K., “Three-person stopping game with players having privileges”, J. Math. Sci., 105:6 (2001), 2599–2608 | DOI | MR | Zbl

[13] Rasmussen W. T., Robbins H., “The candidate problem with unknown population size”, J. Appl. Probab., 12 (1975), 692–701 | DOI | MR | Zbl

[14] Ravindran G., Szajowski K., “Non-zero sum game with priority as {Dynkin's} game”, Math. Jpn., 37:3 (1992), 401–413 | MR | Zbl

[15] Rose J., “{S}election of nonextremal candidates from a sequence”, J. Optimization Theory Appl., 38 (1982), 207–219 | DOI | MR | Zbl

[16] Sakaguchi M., “Optimal stopping games — a review”, Math. Jpn., 42 (1995), 343–351 | MR | Zbl

[17] Sakaguchi M., Mazalov V. V., “A non-zero-sum no-information best-choice game”, Math. Methods Oper. Res., 60:3 (2004), 437–451 | DOI | MR | Zbl

[18] Samuel-Cahn E., “Optimal stopping for i.i.d. random variables based on the sequential information of the location of relative records only”, Sequential Anal., 26:4 (2007), 395–401 | DOI | MR | Zbl

[19] Seale D., Rapoport A., “Sequential decision making with relative ranks: An experimental investigation of the “secretary problem””, Organizational Behaviour and Human Decision Processes, 69 (1997), 221–236 | DOI

[20] Seale D., Rapoport A., “Optimal stopping behavior with relative ranks: The secretary problem with unknown population size”, J. Behavioral Decision Making, 13 (2000), 391–411 | 3.0.CO;2-I class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI

[21] Smith M., “A secretary problem with uncertain employment”, J. Appl. Probab., 12 (1975), 620–624 | DOI | MR | Zbl

[22] Sonin I., “Game problems related to the best choice problem”, Kibernetika, 2 (1976), 70–75 (in Rusian) | MR | Zbl

[23] Szajowski K., “Optimal choice problem of $a$-th object”, Matem. Stos., 19 (1982), 51–65 (in Polish) | MR | Zbl

[24] Szajowski K., “On non-zero sum game with priority in the secretary problem”, Math. Jpn., 37:3 (1992), 415–426 | MR | Zbl

[25] Szajowski K., “Markov stopping games with random priority”, Zeitschrift für Operations Research, 37:3 (1993), 69–84 | MR

[26] Szajowski K., Yasuda M., “Voting procedure on stopping games of {M}arkov chain”, UK-Japanese Research Workshop on Stochastic Modelling in Innovative Manufecuring (Moller Centre, Churchill College, Univ. Cambridge, UK, July 21–22, 1995), Lecture Notes in Economics and Mathematical Systems, 445, eds. Anthony H. Christer, Shunji Osaki, Lyn C. Thomas, Springer, 1996, 68–80 | DOI | MR

[27] Szajowski K., “On stopping games when more than one stop is possible”, Probability Methods in Discrete Mathematics, Proceedings of the Fifth International Petrozavodsk Conference, May 2000, eds. V. F. Kolchin et al., International Science Publishers, 2002, 57–72

[28] Szajowski K., “A rank-based selection with cardinal payoffs and a cost of choice”, Sci. Math. Jpn., 69:2 (2009), 285–293 | MR | Zbl