The Perfect Match

Valentine’s day is upon us, a cheerful reminder that the main purpose of every living creature is to copulate as much as possible and spray the world with its offspring; the more, the merrier.
This is certainly easy enough for all those twice blessed prokaryotes; twice blessed, first, for their asexual reproduction via mitosis, obliviating the need for a mate; second for their lack of consciousness, avoiding the misery induced by the absence of aforementioned mate.
However, for the rest of us, finding that special someone is tricky business; it’s a game of both chance and skill, bluffing and honesty, combinatorics and probability (well, if you’re into that kind of stuff). It’s no wonder that the world is filled with attempts to make the whole process easier: dating sites, religious / traditional matchmaking, random-blind-date-generators, etc. But in the end, it all comes down to basic mathematics.

Let’s look at some of the well known algorithms and theorems for matching couples under different conditions. In quite stereotypical behaviour, mathematicians always assume that it’s possible to rank others by order of preference in a unique and unambiguous way, or that you can reject a suitor at point blank range without remorse, stating that “Sorry Billy, Roger is 0.2 [pretties] more handsome than you”, only to dump Roger two days later because the next person in the list comes along.
Oh well. Mathematics, thou art a harsh mistress.

Hall’s Marriage Theorem:
Our first theorem discusses whether it’s possible to get everyone married in a group of n men and n women, assuming that not everyone is willing to marry everyone else (sounds reasonable). The procedure is this: for each man and woman, ask them if they see themselves as a married, middle-age couple. If so, then they are potential wedlock candidates; otherwise, you won’t pair them up. Equivalently, you could ask every man to make a list of the women he would be ok marrying with, then have the women look at the lists and cross themselves out if they don’t agree.
The result can be given as a bipartite graph:

hall_bipartite

Each of the upper nodes represents a woman, each of the bottom nodes represents a man. An edge means that both are ok with an eternal life together. It’s quite possible that a very attractive, high quality person will have many edges, meaning, a lot of people are interested in marrying him/her, while other people might have little or no edges at all. In the above example, Lisa is very popular – everyone wants to marry her, and she agrees to marry with everyone – while Fae only has one possible mate. Thus, some people have more options than others, and the question is, can we assign couples, meaning, pick edges, so that *everyone* gets married in the end?
A simple case where the answer is a straightforward yes is:

bipartite_match

Each man is connected to one woman, and vice-versa – meaning that the couples are already picked here, and we have no real choice.
A case where the answer is no is:

bipartite_no_match

You can try picking out couples and seeing that a solution indeed does not exist.
Hall’s marriage theorem states that a complete matching exists, meaning, everyone can be paired, if and only if the following condition applies: look at all the possible subsets of men (i.e first look at all the men individually, then at all the pairs of men, then at all the triplets, etc.). For each subset M, count the number of different women that they can marry, G(M). Then |M| <= G(M).

We can see that the condition applies in the first case – for each man in the set, there is an appropriate woman, and thus M = G(M), and we have a matching. In the second case, however, the condition does not hold: look at Joe, Frank, and Mark: the three of them only have two potential mates: Jill and Lisa. The theorem does not hold, and indeed, there is no matching.
A proof of this theorem (actually a slightly more generalized one) can be found in wikipedia. Notice that the theorem doesn’t tell you at all how to find the matching, only that it exists.

Happy Marriage: The Hungarian Method:
Suppose now that our n bachelors and bachelorettes have had enough of the single life, and they decide that everyone should get married, no matter what. So instead of asking every pair whether or not they agree to marry each other, we ask them to rank the match. The result is a number for each (man, woman) pair; the higher it is, the more miserable they will be with their marriage. We want to find a matching between all men and women, such that the overall happiness is highest, meaning that the sum over all rankings of the chosen pairs is the lowest it can be.
A way of looking at this is the following: create a n x n matrix, where the (i,j) entry contains the ranking of matching the i-th man with the j-th woman. An example might be as follows:

hungarian_matrix

So a marriage between Frank and Anne would be a happy one, while a marriage between Joe and Jill would be rather miserable in its own way.
The question reduces to this: we need to choose n squares overall, each one in a different row and a different column, so that the sum of all the chosen squares is minimal.
The simplest way to solving this is the brute force approach: just go over all the possible matchings, and pick the best one. But when there are n men and n women, there are n! different possibilities. Try doing this for 30 men and women; tell me about it when the universe ends.
Something more clever is needed, and indeed, there exists an algorithm called the Hungarian Algorithm which can solve it in O(n3) moves. In general, it relies on the fact that you can add or subtract any number from an entire row or an entire column of the matrix, and this will not change the optimal matching. Think about it this way: if you add a number to an entire row, the total sum will change, but you are going to have to pick an entry in that row anyway, so whichever matching you choose, you will always get a larger sum.
The aim of the Hungarian algorithm is to add and subtract values from the different rows and columns in a clever way, so that the values in the matrix are always non-negative. Eventually, as if by magic mathematics, there appears an arrangement of zeros that can be picked as a matching. The algorithm is not simple, and will not be given here; conveniently, it can be found at this nice site (in the context of assigning jobs to workers, but hey, once you get to a matrix formulation, the mathematics is all the same).

Stable Marriages:
The previous algorithm gave us a global maximum for happy marriages – when we summed the total “miserableness” of the matching, it was the lowest possible between all possible matchings. However, it may be that one couple was a very bad match, and they live grumply and miserably, but in the overall matching, its still the minimum. We will now ask the question – can we make everyone happy locally?
Of course, we need to ask what that means. One interpretation is this: suppose that we match up all the couples. Some of them may be dissatisfied, and wish to break apart from the shackles of holy matrimony. If a woman desires another man more than she desires her own husband, and that man also desires that woman more than he desires his own wife, then they may each get a divorce from their current partners and marry each other instead. We say that the matching we initially had is “unstable”. If no such pairs exist, then the matching is stable.
The problem is then the following: suppose we ask each man to create a list, sorted by preference, of all the women, and we ask all the men to create a list, sorted by preference, of all the men. Can we create a stable matching, i.e, no two people will agree on replacing their partners?
It turns out that we always can, and rather efficiently, too. The basic algorithm for doing this is called the Gale-Shapley algorithm. It solves the problem in up to n2 iterations, as follows: in the first iteration, all the men approach the woman first on their list – the one they want the most. Some women may get a lot of suitors, while others may get none at all. This is ok. Each woman, from all the possible suitors, picks the man she likes best, and sends the rest away. So it goes. During every subsequent iteration, all the rejected men go to the next woman on their list, with the women picking between the new guys and the one they chose the previous iteration. The process continues until no one is rejected (this is bound to happen eventually; think why).
In the end, everyone gets matched up, and it can be proven that the matching contains no unstable couples. Of course, the scheme can also be reversed, with the women approaching the men (it turns out that this yields asymmetric results, with the active suitors getting matches that are better for them. Conclusion? It’s better to ask people out than to wait to be asked out).

Final remarks:
Feel free to assemble all your single friends and try these algorithms out. I’m sure it will create no social anxiety whatsoever, and in the end, everyone will be matched up! Hurray for mathematics.
Happy Valentine’s day.

* Note: in the problems introduced we always assumed the happy case, of an equal amount of men and women. Actually, all three problems can be extended to an unequal amount. For Hall’s theorem, instead of asking if everyone can be paired up, we can ask if all the men can find wives, or, conversely, if all the women can find husbands; the theorem stays the same. For the Hungarian algorithm, if there are, for example, more men than women, we can add fictitious “unmarriable-women” until there are an equal amount, and heavily penalize choosing them – no man would want to stay alone. The Gale-Shapely algorithm stays the same, knowing that not all participants will get a date at the end.
To sum it up and state the obvious: when there is a numerical bias towards one gender, someone always gets left out, resulting in mathematical misery. The Technion, having a whopping 35% female minority out of its 13,000 students, is a fine example of this (that’s actually a generous average term; in the physics and mathematics faculties, it’s about 20%…).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s