Discussion 1
1. Prove that every execution of the G-S algorithm (when men are proposing) results in the same stable matching regardless of the order in which men propose.
Solution is the textbook. This is done by showing that regardless of the order of men proposing, men always end up with their best valid partners.
2. Prove that when we run the G-S algorithm with men proposing, women end up with their worst valid partners.
This solution is also provided in the textbook.
3. True or False:
In every stable matching that Gale–Shapley algorithm may end up with when men propose, there is a man who is matched to his highest-ranked woman.
This is false. Here is a counterexample:
m1 m2 —— ——
w1 w1
w2 w2
w3 w3
m3 w1 w2 w3 —— —— —— —— w2 m3 m2 m1 w1 m2 m1 m2 w3 m1 m3 m3
Given the above preference lists, when men propose we end up with the following pairs: (m1,w3), (m2,w2), and (m3,w1) where none of the men end up with their highest-ranked woman.
5. In a connected bipartite graph, is the bipartition unique? Justify your answer.
This is True. We can prove this by contradiction. Let’s say we have already found the bipartition X,Y where all edges in the graph go between X and Y. Now let’s assume that we have another bipartition X’, Y’ different from X, Y. If X’, Y’ is different from X, Y, then there must be at least one node i that used to be in X and now is not in X’ but has moved into Y’. We can run a BFS starting from node i. Say i is at level 1 in the BFS tree. All nodes at level 2 that must have belonged to Y should now be in X’, and all nodes at level 3 which must have belonged to X should now be in Y’, and so on. In other words, all node that used be in X are now in Y’ and all nodes that were in Y are now in X’. So X’, Y’ is not different from X, Y.