Secretary problem

The question is about the optimal strategy (stopping rule) to maximize the probability of selecting the best applicant.

as the limit of (r−1)/n, using t for (i−1)/n and dt for 1/n, the sum can be approximated by the integral Taking the derivative of P(x) with respect to

The optimal thresholds r and probability of selecting the best alternative P for several values of n are shown in the following table.

This problem and several modifications can be solved (including the proof of optimality) in a straightforward manner by the odds algorithm, which also has other applications.

One way to overcome this problem is to suppose that the number of applicants is a random variable

The essence of the model is based on the idea that life is sequential and that real-world problems pose themselves in real time.

The goal is to maximize the probability of selecting only the best under the hypothesis that all arrival orders of different ranks are equally likely.

, whereas this value 1/e was now achieved as a lower bound for the success probability, and this in a model with arguably much weaker hypotheses (see e.g.

(Ferguson, 1989)[1], it's claimed the secretary problem first appeared in print in Martin Gardner's February 1960 Mathematical Games column in Scientific American:Ask someone to take as many slips of paper as he pleases, and on each slip write a different positive number.

The aim is to stop turning when you come to the number that you guess to be the largest of the series.

[1] In this game: The difference with the basic secretary problem are two: Alice first writes down n numbers, which are then shuffled.

So, their ordering does not matter, meaning that Alice's numbers must be an exchangeable random variable sequence

Alice's strategy is then just picking the trickiest exchangeable random variable sequence.

If Alice samples the numbers independently from some fixed distribution, it would allow Bob to do better.

So the fully formal statement is as below:Does there exist an exchangeable sequence of random variables

Stein, Seale & Rapoport 2003 derived the expected success probabilities for several psychologically plausible heuristics that might be employed in the secretary problem.

The figure (shown on right) displays the expected success probabilities for each heuristic as a function of y for problems with n = 80.

This model is consistent with the notion of an interviewer learning as they continue the search process by accumulating a set of past data points that they can use to evaluate new candidates as they arrive.

A benefit of this so-called partial-information model is that decisions and outcomes achieved given the relative rank information can be directly compared to the corresponding optimal decisions and outcomes if the interviewer had been given full information about the value of each applicant.

Experimental psychologists and economists have studied the decision behavior of actual people in secretary problem situations.

In real world settings, this might suggest that people do not search enough whenever they are faced with problems where the decision alternatives are encountered sequentially.

While there is a substantial body of neuroscience research on information integration, or the representation of belief, in perceptual decision-making tasks using both animal[20][21] and human subjects,[22] there is relatively little known about how the decision to stop gathering information is arrived at.

Researchers have studied the neural bases of solving the secretary problem in healthy volunteers using functional MRI.

[23] A Markov decision process (MDP) was used to quantify the value of continuing to search versus committing to the current option.

Therefore, brain regions previously implicated in evidence integration and reward representation encode threshold crossings that trigger decisions to commit to a choice.

He had heard about it from John H. Fox Jr., and L. Gerald Marnie, who had independently come up with an equivalent problem in 1958; they called it the "game of googol".

Fox and Marnie did not know the optimum solution; Gardner asked for advice from Leo Moser, who (together with J. R. Pounder) provided a correct analysis for publication in the magazine.

Soon afterwards, several mathematicians wrote to Gardner to tell him about the equivalent problem they had heard via the grapevine, all of which can most likely be traced to Flood's original work.

[26] Ferguson has an extensive bibliography and points out that a similar (but different) problem had been considered by Arthur Cayley in 1875 and even by Johannes Kepler long before that, who spent 2 years investigating 11 candidates for marriage during 1611 -- 1613 after the death of his first wife.

By a generalization of the classic algorithm for the secretary problem, it is possible to obtain an assignment where the expected sum of qualifications is only a factor of