A matchmaking service wants to couple $$n$$ men $$m_0, m_1, \ldots, m_{n-1}$$ with $$n$$ women $$w_0, w_1, \ldots, w_{n-1}$$. Each man and each woman was asked to arrange all candidates of the opposite sex according to their personal preference. The preferences of the men and the preferences of the women can be represented as two $$n \times n$$ tables. The first row of the table containing the preferences of the men, for example, indicates how man $$m_0$$ has ordered the women. A value $$i$$ ($$0 \leq i < n$$) in the first column indicates that the first choice of man $$m_0$$ is woman $$w_i$$. A value $$j$$ ($$0 \leq j < n$$) in the second column indicates that the second choice of man $$m_0$$ is woman $$w_j$$. Analogously, the second row of the table indicates how man $$m_1$$ has ordered the women. The table containing the preferences of the women is structured in the same way.

The following two tables show an example of the preferences given by four men (left) and four women (right), where the candidates of both groups have been labelled 0, 1, 2 and 3.

From these tables, we can derive for example that the first choice of man $$m_0$$ is woman $$w_1$$, whereas man $$m_0$$ itself is only the third choice of woman $$w_1$$.

The matchmaking service now wants to make a pairwise coupling of the men and women, taking into account their personal preferences. They want to do this in such a way that it is not possible anymore to find a man and a woman that mutually favors each other above the partners they have been coupled with. If they succeed to do so, chances are high that this will lead to stable marriages. We refer to this article¹ for a detailed explanation and more background information about the stable marriage problem².

Algorithm

David Gale and Lloyd Shapley proved in 1962 that it is always possible to find a stable solution for the above problem in case there's an equal amount of men and women. They also provided an algorithm to find this solution. The Gale-Shapley algorithm can be described as follows:

initially all men and all women are free (not coupled)
as long as there still is a free man M (that has not been coupled to a woman)
    find the most preferenced woman W that man M was not coupled with before (*)
    if woman W is free (not coupled)
        couple man M to woman W
    otherwise woman W must be coupled to a male competitor C
        if woman W prefers man M over man C
            couple man M to woman W
            make man C a free man again (no longer coupled with woman W)
        otherwise woman W remains coupled to man C

Gale and Shapley also proved that at point (*) of the algorithm, there will always be a woman $$W$$ that has not gotten a proposal from man $$M$$.

For the sample tables containing the preferences of men and women as given above, the algorithm takes the following steps:

• iteration 1: man 0 is coupled to woman 1 (his first choice)

• iteration 2: man 1 is coupled to woman 3 (his first choice)

• iteration 3: man 2 is coupled to woman 0 (his first choice)

• iteration 4: man 3 is coupled to woman 1 (his first choice), because woman 1 prefers man 3 over man 0; man 0 is free again

• iteration 5: man 0 is coupled to woman 0 (his second choice), because woman 0 prefers man 0 over man 2; man 2 is free again

• iteration 6: man 2 is coupled to woman 2 (his second choice)

• all men and all women are now coupled

  • man 0 $$\leftrightarrow$$ woman 0

  • man 1 $$\leftrightarrow$$ woman 3

  • man 2 $$\leftrightarrow$$ woman 2

  • man 3 $$\leftrightarrow$$ woman 1

Assignment

Write a function matchmaking that implements the Gale-Shapley algorithm. The function takes two arguments that respectively represent the personal preferences of a group of $$n$$ men and a group of $$n$$ women. Each argument represents a table of preferences, given as a list (list) of lists (list) of integers (int), where each of the inner lists represents an ordering of the numbers $$0, 1, \ldots, n-1$$. The function must return a tuple of couples, where each couple is itself represented as a tuple containing two integers (int): the label of a man and the label of the woman the man was coupled with. The couples must be arranged in ascending order of the labels assigned to the men.

Example

>>> preference_men = [[1, 0, 2, 3], [3, 0, 1, 2], [0, 2, 1, 3], [1, 2, 0, 3]]
>>> preference_women = [[0, 2, 1, 3], [2, 3, 0, 1], [3, 1, 2, 0], [2, 1, 0, 3]]
>>> matchmaking(preference_men, preference_women)
((0, 0), (1, 3), (2, 2), (3, 1))

>>> preference_men = [[0, 2, 1], [1, 0, 2], [1, 2, 0]]
>>> preference_women = [[2, 1, 0], [2, 1, 0], [1, 2, 0]]
>>> matchmaking(preference_men, preference_women)
((0, 2), (1, 0), (2, 1))

>>> preference_men = [[0, 2, 1, 3], [2, 1, 3, 0], [0, 3, 1, 2], [1, 2, 0, 3]]
>>> preference_women = [[1, 0, 2, 3], [0, 2, 3, 1], [3, 0, 1, 2], [1, 3, 2, 0]]
>>> matchmaking(preference_men, preference_women)
((0, 0), (1, 2), (2, 3), (3, 1))

The first example corresponds to the sample tables containing the preferences of men and women as given above. The solution for these tables can be represented graphically as:

Resources

• Mairson H (1992). The stable marriage problem. The Brandeis Review 12(1). ³