I was recently at the Salt lake City airport running late to make a connection to Orange County. I had already been in the air ~6 hours by that point, and it was well past dinner time so I wanted to grab some food (I also never skip a meal on the company dime.) It struck me that due to the SLC’s generally poor layout and my connection-imposed time constraint, I was faced with a dinnertime version of the marriage problem.
For those unfamiliar, the problem is a beautiful one and goes something like this:
You’re seeking to marry someone and have a line of \(n\) suitors before you (you might hope \(n\) is long :)), each wishing your hand in marriage. To choose who you’d like to marry, you may interview the suitor at the head of the line. Once you’re satisfied with the interview, you may choose to either accept or reject the suitor’s marriage proposal. If you accept the proposal, the remainder of the suitors leave the line, never to return. If you reject the proposal, the suitor you just interviewed leaves the line, never to return. How can you pick the optimal or “best” suitor?
Note: After a quick Google search, it looks like this problem is much more commonly known as the secretary problem. I actually had an incredibly hard time finding an adaptation of the problem to marriage. The problem as first introduced to me by a friend of mine at Harvard, who posed it in the context of marriage.
So what does the marriage problem have to do with my situation at the SLC? They’re fundamentally the same problem! Consider the following criteria:
Before we talk about how to solve the marriage problem (and how that turned out for my dinner problem), I want to take a moment to point out how wonderfully this situation fits the problem’s premise. It’s rare that our stylized game-theoretic and decision-theoretic models reflect reality so closely (often because doing so would make them intractable), but this was one of the rare cases where I didn’t have to try and shove the round peg of my situation into the square hole of the problem (don’t snicker).
Ok, enough waxing poetic. An optimal solution to the marriage problem is actually pretty simple. For some \(n\) suitors, we interview the first \(r - 1\) applicants and reject all of them, noting which of them was the best (following the Wiki solution, call this best suitor \(M\)). We simply accept the proposal of the next suitor we find who is better than \(M\). The optimal cutoff (\(r\)) tends towards \(\frac{n}{e}\) with a probability of optimal selection tending towards \(\frac{1}{e}\) (pretty good!).
A slight wrinkle here. The canonical marriage problem assumes knowledge of the number of suitors, \(n\). I, on the other hand, did not know exactly how many restaurants would lie between my arriving and departing gates. This isn’t a huge issue, I can use maybe the first 5 minutes of my 20(!) minute walk to my next gate counting how many restaurants I see and extrapolate the remaining \(n\) accordingly. This is more or less what I did, and was left with an approximated \(n\) of 15 remaining restaurants. So, did the optimal stopping policy work in this case? To my surprise, kind of! I ended up at a restaurant that (ex-post) I would rank #2 of all the restaurants I passed. Unfortunately, the #1 restaurant was amongst the \(r - 1\) initial restaurants (it was, in fact, the very first one I passed… something something greedy algorithms) and so it wouldn’t have been possible to select for any reasonable \(r\).
The fascinating thing here really is what I mentioned earlier – the beauty of the parallels between the decision-theoretic marriage problem and my situation. Even without knowing the optimal stopping solution and implementing it (to varying degrees of success), I think there’s much virtue in studying and understanding these models because they give us a lens through which to view the world around us.
Another funny aside as a recent alum. There’s a variation of the marriage problem known as the postdoc problem. The setup is pretty much entirely the same, except now you’re interviewing post-docs instead of suitors. And instead of searing for the best candidate, you want to find the second-best candidate to extend a postdoctoral offer to. The rational here is that the best postdoc will go to Harvard. As it turns out, this is harder than picking the best.