Stable marriage problem - PrismoSkills

Stable marriage problem - PrismoSkills

Stable marriage problem Puzzle: Given n men and n women and a preference order of marriage from each one of them, how to marry these 2n bachelors such that their marriages are stable. A marriage is stable when both partners in a couple cannot find anyone else (higher in their priority list) available for marriage. In other words, a marriage is stable when every person gets its most desired partner subject to availability. Example: Given men m1 and m2 and women w1 and w2. Preference order of m1 is w1,w2 and that of m2 is also w1,w2. Preference order of w1 is m1,m2 and that of w2 is also m1,m2. Possible marriages among the above are: m1,w1 and m2,w2 m1,w2 and m2,w1 The second system of marriages is less stable than the first one because there exists a combination where both m1 and w1 can find a better spouse as per their choice. While there is no such possibility in the first case, hence its more stable. Solution: An algorithm to do this as follows:

Read full article from Stable marriage problem - PrismoSkills