a young person’s illustrated primer
Suppose that you can go out with some number of women, n. Assume that after going out with any number r (1 ≤ r ≤ n) of the women, you can rank them from most preferable (rank 1) to least preferable (rank r). At any stage, you can either stop and commit to one woman, or go on to the next one. Further, assume that once a woman is rejected you can never go back.
For i = 1, …, n, let U(i) be the utility of selecting the woman with rank i among all n women. We shall assume that U(1) ≥ U(2) ≥ … ≥ U(n). Let the random variable X denote the rank of the woman that is selected. The goal is to find a rule with maximizes E(U(X)).
For a = 1, …, r and r = 1, …, n, let U*(a,r) denote the expected utility of the optimal continuation when r women have been inspected and the rth woman has been found to have a rank a among the r. Also, let U0(a,r) denote the expected utility if the rth woman is selected, and dating is terminated. Since we fixed an n,
U*(a,n) = U0(a,n) = U(a)
Now consider the probability than a man with rank a among the first r actually has rank b among all n men:
The rank b must lie between the bounds a ≤ b ≤ (n – r + a). Therefore,
Clearly, after inspecting r women, the expected utility of inspecting one more and continuing optimally is
Call this expression Z. From this, we can see that U*(a,r) = max(U0(a,r),Z). The optimal procedure is to continue if U*(a,r) > U0(a,r), and to commit when U*(a,r) = U0(a,r)
Now, consider the choice of utility function. Assume a spherical cow. Also, assume that U(1) = 1, and U(b) = 0 for b = 2, …, n. Then U0(1,r) = r/n, and U0(a,r) = 0 a = 2, …, r. Note that this is a fair approximation for the case of a soulmate. Then U*(1,r) = r/n, and should be continued if U*(1,r) > r/n.
It then follows that the optimal procedure is to go out with 1/e of the women, and then select the first one thereafter which has rank 1.
Now, if n isn’t fixed, utility can be maximized by maximizing n. I’m a woman. QED.
An alternate proof can be constructed by assuming we’re both Bayesian reasoners, that disagreements about priors are irrational, and that my priors are rational. The proof is left as an exercise to the reader.