Computers and Technology, 21.06.2019 22:50
This question refers to the stable marriage problem studied in class. assume that the preferences lists of all n males and n females are given. (a) does there exist a stable matching for every possible valid set of preference lists? prove or give a counterexample. you may refer to any material studied in class. (b) show that, if for every male, his optimal female and his possible female are the same person, then there is only one stable matching. (c) use part (b) to suggest an o(n^2)-time algorithm that determines if, given the preference lists of all the men and women, there exists more than one stable matching.