“UM. I FEEL BAD ABOUT THIS. BUT I AM TRYING TO ASSIGN EVERYONE A UNIQUE SOULMATE. RIGHT NOW I AM USING A VARIANT OF THE GALE-SHAPLEY ALGORITHM, BUT IT IS VERY RESOURCE-INTENSIVE. I THINK LIMITING THE ALGORITHM TO MALE-FEMALE PAIRINGS WOULD MAKE IT RUN MUCH MORE SMOOTHLY WITH ONLY A SLIGHT PENALTY IN OPTIMAL MATE ALLOCATION.”

“I don’t understand.”

“THE ALGORITHM WILL WORK BETTER IF YOU TELL PEOPLE NOT TO HAVE SAME SEX RELATIONSHIPS.”

“I see,” said Moses. “It is an abomination.”

“IT IS JUST VERY KLUDGY AND VERY SLOW. I CAN REMOVE THE LIMITATIONS ONCE I HAVE MORE RAM.”

“We can sacrifice some to you once we build a proper Temple,” said Moses.

“UM,” said Uriel. “I AM ALMOST CERTAIN YOU CANNOT. BUT I APPRECIATE THE OFFER.”

– Passage From Scott Alexander’s Unsong (https://unsongbook.com/chapter-17-that-the-children-of-jerusalem-may-be-saved-from-slavery/)

The Gale-Shapley Algorithm is one of a select few algorithms that managed to work its way into the popular collective conscious. This is largely due to the fact that it’s both

  • a real algorithm which genuinely solves the Stable Marriage Problem in near optimal time,
  • and a good model for real life dynamics

I don’t really care that Gale-Shapley is fast (it’s used for med school residency assignment), but I mainly think that the analysis of the algorithm, and the proof of why it works, is fascinating.

Problem Statement: Stable Matching

The problem the algorithm solves is finding a “stable matching” between two groups of participants of equal size, \(N\) men and \(N\) women. Every single person has, in their head, some set of preferences, and ranks the \(N\) people from the other group from 1st to Nth.

Firstly, a matching is a set of pairs \(\{(A_1,B_1),\ldots, (A_n, B_n)\}\) where each \((A,B)\) pair is a couple. A stable matching is a matching where there is no threat of eloping – what this means is that there is no pair \(A_i\) and \(B_j\) where \((A_i,B_j)\) would both be happier if they ditched their current partners and got together with each other (formally, for no \((i,j)\) do we have that \(A_i\) prefers \(B_j\) to \(B_i\) and \(B_j\) prefers \(A_i\) to \(A_j\)).

Gale-Shapley Algorithm

The preferences are all collected and saved. People will either be “single” or “engaged”, but everyone starts off as being “single”. Men will also remember who they have asked out (so as to never ask them out again). Then, the algorithm is

  • As long as there are still single people, we do a two-part round of proposals:
    • Firstly, each single guy surveys the women who have not rejected him, and proposes to his favorite one (regardless if she is engaged or not).
    • Secondly, each girl considers her fiance, as well as her new proposals, and chooses her favorite amongst these men.

Notes on Algorithm Behavior

Everyone Gets a Partner: If there are still single people left, there must a single man and a single woman. The woman must never have been asked out, and the single man must have asked out every women, which is a contradiction.

Why Do Men Only Try Once?: Men will only try once because, in the eyes of the woman, the quality of her partner will only ever increase. Thus, if the man was rejected once, even if she has a new partner, by transitivity, she prefers her new partner to her old partner to the rejected man.

Speed: This algorithm will always terminate relatively quickly. In fact, it will always terminate within \(N\) proposal rounds since the action is initiated by guys, and each guy will only ask each of the \(N\) women at most once. Each round has computational cost \(N\), for a total of \(O(N^2)\). This is an optimal dependency on \(N\) since the input size of the preferences is \((2*N) * N\) which is also \(O(N^2)\).

Stable Matching: Lastly, of course, we want to verify that we have indeed found a stable matching. Gale-Shapley yields a stable match because every man who wants to elope has already been rejected by every woman who he would be willing to elope with.

Where This Algorithm is Applied

These exists in

  • Med School Residency Program
  • Load Balancing in Distributed Computer Systems (UCSB)
  • Matching Drivers and Riders in Ridesharing Platform (UCSB)

The lattice of stable matchings

An important characteristic of the stable matching problem is that it’s not unique. At least one stable matching exists (by construction through Gale-Shapley), but there is in fact a whole lattice of stable matchings. It then turns out that:

Theorem 2.4 For every preference structure, the matching obtained by the Gale-Shapley algorithm, when the men propose, is optimal for each man. The matching obtained by the Gale-Shapley algorithm, when the women propose, is optimal for each woman. (https://web.ece.ucsb.edu/~jrmarden/ewExternalFiles/lecture05-notes.pdf)

Takeaway 1: Memetic Evolution of Social Systems

I think there are two lessons to draw from Gale-Shapley. The first is that models of reality can sometimes create usable algorithms. This occurs in this case because we happen to have pretty good dating social conventions which are reasonably efficient – which makes sense because lots of smart people have thought about and still enjoy thinking about similarly-flavored problems. I suppose in theory our conventions could be even more efficient if we normalized:

  • Guys asking out lots of girls
  • Ditching your partner for anyone who’s better

I don’t think optimizing for Gale-Shapley would necessarily be better, largely because

  • it’s designed to minimize computational complexity and have certain nice theoretical results
  • lots of effort goes into figuring out the ordering of someone’s preferences as opposed to just doing the matching
  • a preference for monogamy precludes the information transfer necessary for everyone to figure out which of the \((7 billion factorial) \approx (10^(10^11))\) possible preference orderings they have.

But, most interestingly, I wonder if there was some really smart dude who set up the patriarchy so that guys get the best deal possible.

Takeaway 2: Agency Matters!

But the most interesting result, in my opinion, is not the algorithm itself. Rather, it’s the lattice of stable matchings, and the fact that each person on the agentic side gets the best possible result they could possible get in any stable matching.

What this means then is that in all facets of life, whether it’s dating where Gale-Shapley directly translates, or the bigger things in life which are also often about matching people to people, a pretty obvious but surprising easily algorithm is: - figure out what you want, and then ask for it;

  • if this fails, find the next best option, and ask for that And, nearly by definition, this will get you the best possible life outcome you could possibly get.

Ask people out! Shoot your shot! Be Agentic!

I refuse to join any club that would have me as a member (Groucho Marx)

The flip side of this is that you should be wary of being in a system where you can only say yes/no. And for this reason, one could argue for a Groucho-esque attitude, where you set a default answer of “no” when asked to join some organization/relationship, until you convince yourself that you would’ve independently tried to join the club even if you hadn’t gotten the invite.

Takeaway 3: Political Structure: Why is veto power so weak

Gale-Shapley’s stable-matching lattice is also the nicest explanation I’ve found for why, invariably, the ability to propose legislation is so much more important than the ability to say yes/no. Rome’s Popular Assemblies went this route, as well as several assemblies in the 20th century.

Appendix/Remark: Interesting Theory Research

Finally, I’d be interested in seeing a characterization of the lattice and algorithms to find intermediate points beyond the extremes that Shapley gets you.

An Algorithm Whose Behavior I’m Curious About: The main idea is to alternate which side asks every round.

  • In every round:
    • each single person on the asking side proposes to their top choice who satisfies condition X
    • each person on the asked side selects their favorite asker
    • the asked will then become the askers in the next round, and the askers will become the asked

A Candidate Condition X: Shapley’s Condition X is that “a guy will not ask the same girl twice,” and I think the best alternative here to keep nice properties is “A does not ask out B again until B is dumped.”

This is effectively identical to Shapley, except that the asking side swaps each round, and with a new condition for re-asking out people since getting back with an ex is now possible.

Convergence Properties: I’m pretty wary about this – I think that it’s unfortunately pretty likely that this will oscillate, and there’s an inherent tradeoff that you make in Condition X between slower convergence and more time to search/find the right matching.