Arrival and a Problem

Due to my flight being late (about 70 minutes in the end) I arrived at Changi airport at 1900ish. The flight was somewhat painful because I was coughing and sneezing and to top it off, some diarrhoea as well. I apologised for my coughing to the girl sitting next to me, who pointed to her throat and whispered “I’ve lost my voice.” We had both just finished exams and got sick almost straight after, and agreed all the stress and instant food had taken its toll. She was a Singaporean international student studying to be a veterinarian in Melbourne.

After collecting my pack, I made my way to the MRT (Mass Rapid Transport), the Singaporean train system, and bought an EZ-Link card (a functioning equivalent to a myki card). While waiting for the train, a girl with heavy looking luggage sat next to me and asked where I was going. I explained I was heading to a hostel on Lavender Street, and she said that was the station after hers.

changi

She asked if I was on holiday, so I told her I was here to do a two week long subject through my home university, and would move to the National University of Singapore campus upon its commencement in three days time. I explained I was studying nanotechnology, focusing on physics and biochemistry. She told me she was from China and was a PhD student in mathematics at NTU, another university here. While we were in transit I asked her to explain her research to me.

The stable marriage problem.

We want to find a stable matching between elements of two equally sized sets. i.e a one-to-one mapping from one set to the other set. So given two sets S and T of n elements, each element orders the elements of the other set preferentially from 1 to n. So an element s_i will rank the elements of T, \left \{t_1,t_2,..,t_n \right \} and an element t_j will rank the elements of S, \left \{s_1,s_2,..,s_n \right \}.

An element from each of the two sets gives a pairing (s_i,t_j). Given a second pair (s_k,t_l), where s_i prefers t_l above t_j and t_l prefers s_i above s_i does not exist, then the match is stable.

This can be put in a less formal way by considering a matchmaker with two equally sized groups of men and women to be paired off (yes, this is highly heteronormative). Each man ranks each woman according to preference and vice versa. No man and woman must prefer each other to their current partners for matches to be stable. Intuitively, this makes sense, it may result in infidelity and therefore be unstable.

This problem may seem overly simplistic and unrealistic (at least in our society), but it is used in real-world situations such as placing graduating medical students in hospitals. The solution in use has a number of rounds in which the members of one group act as proposers (hospitals) and the individuals in the other group act as acceptors. The proposers have an advantage as they start at their first preference and work their way through their list, whereas the acceptors have to wait for a proposal. It’s possible that current work being done on this problem is to find a more equitable solution.

Advertisements