Match Algorithm

Math Online Tom Circle

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 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):

Choices1st 2nd 3rd 4th
w1m1 m2m3m4
w2m2 m4m1m3
w3m3 m4m1m2
w4m4 m3m2m1

Suppose the men preferences are (Table 2):


View original post 363 more words


About tomcircle

Math amateur
This entry was posted in Uncategorized. Bookmark the permalink.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.