How to approach Stable Marriage Problem with restricted pairs

Question

Let's say we have a version of the stable marriage problem with the addition that some pairs are restricted based on certain preferences, e.g. whether or not someone lives in a different city and whether or not that person is okay with long-distance (assume people cannot move). Assuming men proposing, Gale–Shapley produces a men-optimal/women-pessimal solution. Given this, what would be the best way to represent preference lists for each party? One idea I had was that if someone is incompatible, they would be left off the preference list altogether. I suppose that means if a woman received a proposal from a man not on her list, she wouldn't be able to be engaged to him, even if he's fine with being in different cities. However, I'm not sure if this would be allowed by the algorithm (at the end of the day, I'd still like all men to be matched, but this could interfere with the algorithm's guarantee of a stable matching). Obviously if everyone lived in different locations and were unwilling, this would be impossible, but given that a lot of people live in the same few locations in my situation, I'm uncertain as to how likely this would be.

So, instead of having variable-length preference lists, I also thought I could keep constant rankings (all lists have size n), but the top half of the list has location-compatible partners (i.e., either I'm in the same location or I don't mind long-distance, regardless of what the other person wants) and the bottom half of the list has location-incompatible partners (i.e., we are in different locations and I don't want long-distance). Given that men are proposing, this means we can presume they most likely receive a location-compatible matching, but if for example there are a few more women who are picky about location, and they receive their worst valid choice, does this increase the likelihood women will be matched with a location-incompatible partner? If that's the only option then I suppose I have to accept it, but I'm wondering if there's a way to modify the algorithm such that women avoid location-incompatibility as much as possible despite Gale–Shapley being women-pessimal.

Answer 1

Give incompatibility a preference penalty on both sides. So if you match my desires but I'm incompatible with you, give me a preference penalty so I'll look for people compatible with me first.

As you guessed, this will not guarantee no incompatible matchings. But it will make a good faith effort to avoid them.