The topic of today’s blog post is about optimally finding a spouse using optimization models (HT Anna Nagurney). This post is based on a paper published in EJOR entitled, “Optimizing the Marriage Market: An Application of the Linear Assignment Model,” and in it, researchers apply the linear assignment problem to identify how to optimally match potential (heterosexual) couples to find a new social optimum. While matching the couples is a textbook exercise, the researchers used a longitudinal dataset in Switzerland to identify meaning weights to assign to each potential pairing. They find that the actual marriages are far from optimal.

The weights are based on logistic regression models for predicting the likelihood of divorce from a longitudinal data set. The weights are based on four types of socioeconomic variables of each person in the set:

1. Age
2. Previous divorce (or not)
3. Education (high or low)
4. Nationality (Swiss, Western, or non-Western)

The weights for each pairing are not symmetric. For example, a wife is much more likely to divorce from a husband five years her junior than five years her senior.

The assignment problem is an integer programming model that produces the lowest cost one-to-one matching between two sets of items, such as individuals and jobs. Here, the two sets of items are men and women. The assignment problem is totally unimodular, and therefore, can be efficiently solved via the Hungarian algorithm.

Let:

• W = set of women
• M = set of men (with |W|=|M|)
• x{ij} = 1 if woman i is matched to man j, i in W and j in M
• c{ij} = the “cost” of matching woman i is to man j.

The optimization problem is:

A solution to the assignment problem admits exactly m=|M| = |W| variables with value 1 (the rest of the variables are zero). The structure here is a bipartite graph: one set of nodes represents the women and the other set of nodes represents the men. Every women is connected to all the men (and none of the women) and vice versa. There are m! possible matchings (corresponding to some permutation of possible pairings), and the assignment polytope has m! extreme points.

The Hungarian algorithm works by finding the reduced cost matrix, by first subtracting the smallest value in each row from the entire row. This is repeated for each row, leaving a zero in each row. Then, this is repeated over the columns. The resulting reduced matrix will have a zero in every column and every row, and all of its entries will be nonnegative. The optimal solution is identified by covering the zeros by adding lines row-wise and column-wise in a multi-step procedure.

I put together a small Excel spreadsheet with 9 men and women [Link to my Excel file and to the instructions], where I solve the assignment program. Please download and use in an introductory LP class.

The authors of the paper say that their method is an “innovative method of optimizing romantic partner allocation.” Of course, this is no way to find a partner for life.  However, the authors point out that they could substantially improve marriage survival by reallocating 68% of the pairings. They conclude that “current marriage markets are suboptimally organized.” My Valentine’s Day wish to my readers is that you optimally organize your love life with or without the use of optimization models.