The Gale-Shapley algorithm works as follows: Single men ("the proposers")
sequentially make proposals to each of their most preferred available women
("the reviewers"). A woman can hold on to at most one proposal at a time. A
single woman will accept any proposal that is made to her. A woman that
already holds on to a proposal will reject any proposal by a man that she
values less than her current match. If a woman receives a proposal from a man
that she values more than her current match, then she will accept the
proposal and her previous match will join the line of bachelors. This process
continues until all men are matched to women.
The Gale-Shapley Algorithm requires a complete specification of proposers'
and reviewers' preferences over each other. Preferences can be
passed on to the algorithm in ordinal form (e.g. man 3 prefers woman 1 over
woman 3 over woman 2) or in cardinal form (e.g. man 3 receives payoff 3.14 from
being matched to woman 1, payoff 2.51 from being matched to woman 3, and payoff
2.15 from being matched to woman 2). Preferences must be complete, i.e.
all proposers must have fully specified preferences over all reviewers and
vice versa.
In the version of the algorithm that is implemented here, all individuals --
proposers and reviewers -- prefer being matched to anyone to not being
matched at all.
The algorithm still works with an unequal number of proposers and reviewers.
In that case some agents will remain unmatched.
This function can also be called using galeShapley
.