1
$\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.

Improve this question
$\endgroup$
4
  • $\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 ♦
    Commented Mar 27, 2019 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. ♦
    Commented Mar 27, 2019 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$
    – ESDAIRIM
    Commented Mar 28, 2019 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. ♦
    Commented Apr 26, 2019 at 16:24

1 Answer 1

Reset to default
1
$\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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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