What is a stable matching?

Question

So my question refers to what precisely is a "Stable Matching"? I am aware of the Stable Marriage Problem, and all solutions seem to indicate that you finish with a "Stable Matching". But I am unsure as to what this actually means.

Answer 1

I would stare at the .gif from the wiki because it is actually a great explanation of the mechanics.

In stable matching we guarantee that all elements from two sets (men & woman, kids & toys, persons & vacation destinations, whatever) are put in a pair with an element from the other set AND that pair is the "best available match"

The way we determine what is the "best available match" is imagine that each element of a set has ranked their preference for the elements of the opposite set. The goal is to satisfy the preferences of everybody. Sticking with the marriage problem, imagine every man has a ranked list of woman and every woman has a ranked list of men. The goal is to match them together making sure everybody gets the highest person on their list possible.

Keep in mind this takes several steps (or rounds) for this to work itself out. In the marriage example another thing to keep in mind is that each side can only do one thing. So in our example women accept, men propose. Also, the proposal is not binding. Meaning that if in round one, a woman gets a proposal from her #2 most desired man and in the next round she gets a proposal from her #1 man, she can reject #2 and take #1. The wiki said it better than I could so...

Upon completion of the algorithm, it is not possible for both Alice and Bob to prefer each other over their current partners. If Bob prefers Alice to his current partner, he must have proposed to Alice before he proposed to his current partner. If Alice accepted his proposal, yet is not married to him at the end, she must have dumped him for someone she likes more, and therefore doesn't like Bob more than her current partner. If Alice rejected his proposal, she was already with someone she liked more than Bob.

Basically, no one gets shafted in the marriage because the pair was the highest preference for one another given limited options.