A mathematical solution to the love polygon

Why you should ask your crush out if you want to have a happier life.

Daily Algorithms #4: Gayle and Shapely Algorithm for Stable marriage problem.

You are a strong independent woman. You are capable of taking care of yourself. However, biology has imposed the essence of love on the human genome, which forces us to find our other half throughout our lives — our significant other. In this race for love, every species has its own rules; in some, males project their artistic capabilities through exuberant displays of beauty, signing up females for mating, and in some the females do. For us humans, the question of who asks whom out has shifted significantly throughout the ages, to this time and age, where both males as well as females, ask each other out. In this blog post, I will tell you why you, as a strong independent woman, should ask him / her out if you want to maximize your chances of getting your dream man / woman.

Love triangles are no news to us. We have been quite familiarized with love triangles, quadiletrals and other love polygons for a long time thanks to the daily soap opera that goes on in our television and everyday lives. Everyone is looking after the other person’s husband / wife. No one is satisfied. Well, the question now is, can we make everyone satisfied? Not totally satisfied per se, as humans are by nature dissatisfied creatures. But satisfied just enough to ensure that they don’t cheat on each other.

Pangela and Jwight. A perfect couple?

Let’s analyze the mechanics of cheating in a relationship then. Let us consider two couples Dwight-Angela and Jim-Pam. Dwight will cheat on Angela only if he fancies Pam more than her, and Pam fancies Dwight more than Jim. Or Jim can cheat on Pam for the same reasons. We see that somone is able to cheat their partners, only when the person they fancy fancies them as well. So given some number of men and some number of women, is it possible to generate such a pair so that no one cheats on each other?

Let’s consider the traditional heterosexual relationship. For a relationship to be formed, there must be a man and a woman. That means that from N men and N women, N couples can be formed. At the first stage, no one is married to anyone else, and everyone has their favoriates. Everyone has a priority list; no one will pine for their crush after their crush leaves them for someone else. Everyone is objective. Pam says if Jim does not fancy her, then she will settle with Dwight if her decides to propose to her. Straight to the point. No complications!

Let’s formulate a system (algorithm):

1. Take N men and N women
2. Pair up the N men and N women
3. If anyone would rather cheat than be with their current partner, pair up the cheaters into a couple
4. If everyone is Okay-ish with their relationship and promises not to cheat (or has no way to cheat) then stop!

Well, human relationships are old and this problem is an old one too! People have thought about this and tried to solve this problem. An algorithm, formulated by David Gayle and Lloyd Shapely outlines the following steps to solve this problem:

1. Take N men and N women
2. Each man and woman has their own priority list, i.e. a list in descending order of attraction to the opposite sex. For the example given, Pam’s list might look like [Jim, Dwight]
3. Until everyone is engaged do the following:
4. Each man takes his list and crosses off the first woman. Then he proposes to the first woman.
5. Two things can happen:
6. If the woman has not been asked by any other suitor, then she accepts his proposal and they get engaged.
7. If the woman is already engaged, then she looks at her own preference list. If she prefers the suitor to her fiance, then she breaks off her engagement and gets engaged to the suitor.
8. After the engagements are complete, marry all the couples.

This algorithm is guaranteed to produce a pairing in O(n²) time complexity.

Let’s analyse this algorithm further.

1. Does it terminate? Do we get to the end?

• Of course it does! Why else would I be blogging about it otherwise? To prove this fact, let us consider the algorithm itself.
• Let’s consider a scenario where every man proposes to the same woman. In this condition, the woman will settle with the man she likes the most. This means that they won’t cheat on each other ever again! So during each proposal round, where N men propose, at least 1 marriage will occur (worst case scenario when every man has the same preference list). This means that for N men, N² proposals will be required in the worst case scenario.

1. Is the result a stable marriage (no cheating occurs)

• To answer this question, let us consider a reverse scenario. Let us consider there are two couples Jim-Pam and Dwight-Angela, and Pam and Dwight want to cheat on their partners with each other. Well, for this pairing to have happened, as Dwight clearly fancies Pam over Angela in this reverse scenario, he would’ve proposed to Pam first. Pam, even though she could’ve been engaged to Jim at the time, would’ve accepted Dwight’s proposal. But Pam is engaged to Jim, so that means she prefers Jim to Dwight. Hence, no cheating can occur. In other words, Jim-Pam and Dwight-Angela are stable couples.
• Even if one person in a relationship is dissatisfied with their current partner, they would have to trade up to get a better partner, and if the better person already has a person they are satisfied with, they would never cheat on them.

1. Who gets the better deal?

• This is an interesting part of analysis of this algorithm. In the above case, clearly, the men get a better deal, and the women need to settle. In a generalized scenario, the suitor would get the best they could and the suited would have to settle for less.

Let’s consider a list of preferences. The capital letters and small letters denote the set of men and women. Men = {A, B, C} and women = {a, b, c}. Their preferences are as follows:

• A — a, b, c
• B — b, c, a
• C — b, c, a
• a — C, B, A
• b — A, B, C
• c — A, B, C

In the first round, A proposes to a, who accepts. Then B proposes to b who accepts and C proposes to b and gets rejected. So far, the pairs are {A, a} and {B, b}. Then C proposes to c, and gets engaged. Hence a stable marriage is formed as : { (A, a), (B, b), (C, c)}.

Let’s consider the reverse scenario where a proposes to C and C accepts. Then b proposes to A and A accepts. Then c proposes to A and gets rejected. The pairs so far are {(a, C), (b, A)}. Now, c proposes to B and B accepts. Then a stable marriage is formed as {(a, C), (b, A), (c, B)}.

In both of these scenarios, considering pair (A, a), and pair (b, A), we see that a likes A the least but A likes a the most, and they end up getting married. Similarly, b likes A the most but A likes b not all that much. Still, they end up getting married. In these both scenarios, we can see that the suitors end up with their highest possible preference and the suited need to settle.

Thankfully for us office fans, Jim and Pam and Dwight and Angela will always be perfect.

Pangela and Jwight are not real, they can’t scare you. Shhh…

Simple as that, right? Unfortunately, human relationships are not algorithms, otherwise, it would’ve been good to see this algorithm in practice. Looking at this, one can come to the conclusion, if you want someone, then propose immediately! No one knows when the next round of proposal will begin.

Get proposing!