0
$\begingroup$

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.

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.

$\endgroup$
  • $\begingroup$ One problem here is that there may be no assignment that leaves no men or women unassigned. In that case, what do you want the algorithm to do? $\endgroup$ – Discrete lizard Mar 27 at 13:35
  • $\begingroup$ First you need to define what criteria you want the assignment to satisfy. The standard algorithm ensures stability, but the definition of stability assumes all participants are ranked. When not all participants are ranked, you'll need to define some equivalent of stability. We can't do that for you -- it requires you to determine what you want from a solution. $\endgroup$ – D.W. Mar 27 at 18:35
  • $\begingroup$ The idea is to give back a configuration that respects the partial preferences, that is all. so if the config respects the choices present in the men and women's lists the problem is solved $\endgroup$ – ESDARII Mar 28 at 8:54
  • $\begingroup$ You haven't defined what it means to "respect the partial preferences", so I'm not entirely sure what that means. $\endgroup$ – D.W. Apr 26 at 16:24
0
$\begingroup$

I am not completely familiar with the problem, but maybe these couple of papers (or references therein) dealing with stable marriage with partial preferences (of which your setting could perceived as a special case) may be helpful:

https://www.math.unipd.it/~frossi/stc-care5-cr.pdf

https://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6840/6488

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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