The stable marriage problem
Or, ask for things
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.
The problem
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 solution
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
But which solution?
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!
Ask for what you want
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.
He notoriously opened his first lecture with a slide breaking down a 16-waking-hour day. IIRC he allocated something like 2 hours to eating, personal hygiene, and personal time, leaving 14 hours for studying.
One simple way to modify the setting to accommodate singleness is by introducing 2N new dummy people: N new “men” corresponding to each woman named Alice_being_single, Betty_being_single, Carol_being_single,… and N new “women” corresponding to each man named Adam_being_single, Bob_being_single, Charles_being_single,…
The dummy variable corresponding to a given real person will always rank that person at the top of its preference ordering (e.g. “Alice_being_single”’s preferences would be Alice > [everyone else, order doesn’t matter]); the real person can put that dummy variable anywhere they want in their preference ranking. So for example, Alice’s preferences might be Adam > Bob > Alice_being_single > Charles.
Note that this is not the most efficient way to incorporate singleness; it’s just the one that leaves the algorithm and all the proofs entirely unchanged.
That is, assuming no commitment devices and other transaction costs (as you’ll see the qualitative advice you can extract from the stable marriage problem is only strengthened if you assume this).
In the variation allowing for singles, the dummy “men” Alice_being_single, Betty_being_single, and Carol_being_single would also ask out their top choices Alice, Betty, and Carol respectively, meaning all women will have at least one offer on day one. If for example Carol preferred being single to dating Charles, she could choose to “date” Carol_being_single instead and reject Charles.
The algorithm will still terminate with no rejected men left in the version that allows singleness, because every man who was rejected by all the real women he would have wanted to marry goes on to ask out his personal dummy variable (e.g. Bob asks out "Bob_being_single"), which will always accept his offer (since he's always its top choice).
Sketch of the proof that the algorithm terminates: Each of the N men can only make N offers before they run out of offers to make, so in the worst case every single man would have to ask out every single woman before people find their matches — that’s at most N^2 days even if only one guy proposes per day. There can’t be any infinite loops (e.g. Alice gets with Bob, then rejects him to get with Carl, then rejects him to get back with Bob) because a woman will agree to date a man if and only if he’s a strictly better choice than her current partner.
Sketch of the proof that the matches are stable: suppose for the sake of contradiction that they’re not stable, i.e. there are two couples, Adam-Betty and Charlie-Diane, such that Adam and Diane prefer each other to their respective spouses. But because Adam preferred Diane to Betty, he would have asked Diane out before he asked Betty out. If Diane was already dating Charlie at that point, she would have ditched him to get with Adam — and if she wasn’t already dating Charlie and Charlie asked her out later after she was already dating Adam, she wouldn’t have said yes. Therefore the algorithm wouldn’t have found the Charlie-Diane marriage in the first place.
For example, Frank would prefer to leave his wife Emma to get with Diane, but Diane likes her husband Ed better than Frank; the same dynamic applies to all six people — the person they like better doesn't like them better.
Sketch of the proof for male-optimality: Consider an arbitrary guy Adam. Assume for the sake of contradiction that Adam ends up with Betty, but in a different universe he could have instead been in a stable marriage with Carol, who he likes better. Because Adam likes Carol better than Betty, he must have tried asking Carol out first, and Carol must have rejected him. The only reason she’d do that is if she was already dating a guy she liked better (call him Dave). But Dave will never leave Carol once he’s matched with her! He went down his list in strict order of decreasing preference, and she was the best girl who said yes to him — only rejected men go on to ask out another women. This means that in any set of pairings containing Adam-Carol, Dave must be with a guy he likes less than Carol. Therefore Adam-Carol would be unstable: Carol and Dave would prefer each other to their spouse.
Yes, I know it would take a very long time for people to even generate their preference rankings and to run the Gale-Shapley algorithm with N of 1.5 million.
Sketch of the proof for female-pessimality: Consider an arbitrary woman Alice. Assume for the sake of contradiction that Alice ends up with Bob, but in a different universe she could have stably been married to Charles instead, who she likes even worse. We know Alice is Bob’s best stable match, so there’s no way for Alice to end up with Charlie: Alice and Bob would break up with their partners and get with each other.
Was I just naturally an aggro and forward person looking for a framework that resonated with my pre-existing proclivities? Yes. But also the argument was both true and genuinely moved me further in this direction than I would have been left to my own devices.
The most important factor cutting against this result is that in many cultures you’ll experience social sanction for asking for something “above your station,” which genuinely harms your future opportunities. But IMO you should try to find your way into ask cultures that do this less if you can; they tend to be more dynamic, fun, and positive-sum. Another obvious factor is that rejection is emotionally painful but the algorithm doesn’t add any kind of cost for that — this is true, but the whole point here is you can unlock a lot of value if you train yourself to get over that cost (not that I’ve done that perfectly by any means). Another, trickier thing is that many women in real life find it to be an active turn off to ask the guy out themselves, and use “did he choose to ask me out?” as a direct filter for a mate. I guess I’m glad I’m autistic enough that this doesn’t bother me too much, because it allows you to try dating shier guys who might be really great overall.
On the other side of the coin, a real life dynamic that makes this result stronger is that commitments tend to be sticky because of transaction costs and commitment expectations: if you start dating someone or working with someone, they’re not going to break up with you or fire you the very next day. This can allow you to get outcomes that are better than the “best stable outcome” in the spherical cow problem.
Very cool. Hadn't heard this. A new and encouraging angle on the whole "don't just take the opportunities life gives you, create your own" kind of thing.
Thanks for reminding me of this, I had forgotten it. It's a fun problem.
The takeaway that asking is often advantageous seems correct to me, and most people should probably ask for things more than they do. I had to learn this even in platonic social life. I used to be terrified of organizing events, but I realized that people usually say yes if you go to the trouble of organizing something.
That said, I think real-life is way more complicated (I'm sure you'd agree), and there are situations where being an asker may be suboptimal all things considered!
Something I've seen a lot of women report is that asking men out often leads to men saying 'yes' because being asked out is flattering and novel for them, but they don't put in much effort because they're not super interested, and often lose interested completely fairly quickly. They wouldn't have asked her out on their own. Of course, this comes with the cost of starting to get invested in someone for weeks or months only for them to bail. Given social norms on who asks whom out, I think "if he was interested, he would" is correct most of the time for straight women, unfortunately*. Not 100% of the time, but often enough that asking out men all the time might not have enough likelihood of success to be worth the downsides.
Another downside of being an asker, not just in a dating context, is you risk exposing yourself to much more rejection. Now yes, this isn't rational to care about in spherical cow land because being explicitly rejected after asking has the same outcome as being passively rejected. But it's psychologically much more difficult to face explicit rejection after asking, and if it happens often enough it's probably not great for your mental health. And poor mental health negatively impacts your ability to achieve your goal. This is the experience of most men on the dating apps.
(I know you talked about this in point 12, but I think you underrate it honestly. I think people can become more resilient to rejection to a point, but I think most will still be hurt by it. I'm also not sure not caring about rejection as much is an autistic thing, it seems orthogonal to that to me. Neurodivergence often is paired with social anxiety in practice.)
Finally, I think a big downside of being an asker is you're always wondering if you could have done better or missed an opportunity. When you're more passive, you simply pick the best option offered to you, and then that's that. I think many people find that position more comfortable and easier to cope with.
*I think this is less true in social circles with lots of shy and/or neurodivergent nerds, where many men might nervous or unsure how to express interest, but that's not most people's circles!