There are many applications in which one wants to produce a self-enforcing matching algorithm, such that no unmatched pair would mutually prefer breaking the existing pair and pairing with each other. This problem is most readily approached as a matching of n parties to n parties, even though most real-world situations are n×m (reflecting a general intuition that it is often easiest to approach a hard problem by first solving related but simpler problems and then extending the solution to the harder case). The Gale-Shapley algorithm finds such a stable matching in n^2 time, which proves the existence of such a matching given any set of preferences.
Interestingly, this seems to be a subset of cooperative game theory, which I studied a bit last . There, people gain from entering coalitions, and the task is to find distributions of the gain that prevent voluntary defection.
No questions.
I find all this talk about fairness rather annoying–it may be a curiosity of the algorithm, but is never treated rigorously. Indeed, it is not even a proper part of the problem–the task is to find a stable matching, not a stable and fair algorithm. Especially given that this is the first formal example, this seems a most distracting addition. While the discussion of fairness seems to be leading into the proof that the algorithm specifies a single matching for every set of preferences, its treatment is hardly necessary to that end. Nevertheless, 7/10; verbose, but fairly clear.
