I think they're referring to the "stable marriage problem" where every person is gonna get married come hell or high water, no takebacks. That problem cannot be solved in general if individuals can give a hard no.

Are you sure? What if you inventing a "phantom partner" for each person, who represents "not getting married". The preferences for that phantom partner would be

1. The person they are phantoming

2-N+1. All other phantom partners

N+1-2N+1. All other people.

If the person prefers not being married over all other available partners, then that will necessarily be a stable marriage. If they don't then the phantom partner will be able to find a match among the other unmatched phantom partners.

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".

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.

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.

Fair enough :)