Re:The stable marriage problem and modern dating
by likelybear on Wednesday July 08, 2020 @04:04PM
(#23773681)
Hard no's are fine in the classic stable marriage problem. "Remain single" gets added as an option to each person's preference list, then you can run Gale-Shapley deferred acceptance more-or-less as normal with each person on the accepting side starting with "remain single".
[ Parent
| on HN ]
Re:The stable marriage problem and modern dating
by klyrs on Wednesday July 08, 2020 @04:35PM
(#23773944)
The original formulation of the problem is looking for a bijection / perfect matching. That isn't always possible if "remain single" is an option. I agree with you and your sibling that modifying the problem is possible, but it won't always produce a perfect matching which is what I meant by unsolvable.
Re:The stable marriage problem and modern dating
by likelybear on Wednesday July 08, 2020 @05:02PM
(#23774191)
Given this appears in Gale and Shapley 1962, I'd say it is part of the original formulation (though they do it by saying people are simply not allowed to apply to colleges where they'd be a hard no rather than apply and be rejected). They're looking at stable matchings for college admissions, not perfect matchings.