I have a slightly different formulation of the stable marriage problem. Basically, I can match one man to one woman, but the preference list is incomplete, which means that a man has expressed interest only in a subset of women and vice versa. I don't think the original Gale Shapley algorithm would work for this, if so what modifications do I need to make? If Gale Shapely does not work here, is there any algorithm to solve this? code suggestions, especially in python for this kind of problem, are very welcomed.
in more concrete terms, this is the problem:
Men = [1, 2, 3, 4, 5]
Women = [a, b, c, d, e]
preferences:
men:
1: a, c, d
2: d, a, b
3: a, e, b
4: c, a, d
5: e, d, a
women:
a: 1, 3, 4
b: 4, 2, 5
c: 5, 1, 4
d: 3, 2, 1
e: 5, 3, 1
I need to match each man to one and only one woman and the number of preferences allowed is fixed and less than the number of candidates.
You would need to define an entire preference list somehow, otherwise the algorithm wouldn't work. That said, it should be relatively simple to "fill out" a preference list with the remaining men/women arbitrarily; you could assign a static ordering, or assign those preferences randomly.
If you need to match one man to one woman on his preference list exclusively, you would inevitably run into situations where the problem cannot be solved.
As for python approaches, there are a number of ways to go about this; it would mostly depend on how you're attempting to approach your implementation of the algorithm.