Why am I still single? The mathematical justification.

I have been looking for a life partner for a very long time. There are a ton of reasons why I couldn’t find one yet. In this post, I am going to describe a mathematical reason behind this. I learned about this in a talk at CERC by prof. Adrian Vetta about his recent paper. Thanks to Gabriele and Federico for organizing this talk. In general, I love it when mathematicians can explain very complex stuff using very abstract models. This post will be a bit technical. But stay with me. I'll explain things in simple words.

We start by looking at a famous problem called Stable marriage problem. Let’s say we have 4 boys (Jafar, Scar, Hades, Beast) and 4 girls (Ursula, Cruella, Maleficent, Gothel). Let’s assume that they are all bachelors. They want to get married. In real world, we face a lot of constraints for getting married. We care about personality, location, habits and what not! Mathematicians abstracted all of that by the concept of preferences. Each boy has a preference. They rank each girl from most preferred partner to least preferred partner. Each girl also does the same. For example, the preference list of Jafar could be: [Maleficent, Gothel, Cruella, Ursula]. That means Jafar prefers Maleficent the most and Ursula the least. Our job is to help them find a match.

But be careful, the match has to be stable. What does that mean? Let’s say Jafar is matched to Ursula and Scar is married to Cruella. However, if Scar prefers Ursula over Cruella and Cruella also prefers Scar over Jafar, then the match is not stable. Scar and Cruella are going to break up with their partners and run away together. We want to avoid this. So, in abstract terms, matching is unstable if there is a boy-girl pair who prefers each other over their current partners.

Do such stable marriages always exist? Yes. As long as each boy and each girl give their full preference list. Let’s see an algorithm to compute one. We consider the following instance.

Boy preferences:
Jafar:  [Maleficent, Gothel, Cruella, Ursula]
Scar:  [Ursula, Maleficent, Gothel, Cruella]
Hades:  [Gothel, Cruella, Ursula, Maleficent]
Beast:  [Cruella, Ursula, Maleficent, Gothel]

Girl preferences:
Ursula: [Jafar, Scar, Hades, Beast]
Cruella: [Scar, Jafar, Beast, Hades]
Maleficent: [Hades, Beast, Jafar, Scar]
Gothel: [Beast, Hades, Scar, Jafar]

The algorithm goes as follows:

1. Select a boy who is still single.
2. That boy is going to ask his next preferred girl, who still hasn’t rejected him.
3. The girl can be single or matched to someone else.
   a. If the girl is single, she temporarily accepts that boy as her match.
   b. If the girl is matched to someone else, she checks her preference list and if the boy is more preferred than her current match, then she accepts him as her match (temporarily again). Otherwise, she rejects him.
4. Repeat until each boy is matched.

It has been proved that this algorithm produces the stable marriage pairs. Now, you might ask, why go through boys list in the algorithm and not the girls list? That is, in the first step, we select an unmatched girl and let that girl ask out boys. In other words, we could have reversed the roles of boys and girls in the algorithm, and it would still produce stable marriage. The question is: Does that matter? Let’s see.

The above algorithm produces the following matching: {Jafar - Maleficent, Scar - Ursula, Hades- Gothel, Beast - Cruella}. If we instead use the algorithm from the girls’ side, it produces the following matching: {Jafar - Ursula, Scar - Cruella, Hades - Maleficent, Beast - Gothel}. So, the answer is Yes, it does matter. In the first matching, each boy gets his first preference (hence they won’t cheat and the matching is stable). On the other hand, in the second matching, each girl gets her first preference. There are in between matching as well. For example, {Jafar - Cruella, Scar - Ursula, Hades - Gothel, Beast - Maleficent}. In this matching, not all boys get their first preference and not all girls get their first preference.

Since our world is male dominated, we are going to use the above algorithm for our further analysis. This is the best case for boys and the worst case for girls. This is where things get interesting. Girls are obviously not going to be happy with that. They want to now hack the algorithm to get better preferences. Turns out they don’t have to do much.

What if the girls say that they would rather stay single than marrying to a low preference partner? In our example, let’s say each girl rejects the proposal below their second preference. In this case, the above algorithm produces {Jafar - Cruella, Scar - Ursula, Hades - Gothel, Beast - Maleficent}. Each girl gets her second preference, and only two boys get their first preference. Much better result for girls compared to the first one. But not so good for the two boys, who are now getting their third preference instead of first.

The girls can go even further and reject everyone who is not their first preference. They would get their first preference as long as there is no clash (two girls having same boy as first preference). Well, this is an ideal case scenario for girls. In reality, it would take a long time to empower all girls. But it turns out, they don’t need to go that far. If only Maleficent rejects her third and forth preferences, the same girl-second-preference matching we saw above, is produced. Not just Maleficient but also Cruella (who got her third preference in the boy-first-preference matching) is benefited, even though Cruella didn’t change her behavior. Isn’t that amazing! Only one empowered girl made a big difference.

It turns out that not many girls need to be empowered to completely turn over the male dominated society. In the paper, they proved that out of say ‘N’ girls, only O(log(N)) girls need to strategize to get the most preferred matching for girls. That’s a very small number. Which is not good news for boys. The society is not completely male dominated to begin with (i.e., our reason for picking boy friendly algorithm is not so valid). Even if it was, a small number of empowered girls can turn all the tables.

I believe this is one of the major reason behind why I am struggling so much to find a partner (along with my personality, location, and other hard to justify decisions). There were times during which my preferences were so lowered that I would have accepted almost anyone as my life partner. But even that didn’t help me find one. What to do? The answer lies in the analysis above and in a not so math heavy post of Nupur (my ex teammate at Google Bangalore). If having self-respect and higher standards can help girls, it can also help me. So, I raised my standards again, and now the universe is struggling hard to find me a partner. I trust the algorithm to eventually help me find one! At least, I get to keep my self-respect otherwise.

Reference:

Ndiaye, N., Norin, S., & Vetta, A. (2021, September). Descending the Stable Matching Lattice: How Many Strategic Agents Are Required to Turn Pessimality to Optimality?. In International Symposium on Algorithmic Game Theory (pp. 281-295). Springer, Cham.

The paper can be accessed at: https://arxiv.org/pdf/2007.15748.pdf

My Favorites:

Video of the week: French revolution (In Hindi, with English captions)

Quote of the week: “The trouble with being in the rat race is that even if you win, you’re still a rat.” — Lily Tomlin