Posted November 2004.
These theorems involve such intuitively appealing yet deep ideas that they serve as a metaphor for the marriage of the emotional and intellectual, examples of mathematics at its most transcendent.
A more general situation occurs if we have equal numbers of men and women but we do not necessarily have the same number of women known by each man and by each woman.
Can you see why it is impossible to marry off all the men to women they know in the diagram above? (Hint: Look at the men at the far left and the far right!)
Can you see how to pair off the men and women so that they know each other? Not a total triviality. Here is a solution:
So, we have several issues to address here: When can one marry off the men to the women, and is there an algorithm, a simple set of rules, that can be followed, that will find such a pairing when one exists in a reasonable amount of time, even for large numbers of men and women?
Hall had come across his theorem in 1935 (as a result about cosets in group theory); in recent years it is typically stated as a theorem about sets. The basic idea is to define a system of distinct representatives (SDR). Think of having a list of committees which have potentially overlapping membership. The goal is to elect a different chairperson for each committee. Abstracting, we have a collection of (unordered) sets of objects whose members have been chosen from some list M of objects. The connection with marriage theorems is that one can think of the sets as being the names that each woman lists for the men (who are the elements of the set M, which explains the use of the letter M) whom she would accept as a mate. Assigning each woman a unique man means finding an SDR for the women's sets. Hall's Theorem states that an SDR exists if and only if for any number i of the women (for i equal to one up to the total number of women) the lumping together of the men on the lists of the i women contains at least i men. (If, for example, 5 of the women only have 4 men on their lists of potential mates, no marriage assignment is possible.) The statement of Hall's Theorem, though very elegant, does not lead immediately to finding an SDR in an efficient way, it only gives a test to see if such an SDR exists. The role of an SDR in the set formulation is related to the notion of a matching in a graph. In this setting, finding an SDR becomes more practical.
Our job is take these rankings and marry the men to the women, but how are we to judge when one way of pairing off the people into couples is better or worse than another way?
The Male Optimal Stable Matching is:
It is interesting that regional systems which developed in Great Britain to match doctors to hospitals were sometimes successful and sometimes not. In examining those regional systems that worked versus those that "fell apart" due to students working outside the system, the key turned out to be that nearly always, the systems that used algorithms which guaranteed stability for the matchings were successful, while those that were not stable did not function well. This empirical information was an interesting vindication that the "theoretical" notion of a stable matching was an important one for practical applications. The NRMP has over the years been the source of a complicated debate over which stable matching algorithm best met the collective needs of students, hospitals, and the nation. Not all of the debate centered around the matching aspects of the process. Some claimed that the system violated anti-trust laws by allowing hospitals to get a cheap source of qualified "laborers."
Adachi, Hiroyuki. On a characterization of stable matchings. Econom. Lett. 68 (2000), no. 1, 43--49. MR1765147 (2001e:91128)
Aldershof, Brian; Carducci, Olivia M. Stable matchings with couples. Discrete Appl. Math. 68 (1996), no. 1-2, 203--207. MR1393319 (97a:05011)
Balinski, Michel; Ratier, Guillaume . On stable marriages and graphs, and strategy and polytopes. SIAM Rev. 39 (1997), no. 4, 575--604. MR1491048 (99b:90096)
Blair, Charles. Every finite distributive lattice is a set of stable matchings. J. Combin. Theory Ser. A 37 (1984), no. 3, 353--356. MR0769224 (86d:05032)
Colenbrander, A., Match algorithms revisited, Academic Medicine, 71 (1996) 414-415.
Mongell, S. and A. Roth, Sorority rush as a two-sided matching mechanism, Amer. Economic Rev., 81 (1991) 441-464.
Rothblum, Uriel G. Characterization of stable matchings as extreme points of a polytope. Math. Programming 54 (1992), no. 1, Ser. A, 57--67. MR1158813 (93c:90065)
NOTE: Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal, which also provides bibliographic services.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance