Random priority two-person full-information best choice problem with imperfect observation

Zdzisław Porosiński; Krzysztof Szajowski

Applicationes Mathematicae (2000)

  • Volume: 27, Issue: 3, page 251-263
  • ISSN: 1233-7234

Abstract

top
The following version of the two-player best choice problem is considered. Two players observe a sequence of i.i.d. random variables with a known continuous distribution. The random variables cannot be perfectly observed. Each time a random variable is sampled, the sampler is only informed whether it is greater than or less than some level specified by him. The aim of the players is to choose the best observation in the sequence (the maximal one). Each player can accept at most one realization of the process. If both want to accept the same observation then a random assignment mechanism is used. The zero-sum game approach is adopted. The normal form of the game is derived. It is shown that in the fixed horizon case the game has a solution in pure strategies whereas in the random horizon case with a geometric number of observations one player has a pure strategy and the other one has a mixed strategy from two pure strategies. The asymptotic behaviour of the solution is also studied.

How to cite

top

Porosiński, Zdzisław, and Szajowski, Krzysztof. "Random priority two-person full-information best choice problem with imperfect observation." Applicationes Mathematicae 27.3 (2000): 251-263. <http://eudml.org/doc/219272>.

@article{Porosiński2000,
abstract = {The following version of the two-player best choice problem is considered. Two players observe a sequence of i.i.d. random variables with a known continuous distribution. The random variables cannot be perfectly observed. Each time a random variable is sampled, the sampler is only informed whether it is greater than or less than some level specified by him. The aim of the players is to choose the best observation in the sequence (the maximal one). Each player can accept at most one realization of the process. If both want to accept the same observation then a random assignment mechanism is used. The zero-sum game approach is adopted. The normal form of the game is derived. It is shown that in the fixed horizon case the game has a solution in pure strategies whereas in the random horizon case with a geometric number of observations one player has a pure strategy and the other one has a mixed strategy from two pure strategies. The asymptotic behaviour of the solution is also studied.},
author = {Porosiński, Zdzisław, Szajowski, Krzysztof},
journal = {Applicationes Mathematicae},
keywords = {mixed strategy; best choice problem; zero-sum game; stopping game},
language = {eng},
number = {3},
pages = {251-263},
title = {Random priority two-person full-information best choice problem with imperfect observation},
url = {http://eudml.org/doc/219272},
volume = {27},
year = {2000},
}

TY - JOUR
AU - Porosiński, Zdzisław
AU - Szajowski, Krzysztof
TI - Random priority two-person full-information best choice problem with imperfect observation
JO - Applicationes Mathematicae
PY - 2000
VL - 27
IS - 3
SP - 251
EP - 263
AB - The following version of the two-player best choice problem is considered. Two players observe a sequence of i.i.d. random variables with a known continuous distribution. The random variables cannot be perfectly observed. Each time a random variable is sampled, the sampler is only informed whether it is greater than or less than some level specified by him. The aim of the players is to choose the best observation in the sequence (the maximal one). Each player can accept at most one realization of the process. If both want to accept the same observation then a random assignment mechanism is used. The zero-sum game approach is adopted. The normal form of the game is derived. It is shown that in the fixed horizon case the game has a solution in pure strategies whereas in the random horizon case with a geometric number of observations one player has a pure strategy and the other one has a mixed strategy from two pure strategies. The asymptotic behaviour of the solution is also studied.
LA - eng
KW - mixed strategy; best choice problem; zero-sum game; stopping game
UR - http://eudml.org/doc/219272
ER -

References

top
  1. [1] H. F. Bohnenblust, S. Karlin, and L. S. Shapley, Games with continuous, convex pay-off, in: H. W. Kuhn and A. W. Tucker (eds.), Contributions to the Theory of Games, I, Ann. of Math. Stud. 24, Princeton Univ. Press, Princeton, 1950, 181-192. Zbl0168.41208
  2. [2] R. Cowan and J. Zabczyk, An optimal selection problem associated with the Poisson process, Theory Probab. Appl. 23 (1978), 584-592. Zbl0426.62058
  3. [3] M. Dresher, The Mathematics of Games of Strategy, Dover, New York, 1981. 
  4. [4] E. G. Enns, Selecting the maximum of a sequence with imperfect information, J. Amer. Statist. Assoc. 70 (1975), 640-643. Zbl0308.62082
  5. [5] E. G. Enns and E. Ferenstein, The horse game, J. Oper. Res. Soc. Japan 28 (1985), 51-62. Zbl0575.90096
  6. [6] E. G. Enns and E. Ferenstein, On a multi-person time-sequential game with priorities, Sequential Anal. 6 (1987), 239-256. Zbl0633.90106
  7. [7] E. Z. Ferenstein, Two-person non-zero-sum sequential games with priorities, in: T. S. Ferguson and S. M. Samuels (eds.), Strategies for Sequential Search and Selection in Real Time (Amherst, MA, 1990), Contemp. Math. 125, Amer. Math. Soc. 1992, 119-133. 
  8. [8] T. S. Ferguson, Who solved the secretary problem?, Statist. Sci. 4 (1989), 282-296. Zbl0788.90080
  9. [9] P. R. Freeman, The secretary problem and its extensions: a review, Internat. Statist. Rev. 51 (1983), 189-206. Zbl0516.62081
  10. [10] A. A. K. Majumdar, Optimal stopping for a two-person sequential game in the continuous case, Pure Appl. Math. Sci. 22 (1985), 79-89. Zbl0598.90100
  11. [11] A. A. K. Majumdar, Optimal stopping for a two-person sequential game in the discrete case, ibid. (1986), 67-75. Zbl0627.90103
  12. [12] P. Neumann, Z. Porosiński and K. Szajowski, On two person full-information best choice problems with imperfect observation, Nova J. Math. Game Theory Algebra 5 (1996), 357-365. Zbl0885.90128
  13. [13] T. Parthasarathy and T. E. S. Raghavan, Equilibria of continuous two-person games, Pacific J. Math. 57 (1975), 265-270. Zbl0308.90049
  14. [14] Z. Porosiński, Full-information best choice problems with imperfect observation and a random number of observations, Zastos. Mat. 21 (1991), 179-192. Zbl0746.62084
  15. [15] E. L. Presman and I. M. Sonin, The best choice problem for a random number of objects, Theory Probab. Appl. 18 (1972), 657-592. Zbl0296.60031
  16. [16] T. Radzik, Nash equilibria of discontinuous non-zero-sum two-person games, Internat. J. Game Theory 21 (1993), 429-437. Zbl0799.90129
  17. [17] T. Radzik and K. Szajowski, Sequential games with random priority, Sequential Anal. 9 (1990), 361-377. Zbl0745.62080
  18. [18] G. Ravindran and K. Szajowski, Non-zero sum game with priority as Dynkin's game, Math. Japon. 37 (1992), 401-413. Zbl0763.90095
  19. [19] J. S. Rose, Twenty years of secretary problems: a survey of developments in the theory of optimal choice, Management Stud. 1 (1982), 53-64. 
  20. [20] M. Sakaguchi, A note on the dowry problem, Rep. Statist. Appl. Res. Un. Japan. Sci. Engrs. 20 (1973), 11-17. 
  21. [21] M. Sakaguchi, Non-zero-sum games related to the secretary problem, J. Oper. Res. Soc. Japan 23 (1980), 287-293. Zbl0439.90106
  22. [22] M. Sakaguchi, Best choice problems with full information and imperfect observation, Math. Japon. 29 (1984), 241-250. Zbl0542.62072
  23. [23] M. Sakaguchi, Bilateral sequential games related to the no-information secretary problem, ibid. 29 (1984), 961-974. Zbl0549.90102
  24. [24] M. Sakaguchi, Some two-person bilateral games in the generalized secretary problem, ibid. 33 (1988), 637-654. Zbl0675.90097
  25. [25] K. Szajowski, On non-zero sum game with priority in the secretary problem, ibid. 37 (1992), 415-426. Zbl0768.90096
  26. [26] K. Szajowski, Double stopping by two decision makers, Adv. Appl. Probab. 25 (1993), 438-452. Zbl0772.60032
  27. [27] K. Szajowski, Markov stopping games with random priority, Z. Oper. Res. 37 (1993), 69-84. Zbl0805.90127

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.