I am trying to solve a stable marriage problem where I have e.g. 20 women and 20 men, but they always only prioritise 4 pre-selected people of the opposite sex.

  1. My algorithm distributes all men and women, so that everybody has 4 potential partners. This happens through the whole group of 20 (not in groups of 4 x 4, which would easily work). If man A has woman B in his list then he is also in her list.
  2. The people prioritise their potential partners from 1 to 4.
  3. My algorithm tries to find the optimal partner depending on their priorization.

This means that they marriage has to be with one of the 4 potential partners. The order of their prioritisation decides on the order the proposing and accepting matrix is gone through, similar to this animation shown in wikpedia.

So basically I have 20 rows of each proposers and acceptors, but only 4 columns.

So far I always get an almost stable solution, in which in the end only one man and one woman can not marry.

How could I solve this problem for even bigger numbers of people (rows), but always keeping 4 (or between 3 and 5) prioritisation (columns)?


closed as unclear what you're asking by David Richerby, Nicholas Mancuso, Luke Mathieson, A.Schulz, Rick Decker Nov 30 '14 at 0:05

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ What do you mean by prioritize? Do people say "I will only marry A, B, C and D, in that order of preference, and I will refuse to marry anyone else" or "I want to marry A, B, C or D in that order of preference; if I can't marry them, I don't care who I marry"? And what problem exactly are you trying to solve? Finding a maximum cardinality stable matching where each person is either unmarried or married to one of their prioritized people? $\endgroup$ – David Richerby Nov 26 '14 at 19:06

In general, you won't be able to marry all but one of the men and all but one of the women. For example, suppose that all of the men want to marry the same four women: you'll get exactly four marriages and an arbitrarily large number of bachelors and spinsters.

  • $\begingroup$ I forgot to mention that the 4 people they can prioritise are not chosen, but distributed beforehand by my algorithm. $\endgroup$ – Luis Nov 27 '14 at 10:01
  • 1
    $\begingroup$ The situation I describe could still occur randomly, albeit with low probability. So you can't always get everybody but one pair married. $\endgroup$ – David Richerby Nov 27 '14 at 10:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.