Tuesday, October 23, 2007

You Know Just Another Mathematical Proof !

Credits : Someone out there.

Suppose that you can go out with some number of guys, n. Assume that after going out with any number r (1 ≤ rn) 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 U0(a,r) denote the expected utility if the rth man 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:
( b – 1 ) × ( nb ) / (

n )
a – 1 ra

The rank b must lie between the bounds ab ≤ (nr + a). Therefore,

U0(a,r) = U(b) ( b – 1 ) × ( nb ) / ( n )
a – 1 ra r

Clearly, after inspecting r guys, the expected utility of inspecting one more and continuing optimally is

1/(r+1) × U*(b, r+1)

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 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.


Amiya said...

I dislike expected utility questions ever since one of them badly screwed me up in my last semester exam x(

And although you can be sure this reader is not going to take up the proof exercise, I did reach the comic strip and it's HILARIOUS. Gonna link it in my new post.

And coincidentally, this new post I've just made is quite apt for someone who enjoys this sorta 'little mathematical proof' of a blogpost.

Steph said...

Thank you for the headache you just gave me.

pankaj said...