Algorithm to Solve Arranged Marriages via the Hall Theorem

By

Home / Algorithm to Solve Arranged Marriages via the Hall Theorem

Should you bypass 'He loves me, He loves me not' with a computer program? Image by Fordos

Informal Discussion of the Hall Theorem

The Hall Theorem can be informally supported by mathematical induction, by showing that no woman would be left without a groom. The formal proof uses the properties of “bipartite graphs” and “saturated vertices”; see Cowen’s lecture notes (in PDF format) for the details, as well as an entertaining discussion about King Arthur and Merlin.

First, if no women participate, then there are none to be left unmarried. If exactly one woman lists at least one man, then she will be married.

Let’s break with the usual induction proof, and note the case of two women who satisfy the condition |T| is less than or equal to |U(C[i] in T)|. If each lists the same two men, the problem is solved very quickly. The first woman gets her first choice; the second woman gets the leftover man. If both women choose a different man, again they are immediately matched.

However, suppose one of the women lists two men, but the other chooses only one of them. If we assign the second woman’s only choice to the first woman, then the second woman would have no-one. However, using the algorithm above, we would backtrack and re-assign the second man to the first woman. This leaves the second woman free to claim her one and only.

If both women list only one man, and the same man, then clearly they cannot both become married; one would have to be left a spinster.

Next, we assume that the Hall Theorem is true for n women, and use that assumption for n + 1. We should also state the assumption that every subcollection that now includes the final woman does indeed satisfy the condition that “|T| is less than or equal to |U(C[i] in T)|”.

By the induction principle, we have assumed that we will find a match for the first n women, even if we need to backtrack and re-assign. If the final woman’s list has the last unclaimed male, then the marriage problem is solved.

So, let’s say that the last woman’s list does not include the last unclaimed man. There must be at least one unclaimed man in the lists of the first n women. One of those women may be re-assigned to an unclaimed man; if that releases a man to the final woman, then the problem is solved. If not, we continue swapping until matches are made… if possible.

Eventually, we either find a match, or find a particular subcollection that fails the condition that |T| is less than or equal to |U(C[i] in T)|. That would be in contradiction to the assumption that the condition was met.

Leave a Comment