2

I've been trying to learn about the Stable Marriage Problem and was wondering what happens if someone doesn't fill in their preference list - at all.

I've read up about the problem with regards to incomplete lists and ties etc. but can't seem to see a specific mention of an empty list. My initial thoughts would be along the lines of this being treated as everyone ranked as a tie but I'm not sure that would be the best way to see things. How would this be handled?

Apologies if this has been asked/answered elsewhere. I also apologise if there is a very obvious answer to this, my brain is currently fried in any case. Thanks in advance for any help.

Jamie
  • 25
  • 8
  • 1
    I think treating everyone not in someone's preference list as tied is fine. The order you loop through them doesn't matter as they will be fine with whoever they end up with – afghanimah Apr 28 '20 at 22:41

2 Answers2

2

An empty list is just the extreme case of an incomplete list: the person has indicated that no matches are acceptable to him/her, so it is guaranteed that (s)he will end up unmatched.

By the way, a small terminological note: the term "stable marriage [problem]", when unmodified, ordinarily denotes the original version of the problem, where there are equal numbers of men and women and each person provides a complete ordered list of all members of the opposite sex. So there are no "incomplete lists and ties etc.", and hence no empty lists. Extensions of the stable marriage problem may introduce support for incomplete lists and/or ties and/or different numbers of men and women, in which case they get names like "stable marriage [problem] with incomplete lists" and so on. We could even imagine different extensions that all have "incomplete lists" but assign different meanings to them, though in practice I think all extensions with "incomplete lists" assign them the same meaning.

ruakh
  • 175,680
  • 26
  • 273
  • 307
1

I believe that if someone does not fill in their preference list, then this would mean that this person does not mind who they are are matched with. Indeed the algorithm would be a bit stuck on this special case, but the logical solution would be to - in the very end of the algorithm - match them with whoever is not matched with anyone yet (if we assume this person is the only person who hasn't filled in their preference list at all).

This is purely speculation, but in my opinion it would be the logical approach to this situation.

lumapools
  • 64
  • 6