Want to discuss problems from problem set #2? Use the comments section below. Your classmates, the TA and I will be following, and will try to help it be a useful place to exchange ideas.
I had an email conversation with the professor and I am posing it here. My question was:
For the part 1.5a. I am not sure how to re-arrange the part of the list with ties, so I could use GS algorithm as a "black box". Is it possible. I was thinking that I could rearrange it in the order of preference of the other party, i.e. for man, rearrange the tie part of a man in the preference of woman to this man. For example, if a man is indifferent to women a and b and b rates m first and a rates m second, then rearrange the tie as [b, a]. The same is for women. I was trying to think through the possibility of the re-writing the GS algorithm. However, here I have problems as well. How to treat the tie members? For example, if a man is indifferent to women a and b, then does he propose to already paired woman. The #1.5a has so many possibilities to make it, that I cannot chose one and I cannot decide which one would be the best.
Short answer: perhaps it doesn't matter. Anyway, the thing to do is try it out on some examples, and see what happens. You can't always expect to reason out the answer before just "trying something" on a lot of examples first.
The post above by "Unknown" is what I had quickly emailed back to Lucia.
@broompilot: No, don't code the algorithm. Test it out with pen and paper for as many examples as you can. Start small. Often if there is a mistake in your idea, it will be revealed by testing even simple examples.
Here's a question to get you all thinking about the right issues. Post your answers here. Do ties really matter? If man A ranks woman 1 first, then 2 and 3 tied, then 4 last, is there any reason not to just replace this with the strict ordering 1, 2, 3, 4? Isn't man A just saying he doesn't care if you fill out his dating slip as 1234 or 1324? Please discuss (excluding the TA).
I had a question pertaining to the terminology of 1.5 and had trouble posting until now for some odd reason:
They use "perfect matching" which means that it is a 1-to-1 mapping and does not use the preference lists but, then they talk about instabilites (weak and strong) which imply stable matchings.
I think I figured out what they are saying as follows:
There are n! possible perfect matchings with at least one (found by G-S) that is also a stable matching, so when they say there exists a perfect matching that has no strong stability then that is a stable matching???
Tom, for man it might not matter, but for a woman, it does. if she prefer 1, then 2 and 3, then 4. If 3 is proposed to her and she agreed, and then 2 proposed to her, it really matters if the order is 1234 or 1324. Is that right? Lucia
I was also wondering about the problems using "perfect" matching instead of a stable matching. If I'm interpreting the questions correctly it should be easier (or at least different) to show a "perfect" matching has none of these instabilities.
The "black box" idea is definitely the approach I'm going to try to take as much as possible, but I'm wondering for problems that say "give an algorithm" is it necessary to do a thorough proof of its correctness? (my guess is yes, but it'd be nice to have Prof. Hayes' verification)
And Krista, I would try to reconsider your n! idea and relate it to how Prof Hayes used his card example in class. (Does it matter what order the matchings are in for a perfect matching?)
I'm assuming that the best approach to using the "black box" is to run with what Prof Hayes is hinting at with the filled out lists. This should be able to give us a perfect matching using the G-S algorithm.
then with regards to the pref lists there is at least one stable matching (using G-S to find one) that is contained in the above n! possible matchings??
Could be over thinking it perhaps but that is how I am reading it :)
@Krista and @Lucas, there are n! perfect matchings--all the ways to pair up all n men with n women. This has nothing to do with the preference lists.
Question 5 asks you to think about how things are different from eHarmony town if we allow ties in the preference lists. The first way they are different is that it can be unclear what the right notion of an "instablility" is. Briefly, if man m prefers woman w' over his spouse w, and woman w' ranks her husband and m equally, does that count as an instability or not? Depending how we answer this, may lead to different answers about whether stable matchings are always possible.
Does this help? I feel from your comments, that you may still be having trouble understanding the problem statement.
In particular, there are 3 distinct concepts of stability here. - The original one, that only applies in the original setting with no ties. - "Strong stability", defined in part 5a. - "Weak stability", defined in part 5b. (the second 2 both apply in the new setting that allows ties in the preference lists)
@broompilot in comment #6 wrote: Tom, for man it might not matter, but for a woman, it does. if she prefer 1, then 2 and 3, then 4. If 3 is proposed to her and she agreed, and then 2 proposed to her, it really matters if the order is 1234 or 1324. Is that right?
Yes and no. The matching output by the Gale-Shapley algorithm may very well change in this case (although we need to know all the preference lists to say for sure). So in that sense, it matters how the ties are broken. On the other hand, does this woman care whether she ends up married to 2 or to 3? No, in the sense that she ranks them equally.
So, what I'm getting at is, will the way we break these ties affect whether the outcome is "stable" in the sense defined in 5a, and in the sense defined in 5b?
Work out some examples, for instance with n=2 and n=3, in complete detail, meaning: make up preference lists, figure out all the possible stable matchings (under both versions), and figure out whether there is a way to break the ties so that the G-S algorithm gives the right type of answer. I think that should give a lot of insight, especially if you try to make the preference lists interesting.
@Lucas in comment 7: Yes, it is necessary to give a thorough explanation of why an algorithm is correct. This is the case whether you are giving a new algorithm, or doing a reduction to the Gale-Shapley algorithm. (The kind of explanation is rather different in these 2 cases though.)
@broompilot in comment 12: Re-read the last sentence of the first paragraph in question 8. It clearly says that you don't need to answer the question for men.
Krista, sorry for leading you astray from the # of matchings, but also Prof Hayes is right in the regard that the number of matchings does not affect the preference lists (which are going to be the inputs for the G-S algorithm).
I've tried a few examples for 1.5a after completing 1.5b and 1.8 and what helped me understand the problem is looking at what happens if a woman is already engaged to a man, say m1 and m2 proposes to her. If these two (m1 and m2) are tied in her preference list, how does your solution handle it? And does it affect the stability of the final output?
You also need to consider the order in which the man will propose if he has two women that are tied in his preference list. These are the only two differences from the original eHarmony town problem, if I'm not mistaken.
I hope these considerations will help you.
And to answer Prof Hayes question above. No, ties do not really matter. You will get different stable matching outputs depending on how you order "ties" but you will always get a stable matching if you use G-S.
I can't think of a counter-example where it would be the case where there could be an output that would be a strong instability that is caused by the consolidation of these preferences, I'm just working on proving that it's never the case now.
I had an email conversation with the professor and I am posing it here. My question was:
ReplyDeleteFor the part 1.5a. I am not sure how to re-arrange the part of the list with ties, so I could use GS algorithm as a "black box". Is it possible. I was thinking that I could rearrange it in the order
of preference of the other party, i.e. for man, rearrange the tie part of a man in the preference of woman to this man. For example, if a man
is indifferent to women a and b and b rates m first and a rates m second, then rearrange the tie as [b, a]. The same is for women.
I was trying to think through the possibility of the re-writing the GS algorithm. However, here I have problems as well. How to treat the tie
members? For example, if a man is indifferent to women a and b, then does he propose to already paired woman. The #1.5a has so many possibilities to make it, that I cannot chose one and I cannot decide which one would be the best.
Short answer: perhaps it doesn't matter. Anyway, the thing to do is try it out on some examples, and see what happens. You can't always expect to reason out the answer before just "trying something" on a lot of examples first.
ReplyDeleteHow do you test it? Do you code the algorithm or just use pen and paper?
ReplyDeleteThe post above by "Unknown" is what I had quickly emailed back to Lucia.
ReplyDelete@broompilot: No, don't code the algorithm. Test it out with pen and paper for as many examples as you can. Start small. Often if there is a mistake in your idea, it will be revealed by testing even simple examples.
Here's a question to get you all thinking about the right issues. Post your answers here. Do ties really matter? If man A ranks woman 1 first, then 2 and 3 tied, then 4 last, is there any reason not to just replace this with the strict ordering 1, 2, 3, 4? Isn't man A just saying he doesn't care if you fill out his dating slip as 1234 or 1324? Please discuss (excluding the TA).
I had a question pertaining to the terminology of 1.5 and had trouble posting until now for some odd reason:
ReplyDeleteThey use "perfect matching" which means that it is a 1-to-1 mapping and does not use the preference lists but, then they talk about instabilites (weak and strong) which imply stable matchings.
I think I figured out what they are saying as follows:
There are n! possible perfect matchings with at least one (found by G-S) that is also a stable matching, so when they say there exists a perfect matching that has no strong stability then that is a stable matching???
I had to read over and over and over... again :)
Tom, for man it might not matter, but for a woman, it does. if she prefer 1, then 2 and 3, then 4. If 3 is proposed to her and she agreed, and then 2 proposed to her, it really matters if the order is 1234 or 1324. Is that right?
ReplyDeleteLucia
I was also wondering about the problems using "perfect" matching instead of a stable matching. If I'm interpreting the questions correctly it should be easier (or at least different) to show a "perfect" matching has none of these instabilities.
ReplyDeleteThe "black box" idea is definitely the approach I'm going to try to take as much as possible, but I'm wondering for problems that say "give an algorithm" is it necessary to do a thorough proof of its correctness? (my guess is yes, but it'd be nice to have Prof. Hayes' verification)
And Krista, I would try to reconsider your n! idea and relate it to how Prof Hayes used his card example in class. (Does it matter what order the matchings are in for a perfect matching?)
My last post wasn't very clear. The proof of correctness was in regards to an algorithm that we made, not the G-S algorithm. Sorry.
ReplyDeleteI'm assuming that the best approach to using the "black box" is to run with what Prof Hayes is hinting at with the filled out lists. This should be able to give us a perfect matching using the G-S algorithm.
ReplyDeleteI got it. Actually, running a couple tests like Prof. Hayes advised really helped.
ReplyDeleteLucas, here is an example of what I was thinking:
ReplyDeleten = 3 men and women
6 = n! possible perfect matchings =>
(m1,w1), (m2,w2), (m3,w3)
(m1,w1), (m2,w3), (m3,w2)
(m1,w2), (m2,w1), (m3,w3)
(m1,w2), (m2,w3), (m3,w1)
(m1,w3), (m2,w1), (m3,w2)
(m1,w3), (m2,w2), (m3,w1)
then with regards to the pref lists there is at least one stable matching (using G-S to find one) that is contained in the above n! possible matchings??
Could be over thinking it perhaps but that is how I am reading it :)
for the problem 8, we don't need to prove the same for men, do we?
ReplyDelete@Krista and @Lucas, there are n! perfect matchings--all the ways to pair up all n men with n women. This has nothing to do with the preference lists.
ReplyDeleteQuestion 5 asks you to think about how things are different from eHarmony town if we allow ties in the preference lists. The first way they are different is that it can be unclear what the right notion of an "instablility" is. Briefly, if man m prefers woman w' over his spouse w, and woman w' ranks her husband and m equally, does that count as an instability or not? Depending how we answer this, may lead to different answers about whether stable matchings are always possible.
Does this help? I feel from your comments, that you may still be having trouble understanding the problem statement.
In particular, there are 3 distinct concepts of stability here.
- The original one, that only applies in the original setting with no ties.
- "Strong stability", defined in part 5a.
- "Weak stability", defined in part 5b.
(the second 2 both apply in the new setting that allows ties in the preference lists)
@broompilot in comment #6 wrote:
ReplyDeleteTom, for man it might not matter, but for a woman, it does. if she prefer 1, then 2 and 3, then 4. If 3 is proposed to her and she agreed, and then 2 proposed to her, it really matters if the order is 1234 or 1324. Is that right?
Yes and no. The matching output by the Gale-Shapley algorithm may very well change in this case (although we need to know all the preference lists to say for sure). So in that sense, it matters how the ties are broken. On the other hand, does this woman care whether she ends up married to 2 or to 3? No, in the sense that she ranks them equally.
So, what I'm getting at is, will the way we break these ties affect whether the outcome is "stable" in the sense defined in 5a, and in the sense defined in 5b?
Work out some examples, for instance with n=2 and n=3, in complete detail, meaning: make up preference lists, figure out all the possible stable matchings (under both versions), and figure out whether there is a way to break the ties so that the G-S algorithm gives the right type of answer. I think that should give a lot of insight, especially if you try to make the preference lists interesting.
@Lucas in comment 7: Yes, it is necessary to give a thorough explanation of why an algorithm is correct. This is the case whether you are giving a new algorithm, or doing a reduction to the Gale-Shapley algorithm. (The kind of explanation is rather different in these 2 cases though.)
ReplyDelete@broompilot in comment 12: Re-read the last sentence of the first paragraph in question 8. It clearly says that you don't need to answer the question for men.
Krista, sorry for leading you astray from the # of matchings, but also Prof Hayes is right in the regard that the number of matchings does not affect the preference lists (which are going to be the inputs for the G-S algorithm).
ReplyDeleteI've tried a few examples for 1.5a after completing 1.5b and 1.8 and what helped me understand the problem is looking at what happens if a woman is already engaged to a man, say m1 and m2 proposes to her. If these two (m1 and m2) are tied in her preference list, how does your solution handle it? And does it affect the stability of the final output?
You also need to consider the order in which the man will propose if he has two women that are tied in his preference list. These are the only two differences from the original eHarmony town problem, if I'm not mistaken.
I hope these considerations will help you.
And to answer Prof Hayes question above. No, ties do not really matter. You will get different stable matching outputs depending on how you order "ties" but you will always get a stable matching if you use G-S.
I can't think of a counter-example where it would be the case where there could be an output that would be a strong instability that is caused by the consolidation of these preferences, I'm just working on proving that it's never the case now.