Skip to main content
Computer Science

Return to Question

deleted 1 character in body
Source Link
sashang
sashang
  • 103
  • 3

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 goodbad 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.

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 good 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.

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.

edited title
Link
Ariel
Ariel
  • 13.6k
  • 1
  • 21
  • 39

Alternative proof of Question 1.1 in Algorithm Design book Stable matching with constraints

Source Link
sashang
sashang
  • 103
  • 3

Alternative proof of Question 1.1 in Algorithm Design book

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 good 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.