# The 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 houses to families
5. Match Xmas gifts exchange with party participants (each participant puts their gift in a pool for exchange)

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 1st 2nd 3rd 4th m2 w1 w4 w3 w2 m3 w1 w2 w3 w4 m1 w2 w4 w3 w1 m4 w3 w1 w2 w4

Notation:
“->” propose
“♡” prefer

On Day 1
All men pick their 1st choice woman…

Both (m2 & m3) love the same woman w1,
{m2, m3} -> w1 ♡ {m1, m2, m3, m4}
so w1 chooses m2 tentatively (can be changed if better choice in next days)

m1 -> w2 ♡ {m2, m4, m1, m3}
so w2 chooses m1 tentatively.

m4 -> w3♡ {m3, m4, m1, m2}
so w3 chooses m4 tentatively.

Tentative Choice on Day 1:

 m1 w2 m2 w1 m3 ? m4 w3

On Day 2
Rejected in Day 1, now try 2nd choice…

m3 -> w2 ♡ {m2, m4, m1, m3} (w2 prefers m1 over m3)
So w2 committed to m1 (as in Day 1).

On Day 3
Again, try 3rd choice…
m3 -> w3 ♡ {m3, m4, m1, m2}
So w3 ditches m4 (Day 1 choice) and chooses m3.

Tentative Choice on Day 3:

 m1 w2 m2 w1 m3 w3 m4 ?

On Day 4
Now m4 rejected, has to choose another (2nd choice) woman…
m4 -> w1 ♡ {m1, m2, m3, m4}
So w1 stays with m2 (as in Day 1 choice).

On Day 5
Poor m4 rejected by w3 & w1…now try his 3rd choice w2,
m4 -> w2 ♡{m2, m4, m1, m3}
So w2 ditches m1 (Day 1 choice) in favor of m4.

Tentative Choice on Day 5:

 m1 ? m2 w1 m3 w3 m4 w2

On Day 6
m1 was rejected in Day 5, now try his luck on his 2nd choice w4…

m1 -> w4 ♡ {m4, m3, m2, m1}
Since w4 has no other proposal, no choice but to accept m1.

Final Choice on Day 6:

 m1 w4 m2 w1 m3 w3 m4 w2

Notes:
1. If we let the women propose to men, then by Day 1 would have terminated the Match as in:

2. The complexity occurs for men proposing to women, as shown in Table 2, both {m2, m3} choose w1. There is a fight !

3. While it may be possible for some women to get her man of first choice (here only w3 gets 1st choice m3), what if there are 100 or 1000 men and women? No guarantee to get the 1st choice.

Reference:

[Available @ AMK National Library #518.1]