Optimal Stopping Algorithms for the Secretary Problem

The secretary problem is as follows. There are $n$ secretaries, each with a positive valuation. A secretary $x$ is ranked higher than secretary $y$ if they have a higher valuation than secretary $y$. A manager knows that there $n$ secretaries but must interview each secretary sequentially. The order in which the manager interviews secretaries is random. During each interview, the manager either accepts or rejects the secretary. If the manager accepts the secretary, then the manager does not interview any more secretaries. If the manager rejects the secretary, he may continue to interview more secretaries. The manager’s goal is to select the highest-ranked secretary.

Constant Stopping Algorithm

In this section, I present an algorithm that determines when to stop learning in order to choose the highest-ranked secretary. One possible way to try to select the highest-ranked secretary is to observe the valuation of the first $k$ secretaries, and then if a secretary in the next $n-k$ secretaries has a higher valuation than any of the secretaries in the first $k$ secretaries, accept that secretary. This is what the algorithm below states.

$\textbf{Algorithm. Reject \textit{k} Secretaries}$

1. Reject the first $k$ secretaries and track the highest-ranked secretary.
2. For the last $n-k$ secretaries, if a secretary is ranked higher than the highest-ranked secretary in the first $k$ secretaries, then accept the secretary.

$\textbf{Proposition.}$
The algorithm reject first $k$ secretaries selects the highest-ranked secretary with $\frac{1}{n}\left(1+\frac{k}{k+1}+\frac{k}{k+2}+\right.$ $\left.\cdots+\frac{k}{n-1}\right)$ probability.

$\textit{Proof}$. Consider the law of total probability. The probability that the highest-ranked secretary is in any position is $1 / n$. If the highest-ranked secretary is one of the first $k$ secretaries, then they are rejected. If the highest-ranked secretary is in position $k+1$, then they are selected with probability $1$. Likewise, if they are in position $k+2$, then they are selected with probability $1-\frac{1}{k+1}=\frac{k}{k+1}$. This is because the probability of selecting the highest-ranked secretary is equal to the probability that the highest-ranked secretary among the first $k+1$ secretaries appears in the first $k$ positions. This continues until the highest-ranked secretary is in position $n$. In this case, they are selected with probability $\frac{k}{n-1}$. Hence, by the total law of probability, the statement is true.

$\textbf{Proposition.}$
Rejecting approximately the first $n/e$ secretaries yields the highest probability of selecting the highest-ranked secretary.

$\textit{Proof}$. Consider maximizing the probability of selecting the highest-ranked secretary. The probability $\frac{1}{n}\left(1+\frac{k}{k+1}+\frac{k}{k+2}+\cdots+\frac{k}{n-1}\right)=\frac{k}{n}\left(\sum_{i=k}^{n-1} \frac{1}{i}\right)$ is approximately equal to $\frac{k}{n}\left(\ln \left(\frac{n-1}{k-1}\right)\right)$ which is approximately equal to $\frac{k}{n}\left(\ln \left(\frac{n}{k}\right)\right)$ for large $k$ and $n$. This is maximized when the derivative with respect to $k$ is equal to $0$. Hence, $\frac{1}{n}\left(\ln \left(\frac{n}{k}\right)-1\right)=0 \Leftrightarrow k=n / e$.

Dynamic Programming Stopping Algorithm

Determining when to stop or accept a secretary can also be found by using methods from dynamic programming. The optimal stopping policy is when the expected absolute ranking of the secretary at some stage is greater than or equal to the expected absolute ranking of future secretaries. In order to present this result, I define some important notation.

Suppose that $s$ is the cardinality of a subset of the $n$ secretaries. The relative rank of the $i$ th secretary out of $s$ secretaries is a number from $1$ to $s$. The absolute rank of the $i$ th secretary out of $n$ secretaries is a number from $1$ to $n$. Let the random variable $X_i$ be the relative rank of the $i$ th secretary among the first $i$ secretaries. Assume that the variables $X_i$ are identically, independently, and uniformly distributed.

$\textbf{Lemma.}$
The probability that a secretary of relative rank $x$ among the first $s$ secretaries has absolute rank $b$ is given by the distribution

$f(b \mid s, x)=\frac{\binom{b-1}{x-1}\binom{n-b}{s-x}}{\binom{n}{s}}$

for all $b=x, \ldots, n-s+x$.

Similar to the problem above, I consider only the conditional probability of when the secretary’s absolute rank is $1$, given their relative rank. In this case, the above lemma implies that $f(1 \mid s, x)=$ $\frac{s}{n}$ if $x=1$ and $0$ if $x \neq 1$.

The dynamic programming problem can be formulated as

$v_s(x)=\max \left\{f(1 \mid s, x), \frac{1}{s+1} \sum_{x=1}^{s+1} v_{s+1}(x)\right\}$

such that $v_n(x)=1$ if $x=1$ and $0$ otherwise. The first part of the $\max$ function, i.e. $f(1 \mid s, x)$ represents the conditional expected absolute ranking of the $s$ secretary. The second part of the max function represents the expected absolute value of future secretaries, where values closer to zero represent a future secretary with an absolute ranking of one is unlikely. Values closer to one represent a secretary with an absolute ranking of one is likely. Consider the following policy to decide when to stop.

$\textbf{Algorithm. A Stopping Policy}$

1. If at secretary $s \in\{1, \ldots, n-1\}$, $f(1 \mid s, x) \geq \frac{1}{s+1} \sum_{x=1}^{s+1} v_{s+1}(x)$, then choose secretary $s$ and stop. Otherwise, continue.

2. If no secretaries from $1, \ldots, n-1$ is chosen, then choose secretary $n$.

$\textbf{Proposition.}$
For some $m(n)$, the policy selects the highest-ranked secretary with probability $\frac{1}{n}\left(1+\frac{m-1}{m}+\cdots+\frac{m-1}{n-2}+\frac{m-1}{n-1}\right)$.

$\textit{Proof.}$ Use the law of total probability. The probability that the policy selects the highest-ranked secretary is the sum of the probabilities that it selects the highest-ranked secretary at position $i=1, \ldots, n$. The probability of selecting the highest-ranked secretary at position $i$ is equal to the probability that the highest-ranked secretary is at position $i$, given that $i$ is selected and the probability that $i$ is selected. For $i=1, \ldots, n-1$, the conditional probability is equal to $f(1 \mid i, 1)=\frac{i}{n}$. For secretary $i=n$, the probability is equal to $\frac{1}{n}$. Further, the lemma below describes the probability of selecting a secretary. Hence, for all $s>m$, define

$h(m, s):=\frac{1}{s} \prod_{i=m}^{s-1} \frac{i-1}{i}=\frac{1}{s} \frac{m-1}{s-1}.$

The probability that the policy selects the highest-ranked secretary is

$\begin{array}{l} \frac{1}{m}\left(\frac{m}{n}\right)+h(m, m+1) \frac{m+1}{n}+\cdots+h(m, n-1) \frac{n-1}{n}+\frac{m-1}{n-1} \frac{1}{n} \\ =\frac{1}{n}+\frac{m-1}{m} \frac{1}{n}+\cdots+\frac{m-1}{n-2} \frac{1}{n}+\frac{m-1}{n-1} \frac{1}{n} \\ =\frac{1}{n}\left(1+\frac{m-1}{m}+\cdots+\frac{m-1}{n-2}+\frac{m-1}{n-1}\right). \end{array}$

The result here is incredibly similar to the probability that the reject first $k$ secretaries algorithm finds the highest-ranked secretary. It can also be shown that under the provided stopping policy, $m$ is approximately $\frac{n}{e} + 1$.

$\textbf{Lemma.}$
For some $m(n)$, the policy selects secretary $m$ with probability $\frac{1}{m}$, secretary $m+1$ with probability $h(m, m+1)$, secretary $m+2$ with probability $h(m, m+2), \ldots$, and secretary $n-1$ with probability $h(m, n-1)$. Secretary $n$ is selected with probability $\frac{m-1}{n-1}$. For all secretary $l<m$, the policy selects secretary $l$ with probability $0$.

$\textit{Proof.}$ At any specific secretary $s \in\{1, \ldots, n\}$, the policy selects secretary $s$ with probability

$P\left(f\left(1 \mid s, X_s\right) \geq \frac{1}{s+1} \sum_{x=1}^{s+1} v_{s+1}(x)\right)=\left\{\begin{array}{l} \frac{1}{s} \text { if } s \geq m \\ 0 \text { if } s<m \end{array}.\right.$

The probability is positive only when $f(1 \mid m, x)>0$, which occurs when $x=1$. The probability of the relative rank being one out of $m$ ranks is $1 / m$. Further, if $f(1 \mid m, x)>0$ for some $m$, then $f(1 \mid m+1, x)>0$ if $x=1$. Hence, secretary $m$ is selected with probability $1 / m$, and a subsequent secretary $p$ is selected with the probability that secretaries $m$ to $p-1$ are not selected and $p$ is selected. Secretary $n$ is selected if no other previous secretaries were selected, which is

$\left(1-\frac{1}{m}\right)\left(1-\frac{1}{m+1}\right) \ldots\left(1-\frac{1}{n-2}\right)\left(\frac{1}{n-1}\right)=\frac{m-1}{n-1}.$