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.

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

“->” 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

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.


[Available @ AMK National Library #518.1]

See also: Stable Marriage Problem


One thought on “The Match Algorithm

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s