If you happen to be a student at Berkeley, I highly recommend CS 70 (Discrete Mathematics and Probability Theory), especially when it’s taught by Anant Sahai, who’s a delightfully classic hardass immigrant professor who will probably teach you a lot about math and at least something about life.1 This class introduces several of my favorite pieces of math ever: RSA, Shamir’s secret sharing, error correcting codes. But the most profoundly affecting was easily the Stable Marriage Problem. The Secretary Problem can only dream of having this much influence on my dating life.
I gather the woke feminist libs renamed this the Stable Matching Problem, but I present the Stable Marriage Problem in its original based trad formulation:
There are N men and N women.
Each man ranks all the women in order of who he’d be most excited to marry, and each woman similarly ranks all the men. (Importantly for the headline result, everyone would prefer being married to someone over being single; I discuss modifications to allow for people staying single in footnotes.2)
The goal is to marry everyone off to someone of the opposite sex such that all N resulting marriages are stable. This means there does not exist any two marriages, call them Alice-Bob and Carol-Dave, where Alice and Dave (or Bob and Carol) mutually prefer each other to their respective spouses. If Alice ranks Dave higher than Bob, and Dave ranks Alice higher than Carol, then we assume Alice and Dave will break off their marriage and get with each other instead — that is, their marriages are unstable.3
For example, imagine a world with three men (Adam, Bob, and Charles) and three women (Alice, Betty, and Carol) with the following preference-orderings:
Women
Alice: Adam > Bob > Charles
Betty: Adam > Charles > Bob
Carol: Bob > Adam > Charles
Men
Adam: Betty > Alice > Carol
Bob: Betty > Carol > Alice
Charles: Carol > Alice > Betty
In this setting, the following is a set of three stable marriages:
Adam marries Betty
Both are with their respective top choice
Bob marries Carol
Carol is with her top choice
Bob would prefer to break up with Carol to get with Betty, but Betty would decline because she’s with her top choice Adam
Charles marries Alice
Alice would prefer to break up with Charles to get with either Adam or Bob, but Adam and Bob are both with women they like better than Alice
Charles would prefer to break up with Alice to get with Carol, but Carol is already with her top choice Bob
As numbers grow, it’s not immediately obvious you can always even find a full stable set of marriages. Imagine a village of 1300 men and 1300 women who create 1,690,000 preference data points between them that could be arbitrarily inconvenient and incompatible: maybe Bob loves Alice but Alice barely thinks about Bob and is in love with Carl who won’t give her the time of day as he pines after Diane who doesn’t have a thought for anyone but Edmund…imagine being a matchmaker handcrafting 1300 marriages that all work with each other.
In fact, you can always create N stable marriages with absolutely any set of preference orderings. The easiest way to prove this is to demonstrate the algorithm you can run to reliably generate a valid set of marriages.
The classic solution, the Gale-Shapley algorithm, works over a series of days (at most N^2 days, it turns out).
On the first day, every man asks out the top woman on his list, and every woman starts dating the man she likes best out of the ones who have asked her out. In our example, Adam and Bob would try asking out Betty, and Charles would try asking out Carol. Betty would start dating Adam (rejecting Bob), Carol would start dating Charles (her only offer), and Alice would remain single (no one asked her out).4
On every subsequent day, all the rejected men go down to the next woman on their list who hasn’t rejected them yet, regardless of whether she’s already dating another guy. All women get to choose whether to stay with their current boyfriend (if they have one) or accept one of their fresh offers. In our example:
On day 2, Bob (who was rejected by Betty) would try asking Carol out (who’s currently dating Charles). Since Carol likes Bob better than Charles, she would break up with Charles and start dating Bob.
On day 3, Charles (who was just rejected by Carol) would try asking Alice out. Since she’s currently single, she accepts.
On day 4, there are no rejected men left and the algorithm terminates.
Once there are no more rejected men floating around,5 all current romantic relationships are made permanent. In our example, we generate the matching from the previous section: Adam-Betty, Bob-Carol, Charles-Alice.
You can prove that this algorithm always terminates with everyone married, and that the marriages generated at the end are always stable.6
Okay, so we know this algorithm always puts everyone in some marriage where all those marriages are stable with respect to one another. But most preference-rankings admit multiple distinct sets of mutually stable marriages — which one does it find? Consider these preferences:
Women
Diane: Dave > Ed > Frank
Emma: Ed > Frank > Dave
Flora: Frank > Dave > Ed
Men
Dave: Emma > Flora > Diane
Ed: Flora > Diane > Emma
Frank: Diane > Emma > Flora
There are three different solutions that all constitute a complete set of stable marriages:
Dave-Diane, Ed-Emma, Frank-Flora. These marriages are stable because the women all have their top choice.
Dave-Emma, Ed-Flora, Frank-Diane. These marriages are stable because the men all have their top choice.
Dave-Flora, Ed-Diane, Frank-Emma. Everyone has their second choice, but all marriages are stable because attraction is never mutual.7
What would our algorithm do? Well, on the first day Dave would ask out Emma, Ed would ask out Flora, and Frank would ask out Diane…and that’s it. All women would accept, no men would be rejected, and everyone would be married off on day one. The men all got their top choice, and the women all got their last choice.
In fact, the Gale-Shapley algorithm is always male-optimal. “Male optimal” doesn’t mean men on average get a better deal than women on average: it means all men simultaneously get the best possible wife they could have gotten in any possible stable arrangement.8
This is an extremely strong property.
Imagine New York City, which has roughly 1.5 million single men and women. There are potentially thousands of stable marriage arrangements consistent with their preferences. Imagine we ran the Gale-Shapley algorithm and it found one particular set of 1.5 million marriages.9
Now consider one solitary guy, Jake, who ends up married to Jane.
Jake likes Jane well enough, but she’s a 7 at best, he thinks, and sometimes he wistfully wonders if in some other world he could have gotten with the 9 of his dreams. Then one day, straight out of a bad Adam Sandler movie, God Himself comes down and says “You know what Jake, I will break everyone up with their spouse now and personally arrange everyone’s marriage in New York City so that you personally end up with the best possible woman…though of course we wouldn’t want her to break up with you right after I do that, so I’ll look for whatever stable matching leaves you, Jake, personally best off out of all the millions of men and women in this city.”
It turns out He would fail. And He would also fail to do any better for Adam, or Bret, or Kevin, or Ezra, or any other guy — even if all He cared about was helping that one dude!
And at the same time, the algorithm is always female-pessimal: of all the possible valid stable marriages, every single woman gets her worst possible stable husband.10 Any rearrangement God tries would probably leave Jane stably married to a man she likes better than Jake!
As a woke feminist lib myself, I don’t see the algorithm here as fundamentally “male”-optimal and “female”-pessimal: it is asker-optimal and askee-pessimal. The problem rewards agency and punishes passivity, to an astonishingly strong degree.
Working out all these proofs and a zillion variants in Soda Hall at 3 am when I was nineteen had a real impact on how I approached the rest of my life.11 I’ve initiated almost all my romantic relationships. When I saw that GiveWell was looking for rising seniors to be summer interns, I emailed them and was like “I’m a rising junior but can I do it anyway?” I went on to work at Open Phil (which spun out of GiveWell) for nine years. I’ve lived in four group houses and initiated all of them. Most recently, I asked a couple with two kids to live with me and my husband after knowing each other only about a year, which even I thought was a bit nuts — they not only founded an amazing house with us, but also told me they would never have had the courage to ask us.
There are a lot of ways to achieve this mindset that involve much less math. Some of the assumptions of the problem decrease the strength of the result (though others increase it IMO).12 I 70% just wanted to tell you about some cool math. But I think the core dynamic in the proof of asker-optimality and askee-pessimality does apply to real life. If you only ever pick from offers you get, you never try anything unless someone out there already knew you and liked you enough that they took the trouble of coming to you. If you ask for stuff, you get to pick from among the entire universe of potential options theoretically available to you — and who knows, it might work out.