1. Consider the following set P of men's and women's preferences. Men Preferences A S TU...

 

Transcribed Image Text:

1. Consider the following set P of men's and women's preferences. Men Preferences A S TU V B S VUT C S UT V D U V T S Preferences DAB Women S C T ADC B U C D B A V A CD B (a) Find the stable matching for set P, that would be produced by running the Gale- Shapley algorithm as presented in class, in which the men do the proposing. (b) Set P has k different stable matchings. What is k? If you cannot determine k exactly, give the best upper bound and the best lower bound that you can. Justify your statement. 1. Consider the following set P of men's and women's preferences. Men Preferences A S TU V B S VUT C S UT V D U V T S Preferences DAB Women S C T ADC B U C D B A V A CD B (a) Find the stable matching for set P, that would be produced by running the Gale- Shapley algorithm as presented in class, in which the men do the proposing. (b) Set P has k different stable matchings. What is k? If you cannot determine k exactly, give the best upper bound and the best lower bound that you can. Justify your statement.