An Algorithm to Solve the Marriage Problem
An algorithm, or set of rules that is programmed into a computer, can solve the marriage problem once the women make their lists. This is how it works:
- Start with the first woman’s list. Assign the first (available) man on her list to her.
- Continue with the rest of the women, assigning the first man not already taken by another woman.
- Whenever we find a woman whose list only has men who already have been taken, go back to the previous woman and select the next available man; then resume with the next woman (whose list now has that man available.)
- Stop when every woman has her own man.
Note that the above algorithm might backtrack from the last woman all the way to the first, if that’s what it takes to arrange marriages by creating an SDR.
This is a very inefficient algorithm; for n women, it may need to consider some n^2 (n-squared) possible marriages. (It is similar to the inefficient “bubble sort” algorithm. Programmers prefer algorithms that grow more slowly, as a multiple of n).
However, this algorithm can, in theory, be followed by a Turing machine or any real, physical computer; it may just take a very long time to deal with a large number of potential couples.
Deciding Whether a Particular Marriage Problem can be Solved
One can spare the computer by deciding quickly that a particular collection of women cannot possibly solve their marriage problem.
Obviously, if there are more women than men, some women would be fated to be spinsters. However, the Hall Theorem can decide whether a particular marriage problem can be resolved in those cases where the number of men and women are equal.
The Hall Theorem
The Hall Theorem states that an SDR can be determined if, and only if, |T| is ≤ |U(C[i] in T)| for every subset ‘T’ of ‘C’. (In English: the number of elements in every subset T is less than or equal to the number of unique elements in the union of all sets C[i] in that T).
Here is an English explanation of the Hall Theorem:
The set ‘T’ is any subset of ‘C’, up to the full collection of all the women.
|T| represents the number of women, and also the number of lists of their desirable men. |U(C[i] in T)| is the number of unique men named by these women.
If the women name fewer men than there are women, if every woman insists on marrying Brad Pitt, for example, then they will be disappointed.
If the women name at least as many different men as there are women, then each woman will have an acceptable groom.
Note that the condition must be true for each and every subset ‘T’ of ‘C’; otherwise there is a subset where at least one woman cannot find a husband.
Decoding Science. One article at a time.