# Stable Marriage - set of preferences such that every arrangement is stable?

This is a homework problem from the MIT OCW math for CS class, assignment 4, problem 5.

Prove or disprove the following claim: for some n ≥ 3 (n boys and n girls, for a total of 2n people), there exists a set of boys’ and girls’ preferences such that every dating arrangement is stable.

As I understand it, this is asking for a set of preferences such that any combination of matchings is stable.

Informally, my thought was to show by contradiction this is not possible. I assume the theorem is true, then there must be some combination such that every male is paired with his least favorite partner. In this case, assuming the theory holds, then every female must prefer their partner the most. Otherwise, if any female prefered any other male more, they would form a rogue couple. This then would be true starting with the female set, that is there exists a combination such that each female is paired with her least favorite, so each male must like his partner the most.

Given this, and that we are looking at every combination, there must exist a combination of two couples such that a male is with his least favorite and a female is with her least favorite (who are different people because of the idea above). This would create a non-stable matching, so there is a contradiction.

I feel this is wrong somehow, and that I am missing something obvious. Would someone point me in the right direction?

I am sorry if this is way off base or too informal, I do not have a background in math, and trying to teach myself has been fun but slow going without anyone to consult.

• After reading my idea again, I suppose I can't assume that each least favorite partner is different. Any thoughts? I think I went down the completely wrong path at the start here. – Jeremy Jul 11 '14 at 15:14
• en.wikipedia.org/wiki/Stable_marriage_problem#Solution Does this solve your problem? Or am I misunderstanding the question? – John Machacek Jul 11 '14 at 15:23
• That algorithm finds a single possible stable solution, the problem (I think) is looking for **a proof that there exists** a list of preferences such that every combination of pairings is stable. Henning's answer might make the question clearer. **edited – Jeremy Jul 11 '14 at 15:28
• Ok I see very well carry on :) – John Machacek Jul 11 '14 at 16:23

The only thing you need, then, is to be sure that there is such a couple for any set of preferences where $n\ge 3$. A simple counting argument will succeed in that ...
• Alternatively, pick 3 random boys and 3 random girls, and given their preferences about each other find an unstable matching among those 6 persons. Then extend it randomly to a matching of everyone -- this cannot make it stop being unstable. (But I'm not sure it's actually easier to prove the $n=3$ case than to give a direct general proof for $n\ge 3$). – Henning Makholm Jul 11 '14 at 15:32