2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jeremy Jul 11 '14 at 15:14
  • $\begingroup$ en.wikipedia.org/wiki/Stable_marriage_problem#Solution Does this solve your problem? Or am I misunderstanding the question? $\endgroup$ – John Machacek Jul 11 '14 at 15:23
  • $\begingroup$ 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 $\endgroup$ – Jeremy Jul 11 '14 at 15:28
  • $\begingroup$ Ok I see very well carry on :) $\endgroup$ – John Machacek Jul 11 '14 at 16:23
2
$\begingroup$

It looks like you're looking for more than you need here. You can go about it directly: given any set of preferences there exists a matching that is not stable.

What you need is only to find one combination of boy and girl such that the boy is not the girl's least favorite partner, and the girl is not the boy's least favorite partner. Then, in order to create a non-stable matching, just pair each of those two up with their least favorite partner, and then match up everyone else randomly.

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 ...

$\endgroup$
  • $\begingroup$ The class hasn't covered counting yet, could I prove by induction using n = 3 as the base case? $\endgroup$ – Jeremy Jul 11 '14 at 15:28
  • $\begingroup$ @Jeremy: Counting is usually taught in elementary school... No induction is needed, just consider how many potential pairs of boys and girls there are, and how many of those can be excluded because the boy is the girl's worst nightmare or vice versa. Note that everyone has only one worst nightmare. $\endgroup$ – Henning Makholm Jul 11 '14 at 15:30
  • $\begingroup$ 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$). $\endgroup$ – Henning Makholm Jul 11 '14 at 15:32
  • $\begingroup$ There is an entire section of the class called "counting" (sums, recurrences, cardinality, etc), I was assuming that was what you were referring to. Nonetheless I appreciate the quick feedback. That was sort of my thought after your answer. Given any three couples I could show a unstable arrangement exists, and adding more couples will not make that stable. Thanks! $\endgroup$ – Jeremy Jul 11 '14 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.