The Dowry Problem

You are given a chance to select one of $N$ candidates, who will be presented to you one at a time. You must accept or reject the candidate on the spot, without the possibility of returning to a previously rejected one. What is the best strategy for winning, i.e. for selecting the best candidate? Assume that you can rate each candidate (i.e. the problem is to select the candidate with the highest rating, or score — hence the "dowry").

The most obvious strategy of picking the first one gives $\frac{1}{100}$ chance of winning. It turns out we can do much better than that.

We will consider the following type of a strategy. Check out the first $k$ candidates and remember the highest score among them. Then select the first candidate who beats that score among the remaining $N - k$ candidates. Let's calculate the probability of winning with that type of a strategy for various values of $k$. Using the Formula of Total Probability, we get:

\begin{multline*} P \left( \begin{matrix} \text{winning when rejecting}\\ \text{the first $k$ candidates}\\ \text{among the total of $N$ candidates} \end{matrix} \right) = \\ \\ \\ = \sum_{m=k+1}^{N} P \left( \begin{matrix} \text{the $m$-th candidate} \\ \text{is the best} \end{matrix} \right) \cdot P \left( \begin{matrix} \text{the $m$-th candidate} \\ \text{is selected} \end{matrix} {\Huge|} \begin{matrix} \text{the $m$-th candidate} \\ \text{is the best} \end{matrix} \right) = \\ \\ \\ = \sum_{m=k+1}^{N} P \left( \begin{matrix} \text{the $m$-th candidate} \\ \text{is the best} \end{matrix} \right) \cdot P \left( \begin{matrix} \text{the highest score} \\ \text{that shows up before the $m$-th}\\ \text{is among the first $k$} \end{matrix} \right) = \\ \\ \\ = \sum_{m=k+1}^{N} \frac{1}{N} \cdot \frac{k}{m - 1} = \frac{k}{N} \cdot \sum_{m=k+1}^{N} \frac{1}{m - 1} .\end{multline*}

Now that we have the general formula, we can the optimal value of $k$ (the number of candidates to reject) when selecting among candidates.

To see the general pattern, it may be more useful to of the optimal values of $k$ for the first $1000$ cases. Calculus is needed to explan the observed behavior and the significance of the number $0.3678794\ldots$

Back to the course materials web page.