Saturday, 2 January 2010

The Marriage Problem

How do you know when it's time to get married? As a Maximiser (of which I shall write another time), this question troubles me. How do you know that the one you're with right now, of all the millions of people out there, is The One? How do you know that she isn't yet to come into your life? For that matter... how do you know that you haven't already said goodbye to her?


Don't Stop 'Til You Get Enough
Ooh!

Mathematically, if naively, the problem is simple to formulate. There are many mathematically equivalent versions - the most common is the "Secretary Problem". One version, called "Googol", presents it as a simple game. Imagine that in front of you is a stack of 100 unsorted pages, face down. On each page is written a number, any posible real number, within an unknown range. You can turn over a page from the top of the stack one at a time to see the number, and you can keep on turning as many pages as you like, but once you turn over a new page, you can't go back. Your goal is to stop when you think you've just turned over the highest number you think you'll ever get, and keep it - forfeiting all numbers yet to come and having already forfeited all numbers already seen.
What are your chances of selecting the highest number? Is it just pure luck, or is there a strategy? It turns out that there is a strategy to maximise the probability of selecting the highest number.
The basic idea is to "write off" some initial number of pages just to get an idea of the size of numbers that are in the stack, and use that knowledge to subsequently stop when you think you have the highest number.
Like in statistics, the trick is to obtain a large enough sample of the population to measure the natural variability, so that you can say with some degree of confidence that any given data point is, you might say, a significant other. The difficulty is that whereas in most statistics a larger sample set is better, in this problem a larger sample set increases the probability that the highest data point is in the sample set, and if it's in the sample set, you've already given it up.
So, what is the best strategy? It turns out to be in the form of a "stopping rule": turn over a certain number of pages, making a note of the highest number that you see, and then keep on turning over pages until you get a number higher than that previous best, and stick with this new best.
J. Gilbert and F. Mosteller of Harvard University proved that the optimal number of pages to turn over before stopping at the next new best is 37. This magic number is 100 (pages) divided by 2.72 (e, the base of the natural logarithm). This strategy works for any population size - just divide it by e and sample at least that many data points before stopping at the best so far.


When I'm Sixty-Four
Will you still need me, will you still feed me, when I'm sixty-four?

Now, let's apply this knowledge to the problem of getting married. What is the population size from which I can sample? Very roughly, let's say there are 6.4 billion people, 50% of which are women (3.2 billion), 50% of which are between 18 and 40 (1.6 billion), 25% of which are single and available, leaving 400 million. A demographer would be able to give you a more accurate figure, but what's a few hundred million amongst friends? Now, sadly, not every single one of those women is interested in dating me, but let's conservatively say that 1 in 40 will (because it makes a round number), resulting in a population size of 10 million. Going by Gilbert and Mosteller's 37% rule, then, I should date about 3.7 million women before thinking about getting married! If I 5-minute speed-date 24/7 for the next 35 years, then, and only then, I can think about settling down.


Love The One You're With
If you can't be with the one you love, love the one you're with.

Actually, it's a bit more complicated (no kidding!). In the classical version of this problem, the goal is to try to select the single highest number; the single best partner; The One. Anything less is failure. Aiming high is admirable, but risky: Gilbert and Mosteller's solution is optimal, but still results in only a 37% (1/e) chance of selecting the best partner. Not so great. But it gets worse: there's also a 37% chance of ending up with the last remaining option out of desperation (this would happen if my best partner was one of the first 37% of people that I passed over, meaning that I would never encounter anyone better and would search for the rest of my (dating) life in vain. So: a 37% chance of finding The One; a 37% chance of searching for my entire life only to end up with the last available option; and a 26% chance of something in between - not The One, but probably ok (guaranteed better than a random 37% sample of the population).
In light of those odds, maybe it's better not to optimise the probability of selecting the single best partner, and instead optimise the expected value of whoever is selected, even if they're not the best. In Googol the value would be the number on the page; in the marriage problem it might be the ranking of a partner's beauty, or intelligence, or some more sophisticated aggregate score (about which I shall also write later). The probability of selecting the single best partner will be lower, but the expected value of the partner who is selected will be higher.
J. N. Bearden of the University of Arizona showed that in this modified version of the Secretary Problem, called the Cardinal Payoff Variant, the optimal strategy is still a stopping rule, but the optimal sample size is the square root of the population size, not the population size divided by e. So now I only have to date 3162.27 people instead of 3.7 million - excellent! (sqrt(10,000,000) = 3162.27. I wonder how you date 0.27 of a person?)


This Year's Love
This year's love had better last...

So maybe applying the stopping rule to the literal population size is not feasible. Realistically, we're not constrained by the number of dates, we're constrained by time. Let's say that I want to get married before I'm 40 years old. I started dating when I was 19, so that gives me 20 years to date - 20 pages in my stack. The square root of 20 is 4.47. That means I should date for about four-and-a-half years before thinking about making a commitment. I'm 27 years old now... that's eight years into my dating window. I... I guess it's time to start looking for a wife!


Alright, let me concede that this is an extremely simplistic model of dating. It makes a bunch of assumptions that simply don't hold true in real life.
In real life, for example, I could go down on my knees - both for forgiveness and in proposal - and marry someone I've already dated.
In real life, direct sampling is not the only way of building up a predictive model of the (dating) world - we have anecdotes and movies and women's interest magazines; we share the models we've individually built up, with each other.
In real life... we fall in love and it just doesn't matter.

2 comments:

Brett said...

When it comes down to it, you just know. I can't explain it really... and that kinda frustrates me.

Nick said...

Yes, this isn't meant to be a serious analysis of when to get married - just a mathematical curiosity!

I believe that, as unsatisfying an answer as it is, you're right - and I certainly bow to your experience in this matter :)