3 ms·

If the participants are free to say "I refuse to date anyone of (or not of) race X under any circumstances" then there's no solution in the general case.

EGreg 6y ago
No solution to what
- klyrs 6y ago
  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.
  - likelybear 6y ago
    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".
    - klyrs 6y ago
      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.
      - likelybear 6y ago
        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.
        klyrs 6y ago
        Fair enough :)
  - jeremysalwen 6y ago
    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.

EGreg 6y ago

No solution to what

klyrs 6y ago
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.
- likelybear 6y ago
  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".
  - klyrs 6y ago
    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.
    - likelybear 6y ago
      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.
      - klyrs 6y ago
        Fair enough :)
- jeremysalwen 6y ago
  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.