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.

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

View original post 363 more words

Advertisements

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:

WordPress.com Logo

You are commenting using your WordPress.com 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