Algorithm to Solve Arranged Marriages via the Hall Theorem

By

Home / Algorithm to Solve Arranged Marriages via the Hall Theorem
Marriage of Bride and Groom image by epSos.de

The Hall Theorem shows that an algorithm can make the perfect marriage. Image by epSos.de

An arranged marriage is common in some cultures, but controversial in others. Both human matchmakers and computer algorithms at dating sites have succeeded in finding perfect soulmates… sometimes.

How does the Hall Theorem show that an algorithm can, eventually, match choosy brides and willing grooms? Can a Turing machine verify these results?

The Simplified Marriage Problem for the Hall Theorem

The simplified marriage problem is to find an acceptable match for each woman, but not necessarily an ideal marriage to her “one and only.” It assumes that any one marriage is between one woman and one man; polygamy, polyandry and same-sex marriages are not considered in this mathematical problem.

We stipulate that the same finite number of men as women are participating, and that each man is willing to marry any woman who proposes.

This approach skips past the difficult task of determining the brides’ preferences among a group of prospective grooms. Instead, it begins after each woman has written her own list of those whom she is willing to marry.

Creating a System of Distinct Representatives

This marriage problem is an example of the mathematical task of creating a “system of distinct representatives,” or SDR, of a collection.

Let the collection C = {C[1], C[2], … C[n]}, a finite set of finite sets C[i]. Each C[i] = {e[i, 1], e[i, 2], …e[i, m]}, although these sets may have different numbers (‘m’) of elements.

Let T be any subset of C, so it contains some or all the sets C[i]. Then |T| = the number of sets C[i] in subset T.

The union set of all U(C[i] in T) contains all the elements C[i,j] found in T. Likewise, |U(C[i] in T)| is the number of unique elements C[i,j] found in T. This number may be less than the sum of elements in each C[i], since the C[i] may contain some of the same elements.

Finally, define S = any “system of distinct representatives” of T = any set of unique e[i, j] such that e[i, j] is in T, with one element from each C[i] and no element repeated.

How does this apply to the marriage problem? Each woman’s list is a set C[i]; each element e[i, j] is a man acceptable to this woman.

The marriage problem consists of creating an SDR that matches a unique man (or “e[i, j]”) to each woman (or “C[i]”).

Leave a Comment