0
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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.