Why the First Person to Propose Always Wins (According to Maths)

Why the First Person to Propose Always Wins (According to Maths)
Credit: unsplash

Imagine pairing up 100 men and 100 women based on their personal ranking lists. You assign everyone a partner. Later, Person A and Person B (where A is a man and B is a woman) realise they aren't paired together even though they both rank each other higher than their actual assigned partners. If A and B leave their partners to run off together, call this a ‘rogue’ pair. This causes the entire matching system to collapse. This is also known as the Gale-Shapley Algorithm. [1]

Mathematicians David Gale and Lloyd Shapley later proved that stable matching is guaranteed to exist, no matter how conflicting everybody’s preferences are. [2]

Let sets M and W be two independent sets with equal number of people (n):

Each man of set W follows a strict rule of preference ordering over the set of women W.

We denote this using the symbol:

For instance, we can have a case where:

This means that m_1 strictly prefers w_2 over w_1, w_1 over w_4, and w_4 over w_3.

Similarly, each woman of the set W (w_1 to w_n) also has a strict preference ordering over the set of men M.

Consider this bijection which is always a one-to-one correspondence:

Every unengaged man proposes to the top woman on his preference list whom he hasn’t approached yet. Each woman then rejects every proposal except the one highest on her list. Each man who gets rejected goes further on to propose to the woman of his next choice. This pattern continues on and on until 100 pairs of satisfied couples form, which is what represents. [3]

This method is guaranteed to have zero ‘rogue’ pairs and we can prove this via proof by contradiction. 

Conclusion

This method has been used in countless real life situations, such as Medical Residency Matching, where more than 44,000 students medical graduates in the US are paired with hospital residences every year. The Gale-Shapley Algorithm can also be used in optimising preferences for each person based on how they ranked things individually.


Bibliography

[1] https://www.csuohio.edu/sites/default/files/The%20Stable%20Marriage%20Problem%20and%20Gale-Shapley%20Algorithm.pdf Accessed: 2026-10-05

[2]

https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm Accessed: 2026-10-05

[3]

https://mindyourdecisions.com/blog/2015/03/03/the-stable-marriage-problem-gale-shapley-algorithm-an-algorithm-recognized-in-the-2012-nobel-prize-and-used-in-the-residency-match/ Accessed: 2026-10-05