I think it can be a bit easier to think of the algorithm in terms of job applicants (who receive job offers) and employers (who
propose job offers). And then due to the algorithm, it must be the case that the number of applicants is equal to the number of employers, and each employer is only trying to fill one position.
An applicant (the receiver) will end up with a "worst" match in the sense that if you look at all "stable" pairings (there can be multiple configurations), the applicant is going to have the least favorable one among the different pairings.
There's an important concept of a "blocking pair", and the Gale-Shapley algorithm is trying to eliminate all blocking pairs, and you could say that pairings are stable when no blocking pairs exist. A blocking pair is a job applicant and employer who aren't matched together, but both prefer each other over their current match.
Suppose that after the algorithm is done with its work, Alice doesn't end up with a job offer from her top choice, Google. This must mean that Google never offered her a job because Alice was just too far down on their list, and Google made a deal with someone else they like better than Alice.
An applicant (the receiver) will end up with a "worst" match in the sense that if you look at all "stable" pairings (there can be multiple configurations), the applicant is going to have the least favorable one among the different pairings.
There's an important concept of a "blocking pair", and the Gale-Shapley algorithm is trying to eliminate all blocking pairs, and you could say that pairings are stable when no blocking pairs exist. A blocking pair is a job applicant and employer who aren't matched together, but both prefer each other over their current match.
Suppose that after the algorithm is done with its work, Alice doesn't end up with a job offer from her top choice, Google. This must mean that Google never offered her a job because Alice was just too far down on their list, and Google made a deal with someone else they like better than Alice.