Consider a set of five men and a set of five women. Each man ranks the five women in his order of preference and each woman ranks the men in her order of preference. It is required to pair off the men with the women in such a way that there does not exist a man and a woman who both prefer each other to their current partner.  This is called a stable matching. 

Sounds familiar right? The first episode of the first edition of Love Island Malta presented us with a similar situation. This is, actually, a well-known problem in mathematics, called the Stable Marriage Problem (SMP), even though it does not look like the mathematics we normally think of. 

In 1962, in a paper titled ‘College Admissions and the Stability of Marriage’, Gale and Shapley proved that it is always possible to find a matching in which all pairs are stable, and presented an iterative algorithm to form such a stable matching. Together with Alvin Roth, Shapley won the 2012 Nobel Memorial Prize in Economic Sciences for the theory of stable allocations and the practice of market design in the area of mathematical economics.

Always possible to find a matching in which all pairs are stable

In the “marriage” context, the algorithm works as follows:

• Each man proposes to his first preference  – the woman accepts if she is single or if she prefers the man proposing to her current partner.

• At each subsequent iteration, every unmatched man proposes again to the next woman on their preference list – the women can accept the proposal if they are unmatched or prefer the new proposal, otherwise they can reject the proposal.  This continues until each man is matched to a woman.

The algorithm is guaranteed to produce a stable marriage in O(n^2) time, where n is the number of men and women. The matching is generally not unique.  In fact, if the men choose first, it yields the matching that favours the men’s preferences, while if the women choose first, the algorithm will favour the women’s ranking order.

The image shows an example with sets of size three for simplicity.  Both the men’s and women’s rankings are given, and the iterations are shown for men choosing first. If women choose first, one can check that the stable matching obtained will be the same in this case.  This implies that it is in fact a unique matching.

Josef Lauri is a professor of mathematics at the University of Malta. Christina Zarb is a mathematics lecturer at the University of Malta Junior College.

Sound Bites

•        Several variations and applications of the Stable Marriage Problem exist.  One variation, mentioned in the original paper by Gale and Shapley, is the room-mates problem which describes a matching problem where a set of people have to pick someone to be their room-mate, and therefore the gender of the people involved is of no concern, meaning that we have only one set.   Each person ranks all the other members of the set, in order of preference.  In contrast to the two-sets version, a stable matching is not always guaranteed.

•        An important application of SMP involves Content Delivery Networks (CDNs).  CDNs form a layer of networks within the internet that deliver content distributed over a very large number of servers to billions of users. A user prefers servers which are geographically closer, for faster delivery. A server prefers users which it can serve with lower cost. Every few seconds, the CDNs solve a variant of the Stable Marriage Problem to match users with servers.

For more science news, listen to Radio Mocha on www.fb.com/RadioMochaMalta/.

DID YOU KNOW?

•        There is no Nobel Memorial Prize for Mathematics, surprisingly.

•        The Fields Medal, first awarded in 1936, is regarded as one of most important awards a mathematician can receive, and is often described as the ‘Nobel Prize of Mathematics’. It is awarded every four years and awardees must be under the age of 40.

•        The first woman to win the Fields’ medal was Maryam Mirzakhani in 2014, 78 years after the prize’s institution.  In 2022, Maryna Viazovska became the second female Fields medallist.

•        Another important prize in the field of mathematics is the Abel Prize, instituted in 2003, also enjoying the prestige of being considered equivalent to a ‘Nobel Prize of Mathematics’.  It is awarded yearly and, to date, one woman, Karen Uhlenbeck, received the award in 2019.

For more trivia, see www.um.edu.mt/think.