For those who can't peruse Craigslist at work:
men seeking women
Why we should hang out: a mathematical proof - 24
Reply to: firstname.lastname@example.org
Date: 2007-09-10, 7:00PM CDT
Or, a Young Lady's Illustrated Primer
Suppose that you can go out with some number of guys, n. Assume that after going out with any number r (1 <= r <= n) of the men, 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 man, or go on to the next one. Further, assume that once a guy is rejected you can never go back.
For i = 1, . . .,n, let U(i) be the utility of selecting the guy with rank i among all n guys. We shall assume that U(1) >= U(2) >= . . . >= U(n). Let the random variable X denote the rank of the man 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 guys have been inspected and the rth guy has been found to have a rank a among the r. Also, let U_0(a,r) denote the expected utility if the rth man is selected, and dating is terminated. Since we fixed an n,
U*(a,n) = U_0(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: (b â€“ 1 choose a â€“ 1) * (n â€“ b choose r â€“ a) / (n choose r).
The rank b must lie between the bounds a <= b <= n â€“ r + a. Therefore,
U_0(a,r) = the sum from b = a to n â€“ r + a of U(b) (b â€“ 1 choose a â€“ 1) * (n â€“ b choose r â€“ a) / (n choose r)
Clearly, after inspecting r guys, the expected utility of inspecting one more an continuing optimally is 1/(r+1) * the sum of b = 1 to r + 1 of U*(b, r+1).Call this expression Z. From this, we can see that U*(a,r) = max (U_0(a,r), Z). The optimal procedure is to continue if U*(a,r) > U_0(a,r), and to commit when U*(a,r) = U_0(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 U_0(1,r) = r/n, and U_0(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 guys, 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 guy. 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.