Matching Algorithms and Reproductive Health: Part 1, Matchings Emerge from Social Science

Earlier this week, I was inspired by current events to launch a bold, crazy-sounding series about matching theory and its application to reproductive health.  This first installment is a quick social history of the development of matching theory, largely influenced by (and fact-checked against) Lex Scrijver’s encyclopediac Combinatorial Optimization: Polyhedra and Efficiency.  His paper “On the history of combinatorial optimization (till 1960)” contains similar information in an easy-to-download form.

On to the story:  how social science applications drove the  development of matching theory. To start, let’s agree on what a matching is.

A subgraph M of a graph G is called a matching if every node in M has degree zero or one.

That’s fine for doing mathematics, but it leaves the terminology quite opaque. To better understand why “matching” is a good name for such a subgraph, consider a bipartite graph, where, on the left-hand side, the nodes represent people, and, on the right-hand side, the nodes represent jobs. If each edge represents an acceptable assignment of a person to a job, then any subgraph with all degrees zero or one corresponds to an acceptible way of matching people and jobs.

It is easy to dream up practical-sounding extensions of this context. For example, if each edge has a numeric weight, to indicate how desirable the job is to the person, then there is some assignment with maximum desirability. But can you find it? If there are n people and n jobs, then there are n! assignments to check, and even for small values, like n=20, there is not time to look at all of them.

It was exactly this quandary, applied to British soldiers during World War II, that led to the first published algorithm for solving the assignment problem. The author, T.E. Easterfield, described his motivation in his aptly titled paper “A combinatorial algorithm”:

In the course of a piece of organisational research into the problems of demobilisation in the R.A.F., it seemed that it might be possible to arrange the posting of men from disbanded units into other units in such a way that they would not need to be posted again before they were demobilised; and that a study of the numbers of men in the various release groups in each unit might enable this process to be carried out with a minimum number of postings. Unfortunately the unexpected ending of the Japanese war prevented the implications of this approach from being worked out in time for effective use.

(Greg Sorkin reminded me that this last sentence might be that dry, dry style of British irony!)

Easterfield’s algorithm is an improvement on searching all assignments, but it takes time , which is still not fast enough to be useful on anything but the smallest problems. However, the appeal of this exact application of matching theory, “matching men to jobs”, continued into the 1950s (catch that application name? I guess it was a 1950s thing). The psychologist Edward Thorndike worked on it in 1949; it must have been one of the last things he worked on. The first practical method for solving the assignment problem came in 1951, following the realization that the linear programming formulation of the problem always has an optimal value which is integral. But the really practical solution methods (combinatorial algorithms) emerged in the mid-to-late 50s. James Munkres, author of the red topology book (which is now greenish blue), took a break from his topology research to prove that a simple algorithm always finds the optimal solution in arithmetic operations. This was one of the first times that an algorithm which seemed good-in-practice had a proved worst-case polynomial-time bound, and Munkres snuck in a proud, fun lecture on it when I was in his calculus class back in my college days.

As I mentioned, the linear programming formulation has integral solutions. This follows from Birkhoff’s theorem that every doubly stochastic matrix is a convex combination of permutation matricies, which he in turn derived from Hall’s marriage theorem. This “marriage theorem” deserves a social history of its own, and a book on it by Knuth exists, but it consists of math lectures translated from English to French and back again, making it considerably less readable than other things by Knuth.

The stable matching (or stable marriage) problem takes place in a similar setting, and is actually used every year by young doctors and psychologists to assign residencies and practicums. The wikipedia entry does a classic job stating it:

Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women off such that there are no two people of opposite sex who would both rather have each other than their current partners.

I love/hate it, because it is such a blatant example of the anti-social world that mathematicians sometime create for ourselves. The real applications of this theory are not to marriges, of course, but this formulation was developed by Weyl to make it sound whimsical to other mathy folks. Let’s not even talk about how this is hetero-normative. Is it “sexist”? I’m not going to get into that right now…

Finally, let me make sure to mention that, although these examples have been about bipartite graphs, it is also interesting to consider matchings in general graphs. Things get more complicated computationally, the straight-forward linear program is not integral, and in the “stable roommates problem“, there is not guaranteed to be a solution (imagine how moral conservatives might try to make hay with that one).

Theoretical work on matchings continues today, including fast algorithms for random instances, investigations into why residency matching systems might work as well as some say that they do, and message passing algorithms.

That’s a lot of words about matchings, and not many about reproductive health. I mentioned war and patriarchy in passing, but the next installment will be much more directly connected, when I take a look at how matchings were a key tool of a recent analysis which found an association between taking a virginity pledge and having unprotected sex.

Also coming up: more applications, python code, and more potential applications.