4. Stable marriage problem

• There is a group of women and a group of the same number of men. Each person has expressed his/her ranking for the members in the opposite group. The problem is to find a matching between the two groups such that the marriages are stable. A marriage between a man m and a woman w is said to be stable provided that:

  • whenever m prefers another woman o to w, o prefers her spouse to m.
  • whenever w prefers another man o to m, o prefers her spouse to w.

• The following are the rankings:

• Men Women

1. Richard [5,1,2,4,3]

2. Jame [4,1,3,2,5]

3. John [5,3,2,4,1]

4. Hugh [1,5,4,3,2]

5. Greg [4,3,2,1,5]

1.Helen [1,2,4,3,5]

2.Tracy [3,5,1,2,4]

3. Linda [5,4,2,1,3]

4. Sally [1,3,5,4,2]

5.Wanda [4,2,3,5,1]

Previous slide

Back to first slide

View graphic version