ISSN:
1432-0541
Schlagwort(e):
Key words. Competitive secretary problem, No-information case, Relative ranks, Recursive sequences, Convergence of recursive solutions, Algorithm analysis, Discrepancy problems, Minimax optimal, Nash equilibrium.
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
Abstract. Two decision-makers A and B observe sequentially a given permutation of n uniquely rankable options. A and B have one choice each (without recall) and both must make a choice. At each step only the relative ranks are known, and A has the priority of choice. At the end the (absolute) ranks are compared and the winner is the one who has chosen the better rank. Extending results by Enns and Ferenstein [6] and Berry et al. [1] this article gives, for both A and B , the optimal strategy and the corresponding winning probabilities. We show in particular that the limiting winning probabilities for A and B do exist, which closes a most important gap in the work of previous authors. This also provides an algorithm for numerically computing the limiting value of these probabilities. Although our proof is analytic in a strong sense, it is interesting to see that it would have been very hard to assemble it without the help of computer algebra. The reason is that the functions we have to investigate display subranges of indices which contrast considerably with respect to error terms when certain terms are replaced by approximations, and that computations were very helpful to locate those ranges where a particularly fine tuning of error estimates turned out to be indispensable.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/PL00009232
Permalink
