Skip to main content
3 of 3
deleted 1 character in body
sashang
  • 103
  • 3

Stable matching with constraints

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.

sashang
  • 103
  • 3