I'm reading through Algorithm Design by Kleinberg and Tardos and was working on Ch1 Q1. The question is about stable matching and their 'proof' is presented by contradiction. I have an alternative argument and want to know if its right. The question paraphrased is:

Consider a town with n men and n women. Each man as a preference list that ranks the women and each women has a similar preference list. Of these men and women, k men are bad and k women are bad. So there are n-k good women and n-k good men. Each man prefers to match with a good women and vice versa. Therefore all preference lists rank the good people higher than bad people. Show that in every stable matching every good man is married to a good women.

My 'proof':

Assume that there is a pairing where a good man is matched with a bad women. Because there are the same number of good men and women, it means that there is one good woman, currently paired with a bad man, who rejected this good man. If she rejected this good man it means that he must be of lower preference than the bad man she is paired with. But this is a contradiction because a good man cannot be ranked lower than a bad man. It means that the good man is actually bad and there are more bad men than good women and the initial problem statement is false.

  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Jul 11 '16 at 6:11

I assume you want to start your proof with "suppose there is a pairing where a good man $m_1$ is matched with a bad woman $w_1$".

This indeed means that there exists a good woman $w_2$ matched with a bad man $m_2$ (by the pigeonhole principle). However, the contradiction here does not follow from the fact that $w_2$ prefers $m_1$ but is actually matched to $m_2$ (it is possible for a woman to not be matched with her top ranked man).

The contradiction follows from the fact that a matching which contains $(m_1,w_1),(m_2,w_2)$ is not stable, since $m_1$ prefers $w_2$ and $w_2$ prefers $m_1$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.