0
$\begingroup$

Problem Problem

In the above proof, I couldn't understand the reason given for why every boy can't rate some girl $A$ worst. First they are talking about some girl $A$ and later in the reason they are talking about each of the $n$ girls being rated worst by at least $n-1$ boys.

Can someone explain me this proof.

$\endgroup$
  • $\begingroup$ It seems this implicitly assumes there are no "ties": otherwise, if every boy prefers every girl equally, and vice versa, then any pairing would be stable. $\endgroup$ – Daniel Schepler Feb 13 '18 at 20:31
0
$\begingroup$

There are only $n$ boys, so there are $n$ total "worst" labels to distribute among the $n$ girls. That's simply not enough to give each of the $n$ girls $n-1$ or more "worst" labels. Therefore there must be at least one girl who gets fewer than $n-1$ "worst" labels.

They're not saying that it's impossible that every boy dislikes the same girl. They're saying that there must be at least one girl who doesn't get too many dislikes.

$\endgroup$
  • $\begingroup$ This answer is correct, but to address your specific question: The proof does not say “every boy can't rate some girl $A$ worst.” In fact, there can be a girl whom every boy rates worst. That girl will have $n$ “worst” labels. But then every other girl will have zero “worst” labels, and one of those other girls can be the one we’ll call $A$. $\endgroup$ – Steve Kass Feb 13 '18 at 20:18

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.