2

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.

Arkistarvh Kltzuonstev
  • 6,824
  • 7
  • 26
  • 56
ESDAIRIM
  • 611
  • 4
  • 12
  • Stack Overflow is not a free coding service. It is expected that *you* deliver the code and we help fixing it. – Klaus D. Mar 27 '19 at 12:11
  • I am not asking for the code per se, just an algorithm that handles this or a library recommendation that's all, and I will adapt it to my own situation, the tables and matrices are just an example to illustrate the problem. @k – ESDAIRIM Mar 27 '19 at 12:15
  • Sure, add the missing preferences to the end of each persons list in an arbitrary order, then apply the GS algorithm. Some people might get someone they did not add a preference for, but would anyone else want to switch? – Paddy3118 Mar 28 '19 at 21:02
  • Yeah makes sense, actually for my application, I think I will think about a preference measure that I can add programmatically something that makes sense in my case, and use the general GS algorithm thanks@Paddy3118 – ESDAIRIM Mar 28 '19 at 23:13
  • This can help https://github.com/kartikeyas00/RAProblem – Kartikeya Sharma Oct 29 '19 at 04:58

1 Answers1

1

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.

Taylor Nelms
  • 384
  • 2
  • 16
  • thanks @TaylorNelms so the idea is that there is no algorithm that guarantees a solution other than brute force? – ESDAIRIM Mar 27 '19 at 12:18
  • That's not necessarily true; it would depend on the exact parameters of your problem. For instance, if a man is matched with a woman for which he had no preference, is that a failure of the algorithm? I'd toy around with some various implementations on your own (for example, some modifications around the Gale-Shapely algorithm) and see what you can get to work. – Taylor Nelms Mar 27 '19 at 15:06
  • I will find some way to compute preferences and fill in the entire preference list programmatically. and use standard GS – ESDAIRIM Mar 28 '19 at 23:15