Match Algorithm

1962 two American economists David Gale & Lloyd Shipley designed The “Stable Marriage Problem” aka “The Match“.

Note: ‘Stable’ means nobody would be unhappy or breakup after the match.

Applications:
1. Matching couples
2. Matching hospitals & doctor graduates
3. Match schools to students
4. Match HDB house to families
5. …

Scenario: An island with 4 men (m1, m2, m3, m4) and 4 women (w1, w2, w3, w4). You are to match 4 couples of opposite sex.

Each man would propose to a woman. However both men and women could list down their preferences with ranking, the higher ranked person would be given the choice.

Suppose the women preferences are (Table 1):

Choices	1st	2nd	3rd	4th
w1	m1	m2	m3	m4
w2	m2	m4	m1	m3
w3	m3	m4	m1	m2
w4	m4	m3	m2	m1

Suppose the men preferences are (Table 2):

Choices