The Stable Marriage Problem

Assume that two disjoint sets A and B of equal cardinality n are given. Find a set of n pairs <a, b> such that ain A and bin B satisfy some constraints. Many different criteria for such pairs exist; one of them is the rule called the “stable marriage rule.”

Assume that A is a set of men and Bis a set of women. Each man and each woman has stated distinct preferences for their partners. If the m couples are chosen such that there exists a man and a woman who are not married, but who would both prefer each other to their actual marriage partners, then the assignment is said to be unstable. If no such pair exists, it is called stable.

This situation characterizes many related problems in which assignments have to be made according to preferences, such as, for example, the choice of a school by students, the choice of recruits by different branches of the armed services, etc. The example of marriages is particularly intuitive; note, however, that the stated list of preferences is invariant and does not change after a particular assignment has been made. This rule simplifies the problem, but it also represents a distortion of reality (called abstraction).

One way to search for a solution is to try pairing off members of the two sets one after the other until the two sets are exhausted. Setting out to find all stable assignments, we can readily sketch a solution by using the program schema (3.35) as a template. Let try(m) denote the algorithm to find a partner for man m, and let this search proceed in the order of the man’s list of stated preferences. The first version based on these assumptions is (3.36)

Again, we have arrived at the point where we cannot proceed without first making some decisions about data representation. We introduce three scalar types, and, for reasons of simplicity, let their values be the integers 1 to n. Although the three types are formally identical, their designation149 by distinct names contributes significantly to clarity. In particular, it can more easily be made evident what a variable stands for.

The initial data are represented by two matrices that indicate the men’s and women’s preferences.

Accordingly, wmr[m] denotes the preference list of man m, i.e., wmr[ml][r] = wmr[m, r] is the woman who occupies the rth rank in the list of man m. Similarly, mwr[w] is the preference list of woman w, and mwr[w, r] is her rth choice.

The result is represented by an array of women x, such that x[m] denotes the partner of man m. In order to maintain symmetry—also called “equal rights”—between men and women, an additional array y is introduced, such that y[w] denotes the partner of woman w.

It is plain that y is not strictly necessary since it represents information that is already present through the existence of x. In fact, the relations

hold for all m, w who are married. Thus, the value y[w] could be determined by a simple search of x; the array y, however, clearly improves the efficiency of the algorithm. The information represented by x and y is needed to determine stability of a proposed set of marriages. Since this set is constructed stepwise by marrying individuals and testing stability after each proposed marriage, x and y are needed even before all their components are defined. In order to keep track of defined components, we may introduce Boolean arrays

An inspection of the proposed algorithm, however, quickly reveals that the marital status of a man is determined by the value m in a simple manner, namely that

This suggests that the array singlem be omitted; accordingly, we will simplify the name singlew to single.

These conventions lead to the refinement shown in (3.43). The predicate acceptable can be refined into the conjunction of single and stable, where stable is still a function to be further elaborated.

At this point, the strong similarity of this solution with Program 3.5 is still noticeable.

The crucial task is now the refinement of the algorithm to determine stability. Unfortunately, it is not possible to represent stability by such a simple expression as the safety of a queen’s position in Program 3.5. The first detail which should be kept in mind is that stability follows by definition from comparisons of preferences or ranks. The ranks of men or women, however,151 are nowhere explicitly available in our collection of data established so far. Surely, the rank of woman w in the mind of man m can be computed, but only by a costly search of w in wmr[m].

Since the computation of stability is a very frequent operation, it is advisable to make this information more directly accessible. To this end, we introduce the two matrices

such that rmw[m, w] denotes woman w’s rank in the preference list of man m, and rwm[w, m] denotes the tank of man m in the list of w. It is plain that the values of these auxiliary arrays are constant and can initially be determined from the values of wmr and mwr.

The process of determining the predicate stable now proceeds strictly according to its original definition. Recall that we are trying the feasibility of marrying m and w, where w = wmr[m, r], i.e., w has rank r in m’s list of preferences. Being optimistic, we first presume that stability still prevails, and then we set out to find possible sources of trouble. Where could they be hidden? There are two symmetrical possibilities:

1. There might be a woman py, preferred to w by m, who herself prefers m to her husband.

2. There -might be a man pm, preferred to m by w, who himself prefers w to his wife.

Pursuing trouble source 1, we compare ranks rwm[pw,m] and rwm[pw, y[pw]] for all women preferred to w by m, i.e., for all pw = wmr[m, i] such that i<_r. We happen to know that all these candidate women are already married because, were anyone of them still single, m would have picked her beforehand. The described process can be formulated by a simple linear search; s denotes stability.

Following trouble source 2, we must investigate all candidates pm who are preferred by w to their current assignation m, i.e., the investigators are all preferred men pm = mwr[w, i] such that i < rwm[w, m]. In analogy to tracing trouble source 1, comparison between ranks rmw[pm, w] and rmw[pm, x[pm]] will be necessary. We must be careful, however, to omit comparisons involving x[pm] where pm is still single. The necessary safeguard is a test pm < m, since we know that all men preceding m are already married.

The complete algorithm is shown in Program 3.6. Table 3.3 is a set of input data representing arrays wmr and mwr. Finally, Table 3.4 gives the nine computed stable solutions.

This algorithm is notably based on a straightforward backtracking scheme. Its efficiency primarily depends on the sophistication of the solution tree pruning scheme. A somewhat faster, but more complex and less transparent algorithm has been presented by McVitie and Wilson [3-1 and 3-2], who also have extended it to the case of sets (of men and women) of unequal size.

Algorithms of the kind of ‘the last two examples, which generate all possible solutions to a problem (given certain constraints), are often used to select one or several of the solutions which are optimal in some sense. In the present example, one might, for instance, be interested in the solution which on the average best satisfies the men—or the women—or all persons.

Notice that Table 3.4 indicates the sums of the ranks of all women in the preference lists of their husbands, and the sums of the ranks of all men in

The solution with the least value rm is called the male-optimal stable solution; the one with the smallest rw is the female-optimal stable solution. It lies in the nature of the chosen search strategy that good solutions from the men’s point of view are generated first and that the good solutions from the women’s perspective appear toward the end. In this sense, the algorithm is biased toward the male population. This can quickly be changed by systematically interchanging the role of men and women, i.e., by merely interchanging mwr with wmr and interchanging rmw with rwm.

We refrain from extending this program further and leave the incorporation of a search for an optimal solution to the next and last example of a backtracking algorithm.