Sign In

Communications of the ACM

Viewpoint

Lousy Advice to the Lovelorn


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
Lousy Advice to the Lovelorn, illustrative photo

Credit: Akuma-Photo

People seeking advice on getting married have recently been directed to a decidedly unromantic algorithm. The algorithm has two stages. Let N be the maximum number of people you expect to be able to date before you give up. In the first stage, you date and dump N/e .37N people to get a sense of the overall quality of the field. In the second stage, you continue down the list, and you marry the first person that is better than everyone you met in the first stage. (If you reach the end of the list, and the last person is not the best, then the algorithm is indifferent; you can marry them or not.) There is a theorem that supposedly states that following this strategy maximizes the likelihood of marrying the best possible partner of those on your original list.

This algorithm is the subject of the first chapter of Algorithms to Live By, by Brian Christian and Tom Griffiths,1 and has been repeated in recent articles in The Washington Post,6 Business Insider,1 Slate,5 and NPR.4 The headline in Business Insider makes the advice even simpler: 26 is the perfect age to get married.

If this advice seems dubious, your intuitions are working well. Taken literally, the advice is crazy, because the assumptions of the underlying theorem bear no relation to the real world of dating and marriage.

I tell a tale to illustrate the problems with the algorithm. (A version of this tale in verse can be found at Davis.2) Strephon lives in Arcadia with 100 eligible bachelorettes. He is happy to date them all, so N = 100. Therefore, following the algorithm, his plan is first to date 37 of them, and then to marry the next one who is better than any of those 37.

However, the course of following algorithms never did run smooth. Date 17 is Chloe, who is amazing. Strephon is completely smitten. However, a theorem is a theorem, and Strephon can easily calculate that the probability is 0.83 that someone he has not met yet is even better than Chloe. Goodbye Chloe.

The next 34 dates go by with no magic. Date 52 is Phoebe. Phoebe is even more amazing than Chloe. Patting himself on the back for his wisdom and patience in passing up Chloe, Strephon proposes to Phoebe. For Phoebe, Strephon is date #40 out of 75, so she is in her second stagea and she really likes him. Sadly, though, she liked Colin, her #15, even better, so no dice.

Forty-five more women come and go. Date 98 is Daphne. Daphne is as amazing as Chloe except that she listens to the controversial avant-garde composer Karlheinz Stockhausen, but Strephon can live with that. The probability that one of the remaining two women is better than Daphne is only about 0.06. However, the goal of the algorithm is to marry the best partner, and Daphne is definitely not the best partner, since she is inferior to Chloe. Strephon knows better than to contravene an algorithm endorsed by a professor at Berkeley and published in the Washington Post. Goodbye Daphne.

What the algorithm prescribes in the case where Daphne is better than Chloe but worse than Phoebe is not clearly specified; it depends on whether the goal is to marry the best partner of all those on the list, or to marry the best partner who would have accepted you.

You might suppose that Strephon could try calling Chloe and begging for forgiveness; but the theorem that Strephon is relying on assumes that is impossible. By assumption, Chloe has already married someone else.

Enough of the melodrama; what is the math? The theorem is as follows: Suppose you will be presented with a sequence of options, from which you are to select one. At each stage, you must choose the current object or you can pass on it, but either way, your decision is irrevocable. Suppose further that:

  • The only pertinent information you get about the candidates is ordinal. That is, you can judge how the new candidate compares to the earlier ones, but you cannot assign a meaningful cardinal score.
  • Your goal is to maximize the probability of getting the best of the N candidates; you are indifferent between all other outcomes.

In that case, the preceding algorithmpass on the first N/e, then choose the next one that is better than all thoseis provably optimal. Following that algorithm, the probability is about 1/e that you will get the best partner.

The problem and its solution were first published in Martin Gardner's "Mathematical Games" column.3 Chapter 1 of Christian and Griffiths1 and its 15 pages of notes contain a thorough discussion of the problem's history, variants, and applications; see also the Wikipedia entry, Secretary Problem.8

Given the extreme restrictions, it is easy to see that the optimal rule to follow must have the form, "Pass on the first f(N), then choose the next one that is better" for some function f(N). Obviously, a candidate that is not better than all those seen so far cannot be chosen, since it cannot be the best. Moreover, all the information that you have in choosing is the sequence of ordinals; and it is easy to see that the order in which the ones you have passed on carries no useful information.


The assumptions of the theorem are almost never even approximately satisfied in real-world situationsand are especially far-fetched in regard to dating.


For example, suppose that for N = 100 someone were to propose an alternative rule: "Pass on the first 37, then wait until someonecall her Aliceis better than those 37, then continue to wait until someone elseBettyis better than Alice." Suppose that Strephon executes this, meets Alice at 40, and meets Betty at 51. Then all the useful information that he actually has is that Betty is better than 50 women out of 100. Consider an alternative order in which Betty is still 50, but Alice is now 17. Then Betty is now the first person he has met better than the first 37, so by the rule, he should pass on Betty. But there is no significant difference between the first and second situation in what Strephon knows, since the ordering was random.

The fact that f(N) converges to N/e is, to my mind, cute, but not very profound. The proof is an exercise in combinatorics, with nothing particularly insightful.

It seems to me the assumptions of the theorem are almost never even approximately satisfied in real-world situationsand are especially far-fetched in regard to dating. There are many problems. I will first mention a few that seem to me comparatively superficial and open to technical solutions. The assumption that you cannot go backthat Strephon cannot go back to Chloeis often false, but it is reasonable in cases like real-estate hunting or searching for a parking space where there is a lot of competition for desirable resources. It is arguably reasonable as regards dating. The assumption that you know the value of N in advance is often dubious, but certainly there are cases where N can be reasonably estimated. The analysis ignores transactional costs; dating takes time and effort.

Then there are more fundamental problems. The assumption that seems most far-fetched is the "best or nothing" assumption: you want to maximize the probability of getting the best option and are completely indifferent between the other outcomes.

I cannot think of any choice problem where this is a reasonable assumption. This becomes clear if the assumption is cast in terms of maximum expected utility theory, the standard normative theory of choice. This assumption corresponds to assigning a utility of 1 if the best item is chosen and of 0 if it is not. But the agent never knows whether the item he has chosen is actually the best, and therefore does not know his own utility. For instance, suppose that Strephon decides to ignore the algorithm and marry Chloe even though she is only date number 17. Then his utility is 1 if she actually is the best partner for him and 0 if there is someone better, despite the fact that he has no idea which is the case and that his state of nuptial bliss is presumably unaffected. I cannot find any axiom that prohibits this kind of utility function, but it seems counter to the general spirit of what is usually meant by a utility.b


It is not good to promote the view of romantic partners as commodities that are inspected and chosen rather than people whom you woo and who woo you.


The assumption that there is only ordinal information is also problematic. This is critical in Strephon's decision to reject Chloe; it is assumed that there is no difference between her being slightly better than the others he has seen and her being enormously better. In most real situations, once you have seen a reasonable number of options, you have some idea of the ordinary range and you can spot an astonishing outlier.

These objections apply in all cases of choice. For courtship specifically, there is another serious problem. Chloe, Phoebe, and Daphne are not parking spots, waiting there to be chosen; they are not even stochastic processes that randomly accept or reject marriage proposals. At least in our society, they are players engaged in much the same game as Strephon. Suppose that Phoebe's and Strephon's preferences are uncorrellated; that is, Phoebe's preferences are independent of the fact that Strephon proposed to her. Then, even given that Phoebe is in stage 2, the probability that she prefers Strephon to all the men she met in stage 1 is only about e/N. Of course Strephon may have another chance to propose; but the average number of stage 2 candidates who are better than all the stage 1 candidates is only about e 1. There will be a lot of unmarried people in Arcadia.

Probably preferences between potential partners are substantially correlated, which makes things better; but they are also probably correlated across rivals, which makes things worse. In any case, the analysis in this situation would be completely different (and very difficult).

Lovers are proverbially unwise, but I think that most would have the good sense to ditch the algorithm when its advice is obviously idiotic. So I am not actually very worried about Strephon and the rest. However, it is not good to promote the view of romantic partners as commodities that are inspected and chosen rather than people whom you woo and who woo you. Moreover, publishing senseless advice as the unquestionable dictate of mathematics strengthens the general view that mathematics and science are just theories that have nothing to do with the real world.

Back to Top

References

1. Christian, B. and Griffiths, T. Algorithms to Live By: The Computer Science of Human Decisions. Henry Holt, 2016.

2. Davis, E. The 37% Rule. 2017; http://cs.nyu.edu/faculty/davise/Verses/ThirtySeven.html

3. Gardner, M. New Mathematical Diversions from Scientific American. Simon and Schuster, 1966.

4. Krulwich, R. How to marry the right girl: A mathematical solution. National Public Radio, May 15, 2014.

5. Parker, M. The secretary problem: An algorithm for deciding who to marry and other tough choices. Slate (Dec. 17, 2014).

6. Swanson, A. When to stop dating and settle down, according to math. The Washington Post (Feb. 16, 2016).

7. Weller, C. A mathematical theory says the perfect age to get married is 26here's why. Business Insider (Nov. 25, 2016).

8. Wikipedia. Secretary problem; http://en.wikipedia.org/wiki/Secretary_problem

Back to Top

Author

Ernest Davis (davise@cs.nyu.edu) is Professor of Computer Science at New York University.

Back to Top

Footnotes

a. There is a dating service in Arcadia that matches first-stagers with first-stagers and second-stagers with second-stagers.

b. Richard Cole points out that the algorithm has the property that, regardless of the distribution of utilities over items, which is generally poorly known and even poorly defined, the expected value of the utility of the outcome over random orderings is at least 1/e of the optimal choice, assuming all utilities are non-negative.


Copyright held by author.
Request permission to (re)publish from the owner/author

The Digital Library is published by the Association for Computing Machinery. Copyright © 2017 ACM, Inc.


Comments


Roland Kwee

Thanks for your clear analysis of this fun topic. However, the false presumption is that one should look for the "best" partner. Indeed a modern disease. To increase the chance that your genes will survive, and to live longer, healthier, and happier, you should only look for the minimal qualifying partner. The economic theory of diminished returns suggests that the effort for finding another partner that is better than the previous one might outweight the advantages of that better partner. And the article described the bigger chance to end up with no partner at all, or be forced to propose to one that is definitely not the "best", if you are too selective. Perhaps your article could have been shorter, and there are many other, more useful, math riddles.


Displaying 1 comment