Question

Consider a group of n ? 2 males and n ? 2 females with preferences assigned as in the stable marriage problem. Prove or disprove that there always exists a set of marriages (all parties married) that is not stable.

Answer 1

Solution:

at n= 2.

let's say for man A(1, 2), and for B as well it is (1, 2)

and if the women preference is (A, B), and (A, B)

there is a certainty of one unstable matching which is (B, 2), and (A, 1)

similarly, for every n>2 there will be a matching like this which will certainly exist

which proves that at n>= there will still atleast one unstable matching which makes it unstable.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)