In 1962,
David Gale and
Lloyd Shapley proved that, for any equal number in different groups, in the context of college admissions and individuals wanting marriage it is always possible to solve as matched couples to make all resultant pairings / matched factors stable. They presented an
algorithm to do so. The
Gale–Shapley algorithm (also known as the deferred acceptance algorithm) involves a number of "rounds" (or "
iterations"): • In the first round, first
a) each unengaged man proposes to the woman he prefers most, and then
b) each woman replies "maybe" to her suitor she most prefers and "no" to all other suitors. She is then provisionally "engaged" to the suitor she most prefers so far, and that suitor is likewise provisionally engaged to her. • In each subsequent round, first
a) each unengaged man proposes to the most-preferred woman to whom he has not yet proposed (regardless of whether the woman is already engaged), and then
b) each woman replies "maybe" if she is currently not engaged or if she prefers this man over her current provisional partner (in this case, she rejects her current provisional partner who becomes unengaged). The provisional nature of engagements preserves the right of an already-engaged woman to "trade up" (and, in the process, to "jilt" her until-then partner). • This process is repeated until everyone is engaged. This algorithm is guaranteed to produce a stable marriage for all participants in
time O(n^2) where n is the number of men or women. Among all possible different stable matchings, it always yields the one that is best for all men among all stable matchings, and worst for all women. It is a
truthful mechanism from the point of view of men (the proposing side), i.e., no man can get a better matching for himself by misrepresenting his preferences. Moreover, the GS algorithm is even
group-strategy proof for men, i.e., no coalition of men can coordinate a misrepresentation of their preferences such that all men in the coalition are strictly better-off. However, it is possible for some coalition to misrepresent their preferences such that some men are better-off and the other men retain the same partner. The GS algorithm is non-truthful for the women (the reviewing side): each woman may be able to misrepresent her preferences and get a better match. The Gale–Shapley algorithm also exposes parallelism for accelerating large-scale SMP instances, since unengaged men can make proposals independently in each round. Parallel implementations can assign men to different threads, resolve simultaneous proposals with synchronization primitives, and use optimizations such as queue avoidance, locality-aware data layouts, and hybrid CPU–GPU execution to reduce overhead. ==Rural hospitals theorem==