Algorithm to Solve Arranged Marriages via the Hall Theorem

Marriage Theorem: Summary and Food for Thought

Don't depend on your computer too much! Image by ph0rk

The Hall Theorem proves that it is possible to “arrange marriages” under certain conditions, and impossible otherwise. It is also an example of a “decision problem” that computers can solve – we’ll discuss whether Turing Machines can solve the general case of the Decision Problem at a later date.

Similar algorithms may be used in assigning medical school residents to hospitals, and other assignment situations.

The complexity of the algorithm makes it very expensive or time-consuming, as the number of participants increases. When participation grows to 10 times the previous roster, then the workload increases 100 times.

Even working through the Hall Theorem to decide whether there is a solution, requires checking each combination of subsets of women, and sorting the names of the men each time to ensure each is only listed once.

The Hall Theorem: Points to Ponder

Does it seem reasonable that matchmaking services can juggle multiple factors to filter out your most compatible prospects, for the number of clients they claim? Is it likely your parents or a human matchmaker could do this for you, without a computer?

On the other hand, people may make intuitive choices when data is less certain. How much do you trust your intuition?

References:

Bogomolny, A. Marriage Theorem. Cut-the-Knot.org. Accessed May 8, 2012.

Cowen, L. Lecture 1: Perfect and Stable Marriages. (2011). Tufts University. PDF accessed May 8, 2012.

McLeman, C. and Ferguson, K. Hall’s marriage theorem (version 3). PlanetMath.org. Accessed May 8, 2012.