The 1/e-strategy is sub-optimal for the problem of best choice under no information

DOI10.1016/J.SPA.2021.04.011MaRDI QIDQ2145815zbMATH OpenOpenAlexFDO

Authors F. Thomas Bruss, L. C. G. Rogers

Publication date 20 June 2022

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.13288, https://dipot.ulb.ac.be/dspace/bitstream/2013/324897/3/Bruss1.pdf

zbMATH Keywords

Hamilton-Jacobi-Bellman equationoptimal stoppingsecretary problempure birth processproportional increments

Mathematics Subject Classification ID

Stopping times; optimal stopping problems; gambling theory (60G40)

Abstract: This paper answers a long-standing open question concerning the $1/e$-strategy for the problem of best choice. $N$ candidates for a job arrive at times independently uniformly distributed in $[0,1]$. The interviewer knows how each candidate ranks relative to all others seen so far, and must immediately appoint or reject each candidate as they arrive. The aim is to choose the best overall. The $1/e$ strategy is to follow the rule: `Do nothing until time $1/e$, then appoint the first candidate thereafter who is best so far (if any).' The question, first discussed with Larry Shepp in 1983, was to know whether the $1/e$-strategy is optimal if one has `no information about the total number of options'. Quite what this might mean is open to various interpretations, but we shall take the proportional-increment process formulation of cite{BY}. Such processes are shown to have a very rigid structure, being time-changed {em pure birth processes}, and this allows some precise distributional calculations, from which we deduce that the $1/e$-strategy is in fact not optimal.

Recommendations

• The best choice problem with random arrivals: how to beat the \(1 / e\)-strategy
• A unified approach to a class of best choice problems with an unknown number of options
• scientific article; zbMATH DE number 1232442
• Strategies in the secretary problem
• A secretary problem with missing observations

Cites work

• scientific article; zbMATH DE number 3226601 (Why is no real title available?)
• A unified approach to a class of best choice problems with an unknown number of options
• A unified approach to a class of optimal selection problems with an unknown number of options
• An Optimal Selection Problem Associated with the Poisson Process
• Conditions for quasi-stationarity of the Bayes rule in selection problems with an unknown number of rankable options
• Invariant record processes and applications to best choice modelling
• Pascal processes and their characterization
• Stochastic processes with proportional increments and the last-arrival problem
• The Best Choice Problem for a Random Number of Objects
• The Secretary Problem with an Unknown Number of Options
• The secretary problem with an unknown number of candidates

Cited in

(2)

• The best choice problem with random arrivals: how to beat the \(1 / e\)-strategy
• scientific article; zbMATH DE number 3965850 (Why is no real title available?)

This page was built for publication: The 1/e-strategy is sub-optimal for the problem of best choice under no information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2145815)