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.
- 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.
- The people prioritise their potential partners from 1 to 4.
- 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)?