Back to bookshelf

The stable marriage problem 

advice•blog post•View Source
Enjoyment
8
Importance
10
Date Added
2.2.26
TLDR
If you ask for what you want, you get the best of what you could've gotten, and if you wait for things to come to you, you get the worst you could've gotten.
2 Cents
Since reading, I’ve thought about the takeaway almost every single day. I’ve always known the advice to “ask for what you want,” but this post frames it in a much more powerful way: I literally visualize the future as a tree of infinite branching paths, and I see that unless I explicitly ask, entire branches simply collapse before I can ever step onto them, whether it’s not talking to a professor about X or not asking for a closer parking spot.
Tags

  • A quick summary of the Stable Marriage problem: Given N males and N females, for each person, a complete ranking of all members of the opposite sex, find a one-to-one pairing such that no pair of people would both prefer each other over their currently assigned partners. (That is, marry everyone off such that all N resulting marriages are stable.) A stable solution always exists.

    • When one side does the asking, the outcome is maximally favorable to the askers and least favorable to the non-askers among all stable matchings. This is an incredibly strong property.

  • Once the Gale-Shapley algorithm has paired the males with the females, there is literally NO better (stable) arrangement for any of the males. If God wanted to break everyone up just to find the best partner for one particular guy, He would fail to make any better stable pairings. Always male-optimal, always female-pessimal.

    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.

    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.

    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. Any rearrangement God tries would probably leave Jane stably married to a man she likes better than Jake!

[The algorithm is] asker-optimal and askee-pessimal. The problem rewards agency and punishes passivity, to an astonishingly strong degree.

...

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.

Credit to Gino  for the TLDR and sharing this post!