Sequences of the Stable Matching Problem

Matvey Borodin, Aidan Duncan, Boyan Litchev, Jiahe Liu, Veronika Moroz,

Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt

PRIMES STEP Department of Mathematics MIT 77 Massachusetts Ave. Cambridge, MA 02139 USA

                 primes.step@gmail.com

Tanya Khovanova Department of Mathematics MIT 77 Massachusetts Ave. Cambridge, MA 02139 USA

                  tanya@math.mit.edu

Abstract

We begin this paper by discussing different types of preference profiles related to the stable marriage problem. We then introduce the concept of soulmates, where a man and a woman rank each other first, and hell-pairs, where a man and a woman rank each other last. We generate sequences enumerating preference profiles of different types. We also calculate sequences related to the egalitarian cost, or “quality”, of a matching. In total, we introduce and discuss 30 new sequences related to the stable marriage problem and discuss 6 sequences that are already in the On-Line Encyclopedia of Integer Sequences.

1 Introduction

In the stable marriage problem (SMP) [2], n men and n women get married depending on their preferences in such a way that the matching is stable. A matching is not stable if there exist two people of opposite genders who prefer each other over their assigned partners.

The SMP applies to a variety of settings and has many applications and generalizations. The most famous application is used for matching medical students with residency programs [2], which is a variation of the stable marriage problem where hospitals are allowed to hire several graduate students.

In this paper, we describe many sequences related to this problem.

In Section 2, we describe our assumptions in accordance with the original setting of the stable marriage problem, where people of two different genders marry each other. We give preliminary definitions, including the egalitarian cost for matching a pair of people of opposite genders.

In Section 3, we introduce sequences related to different types of preference profiles depending on n, the number of men, which is the same as the number of women. These sequences describe the total number of preference profiles, as well as the number of preference profiles for each of the following: profiles where all men prefer the same woman, profiles where the first man is more desirable than the second man, profiles where all men rank the women the same way, profiles where all women have distinct men as their first choice, and profiles where the matrix of men’s profiles forms a Latin square.

In Section 4, we concentrate on sequences that depend on the number of soulmate pairs. Soulmate pairs are important in the SMP as they describe a pair of people who rank each other first. As a result, in a stable matching, any two people in a soulmate pair must be married, and then, they can be removed from consideration. We count the number of profiles with k pairs of soulmates. We also count the number of profiles with k pairs of soulmates in a special case when the men’s and women’s preferences form Latin squares. We provide formulas for these sequences.

In Section 5, we calculate the number of profiles that generate a given number of stable matchings. There is no easy formula for these numbers, so they are calculated by a program. Given the computational complexity, we only calculated the values for n up to n = 4. For n = 2, the number of stable matchings could be either 1 or 2. For n = 3, the number of stable matchings could be 1, 2, or 3. For n = 4, the number of stable matchings is not more than 10.

In Section 6, we consider some interesting sequences. First, we look at hell-pairs. A hell-pair is a pair of people of opposite genders who rank each other last. Intriguingly, they may still end up together in a stable matching, in which case we call them a hell-couple. We count the number of profiles where hell-couples are possible. Then we count the number of profiles containing outcasts—two people of opposite genders whom everyone else ranks last, making them destined for each other in a stable marriage. Finally, we enumerate the profiles where the outcasts form a hell-couple.

Section 7 is devoted to the symmetries of the SMP. We count the number of preference profiles up to relabeling men.

Given a preference profile, it is possible to have different stable matchings with different egalitarian costs. In Section 8, for values of n up to 4, we investigate which egalitarian costs are possible in a stable matching. In addition, we count the total number of stable matchings for a given egalitarian cost.

2 Preliminaries

First, we make several assumptions:

• We have n men and n women.

• Each person prefers to be married over being single.

• A man only marries a woman, and vice versa.

• Each person ranks people of the opposite gender without ties.

Thus, each man numbers the n women in increasing order from 1 through n, with 1 being his favorite and n being his least favorite. Similarly, each woman numbers the n men in increasing order from 1 through n, with 1 being her favorite and n being her least favorite. We call these 2n sets of preferences a preference profile.

We can look separately at men’s profiles and women’s profiles. We can arrange men’s preferences in a matrix where the i-th row corresponds to the i-th man’s preferences. Thus, each row is a permutation of the numbers 1 through n in such a matrix. Similar arguments work for women’s preferences.

Once all the preference profiles are set, people are paired into marriages. We call the set of all these marriages unstable if there is a man m and woman w such that they prefer each other to their spouses, and stable if no such man/woman pair exists. In an unstable set of marriages, the pair m and w described above is called a blocking pair or a rogue couple. By definition, a set of marriages without a rogue couple is stable.

We call a set of stable marriages a stable matching. We denote the maximum number of stable matchings for n men and n women as M(n). If two people can end up married in a stable matching, they are called valid partners of each other.

The Gale-Shapley algorithm [2], also known as the deferred acceptance algorithm, finds a stable matching given a preference profile. It involves a number of rounds described as follows:

• In the first round, each man proposes to the woman he prefers most, and then each woman replies “maybe” to her most preferable suitor and “no” to all other suitors. Each woman is then provisionally “engaged” to the suitor she prefers the most out of those who proposed to her in that round. This suitor is, likewise, provisionally engaged to her.

• In each subsequent round, each unengaged man proposes to the woman he prefers most out of the women to whom he has not yet proposed, regardless of whether the woman is already engaged. Then, each woman becomes provisionally engaged to the suitor she prefers the most out of those who have proposed to her so far. In doing so, she may reject her current provisional partner, who then becomes unengaged.

• This process is repeated until everyone is engaged.

This version of the algorithm is called men-proposing. By symmetry, there exists a women-proposing algorithm. The men-proposing Gale-Shapley algorithm is man-optimal and woman-pessimal. That means every man gets paired with the best possible valid partner, and every woman gets paired with the worst possible one. By symmetry, the womenproposing Gale-Shapley algorithm is woman-optimal and man-pessimal.

2.1 The egalitarian cost

The pairwise egalitarian cost of a man and a woman is the sum of the rankings they give each other [3]. If we suppose woman w ranks man m as i-th in her preferences, and m ranks w as j-th in his preferences, then the egalitarian cost of the pair (m, w) equals i + j. The egalitarian cost of a stable matching is the sum of all the pairwise egalitarian costs of the married couples in the matching. Any matching with the smallest possible egalitarian cost is called egalitarian.

Now, suppose we have a man and a woman with a pairwise egalitarian cost of 2. This means that they both rank each other first. Thus, unless they are married, they will form a blocking pair. That means any stable marriage has to have them as a couple. We call such a pair a soulmate pair or soulmates.

Soulmates are important as they reduce the matching problem to fewer people. In a stable matching problem with n men, n women, and k pairs of soulmates, the number of stable matchings is the same as the number for the group of people from which the soulmate couples are removed, with the preferences for each person adjusted accordingly. In particular, the maximum number of stable marriages for any set of 2n people with k pairs of soulmates cannot exceed M(n − k).

3 Preference profiles

3.1 The total number of profiles

The total number of different preference profiles is

(n!)^{2n},

as each person can rank the opposite gender in n! ways.

Here are the first few terms of the sequence for the total number of different preference profiles, with the first term corresponding to n = 1:

1, 16, 46656, 110075314176, 619173642240000000000.

This is sequence \underline{A185141} in the OEIS [4]. It is defined as “a(n) is the number of ‘templates,’ or ways of placing a single digit within an n^{2}-by-n^{2} Sudoku puzzle so that all rows, columns, and n-by-n blocks have exactly one copy of the digit.” This connection between preference profiles and Sudoku puzzles has already been studied in [1].

3.2 The homecoming queen

We consider profiles where all men prefer the same woman. We call this woman a homecoming queen. We count the profiles where a homecoming queen exists. Equivalently, we can consider the profiles where all women have the same man, a homecoming king, as their first choice.

For n men and n women, there are n ways to pick the woman that all men rank first. Then there are ((n − 1)!)^{n} ways to fill in the rest of their preference profiles. There are then (n!)^{n} ways to fill in the preference profiles for the women. This results in a total of

n((n − 1)!)^{n}(n!)^{n}

profiles where all men prefer the same woman. This is the same number of preference profiles as when there exists a woman that all men rank at the i-th place, where i can be anywhere from 1 to n.

The sequence of the total number of preference profiles where all men prefer the same woman as their first choice is now sequence \underline{A340890} and starts as follows:

1, 8, 5184, 1719926784, 990677827584000000, 2495937495082991616000000000000, ….

We can ignore women’s preferences and divide the sequence by (n!)^{n}. We get the following sequence, which counts the number of different possible men’s preferences in the stable marriage problem with the homecoming queen. This is now sequence \underline{A342573}:

1, 2, 24, 5184, 39813120, 17915904000000, ….

The formula for the n-th term is

n((n − 1)!)^{n}.

This sequence can be viewed as the number of ordered n-tuples consisting of n (not necessarily distinct) permutations of order n such that the first element of each of them is the same. Equivalently, we can say that the i-th element of each of them is the same.

If we can assume that the homecoming queen is woman number 1, then the number of such men’s profiles is sequence a(n) = ((n − 1)!)^{n}.

1, 1, 8, 1296, 7962624, 2985984000000, 100306130042880000000, ….

This sequence is the same as sequence \underline{A091868} shifted by 1.

Another natural sequence is the number of profiles where all men prefer the same woman and all women prefer the same man. To calculate the sequence, we just need to square the corresponding terms in sequence \underline{A342573}, which is the number of different possible men’s preferences where they all prefer the same woman as their first choice. We get

1, 4, 576, 26873856, 1585084524134400, 320979616137216000000000000, ….

This is now sequence \underline{A343474}: the number of preference profiles with a homecoming queen and king. The queen and king rank each other first, meaning they are soulmates. Such profiles have exactly one pair of soulmates.

3.3 One woman is more preferable than another

The homecoming queen is a more desirable woman than any other woman. We want to relax this condition and consider a pair of women where woman w_{1} is always ranked higher than woman w_{2}.

We see that for each man, there are \frac{n!}{2} possible profiles, as only half of all potential profiles meet our conditions. Note that we are assuming that n > 1. The total number of ways to arrange all the men’s profiles is

\frac{(n!)^{n}}{2^{n}} .

They form sequence \underline{A343692} starting with index 2:

1, 27, 20736, 777600000, 2176782336000000, ….

By symmetry, sequence \underline{A343692} counts the number of women’s preferences where man m_{1} is always more desired than man m_{2}.

Going back to counting profiles where one woman is more preferable than another, since there are no conditions for the women’s preferences, there are (n!)^{n} ways to arrange them. This gives us a total of

\frac{(n!)^{2n}}{2^{n}}

profiles where every man prefers woman w_{1} over w_{2}. This is now sequence \underline{A338665}, and it starts as

4, 5832, 6879707136, 19349176320000000000, ….

Since every man prefers woman w_{1} to woman w_{2}, he will always propose to woman w_{1} first. When woman w_{2} is proposed to, the man proposing to her has already proposed to woman w_{1}. Since a man can only propose once per round, woman w_{1} is first proposed to by him in an earlier round than woman w_{2}. Once a woman is proposed to, she will remain engaged (not necessarily with the same man) for the rest of the algorithm, so woman w_{1}’s first engagement comes in an earlier round than woman w_{2}’s.

We also consider a symmetric case where both conditions apply: man m_{1} is more desired than man m_{2}, and woman w_{1} is more desired than woman w_{2}. The corresponding sequence is the square of sequence \underline{A343692}; that is, the number of profiles is

\frac{(n!)^{2n}}{4^{n}} .

It is now sequence \underline{A343693}: the number of preference profiles for n men and n women, with n > 1, such that all men prefer woman w_{1} over woman w_{2} and all women prefer man m_{1} over man m_{2}.

1, 729, 429981696, 604661760000000000.

This sequence is sequence \underline{A338665} divided by 2^{n}.

3.4 Same taste

Suppose the men have exactly the same taste meaning that they rank all the women in the same order. Then, the number of ways to arrange men’s preferences is n!, since every man ranks all the women in the same order. This is the sequence of factorial numbers, \underline{A000142}.

If we also consider the women’s preferences, we get a total of (n!)^{n+1} profiles, since the women can rank the men in any order. This sequence of preference profiles corresponds to the OEIS sequence \underline{A091868} and starts as

1, 1, 8, 1296, 7962624, 2985984000000, ….

Performing the Gale-Shapley Algorithm on these profiles always leads to a special result, as we show below.

Proposition 1. When the men all rank the women in the same order, the men-proposing Gale-Shapley algorithm ends in exactly n rounds.

Proof. In the first round of the men-proposing algorithm, all men propose to the same woman: the homecoming queen. She gets engaged to the man of her first choice. In the second round, the n − 1 unengaged men propose to the same woman who is second on their lists, so she gets engaged to her most-preferred man out of the n − 1 men. This continues for n rounds.

Interestingly, we get couples with mutual rankings (1,1), (2,2), and so on. The egalitarian cost of the resulting matching is

n(n + 1).

Notice that if both men and women have the same taste, then the number of such profiles is just (n!)^{2}. This corresponds to the sequence of factorial squares, \underline{A001044}:

1, 4, 36, 576, 14400, 518400, 25401600, 1625702400, ….

3.5 Tastes differ

On the opposite side of the spectrum, consider the scenario where each woman is the first choice for exactly one man, which we call the case where men’s tastes differ. As compared to the previous case, this one may have a chance to make more people happier.

For n men and n women, there are n! ways for the men to arrange their first choices and ((n − 1)!)^{n} ways to rank the rest of the women. We can set the women’s preferences in (n!)^{n} ways, since their preferences are not restricted, giving us a total of

(n!)^{n+1}((n − 1)!)^{n}

preference profiles where all men prefer different women. In general, this sequence describes the number of profiles where each man ranks a different woman as his i-th choice.

The sequence of preference profiles where all men prefer different women as their first choices, which is now \underline{A343475}, starts as follows:

1, 8, 10368, 10319560704, 23776267862016000000, ….

Proposition 2. The men-proposing Gale-Shapley algorithm terminates in one round if and only if each woman is the first choice for exactly one man.

Proof. If every woman is the first choice for exactly one man, then in the first round of the men-proposing algorithm, every woman is proposed to exactly once. So, all women get engaged, and the algorithm stops.

Similarly, if the men-proposing algorithm stops after the first round, all men get engaged in the first round. It follows that they proposed to different women.

If we wanted to count only the men’s preference profiles where each man has ranked a different woman as their first choice, we just need to ignore women’s preferences, which is achieved by dividing sequence \underline{A343475} by (n!)^{n}. This gives us the formula

n!((n − 1)!)^{n}.

We get another sequence, which is now \underline{A343694}. It counts the number of men’s preference profiles where all men prefer different women as their first choices and starts as follows:

1, 2, 48, 31104, 955514880, 2149908480000000.

We can also consider a more specific case where each man ranks a different woman as his first choice and each woman ranks a different man as her first choice. The new sequence counting such profiles, \underline{A343695}, is a square of the previous sequence, \underline{A343694}:

(n!)^{2}((n − 1)!)^{2n},

and starts as follows:

1, 4, 2304, 967458816, 913008685901414400.

We can restrict the profiles some more. Suppose not only men and women have different preferences for their first choices, but also these choices match each other. This is equivalent to saying that we have n pairs of soulmates, and this case is described in Section 4.1.1.

3.6 Tastes really differ

Suppose now, not only does each man rank a different woman first, but also each k-th ranking is distinct across all men. In other words, the men’s preferences form a Latin square when arranged in a matrix. Thus, the number of such profiles for men is described by sequence \underline{A002860} (the number of Latin squares) in the OEIS:

1, 2, 12, 576, 161280, 812851200, 61479419904000, ….

Counting in the women’s preferences, too, for every n, we need to multiply the number of possibilities for the women’s profiles, (n!)^{n}, by the corresponding term of \underline{A002860}(n). This gives us a new sequence \underline{A343696} of unique profiles for n men and n women where men’s profiles form a Latin square:

1, 8, 2592, 191102976, 4013162496000000, 113241608573209804800000000, ….

As before, the men-proposing Gale-Shapley algorithm for such profiles terminates in one round.

Now, we consider the sequence when both the men’s and women’s profiles form Latin squares. We call such profiles mutually-Latin profiles. The formula for the number of profiles is \underline{A002860}(n)^{2} because both the men and women have \underline{A002860}(n) choices for profiles. This sequence, which counts the number of preference profiles when both the men’s and women’s profiles form Latin squares, is now \underline{A343697}:

1, 4, 144, 331776, 26011238400, 660727073341440000, 3779719071732351369216000000, ….

As before, both the men-proposing and the women-proposing Gale-Shapley algorithms for such profiles terminate in one round.

3.7 Latin profiles

The Latin marriage problem is a subset of the stable marriage problem where the sum of a man’s ranking of a woman and said woman’s ranking of the man must equal n + 1. In other words, the egalitarian cost of any man-woman pair is n+1 [5]. The corresponding profiles are called Latin profiles. The Latin marriage problem is interesting because its profiles tend to produce a lot of stable matchings. Sequence \underline{A351413} in the OEIS [4] describes the number of possible stable matchings in a Latin profile, and starts as follows:

1, 2, 3, 10, 9, 48, 61, ….

This sequence counts the number of stable matchings for Latin profiles and thus provides a lower bound of the maximum number of stable matchings for any profile for a given n.

In a Latin profile, men’s preferences (and, by symmetry, women’s preferences) have to form a Latin square [5]. The number of Latin profiles is the number of Latin squares of the corresponding order \underline{A002860}(n) since a Latin square represents men’s preferences. Once the men’s preferences are set, women’s preferences are uniquely determined.

3.8 Disjoint profiles

In this section, we study a special type of profile called a disjoint profile. In such profiles, each pair of mutual rankings (i, j) occurs exactly once. In particular, each disjoint profile has exactly one pair of soulmates and one hell-pair. Such profiles correspond to entries in a disjoint-groups Sudoku [1], where in a particular place in a box, all digits are distinct across all the boxes. For example, the top-left corners of every box have distinct digits. This creates 9 additional groups to add to columns, rows, and boxes that have to contain distinct digits.

As shown in [1], there are 12 disjoint profiles for n = 2.

Proposition 3. For any n, the number of disjoint profiles does not exceed (n^{2})! and is divisible by (n!)^{2}.

Proof. There are n^{2} ways to pair a man and a woman and n^{2} ways for them to rank each other. Thus, each profile is a permutation of possible rankings distributed among possible pairs of people. The number of permutations is (n^{2})!. Not all permutations can be used, as we forbid ties in individual rankings.

In such profiles, there is exactly one pair of soulmates, whom we denote m_{1} and w_{1}. Let m_{1}’s kth choice be w_{k}, and w_{1}’s kth choice be m_{k}. The possible disjoint profiles in this scenario each correspond to (n!)^{2} different profiles overall because there are n^{2} ways to pick the soulmate pair and (n − 1)!^{2} ways to fill in the remainder of the profiles for each person in the soulmate pair. Therefore, the number of disjoint profiles is divisible by n^{2} · (n − 1)!^{2} = (n!)^{2}.

We wrote a program to calculate the number of disjoint profiles. The argument in the proof above allowed us to slightly speed up the program by assuming that the first man and the first woman rank other people in order and multiplying the resulting count of disjoint profiles by (n!)^{2}. We were able to calculate the number of disjoint profiles up to n = 4. This is now sequence \underline{A345679}, which begins

1, 12, 8784, 1031049216, ….

3.9 Joint profiles

In our paper [1], we introduced a new type of Sudoku called joint-groups or JG Sudoku. In such a Sudoku, every digit corresponds to a joint preference profile. In this new profile type, each possible mutual ranking (i, j) appears exactly n times, and once per i. We showed that a joint profile is a mutually-Latin profile; that is, both men’s and women’s preferences form Latin squares. In addition, for a mutual ranking (i, j), the value j is a function of i, thus we can write j = f(i). We call the function f the key function.

The number of joint profiles is the number of Latin squares of order n times the number of key functions, or A002860(n)n!. This follows from the fact that a joint profile is uniquely defined by a Latin square of women’s preferences and the key function, which is a permutation of n elements.

The number of joint profiles as a function of n is now sequence \underline{A344693}:

1, 4, 72, 13824, 19353600, 585252864000, 309856276316160000, ….

4 Soulmates

Recall that soulmates are a pair of people who rank each other first and must, therefore, always be married.

To begin, let’s look at the number of profiles with k pairs of soulmates, which we denote by F (k, n). For n = 2, we can manually check that 2 profiles have no soulmates, 12 profiles have 1 pair of soulmates, and 2 profiles have 2 pairs of soulmates.

We introduce another function that is useful for our calculations. Given our set of n men and n women, consider a subset of k men and k women such that no pair of men and women outside this subset has a soulmate. Then, let us denote the number of profiles for the people not in our subset as S(k, n). We have

S(0, n) = F (0, n) and S(n, n) = 1.

Lemma 4. The formula for S(k, n) is

S(k, n) = ∑_{i=0}^{n−k}(−1)^{i} · \binom{n − k}{i}^{2} · ((n − 1)!)^{2i} · i! · (n!)^{2n−2k−2i}.

Proof. First, the total number of possible profiles for people not in the subset is (n!)^{2n−2k} since there are n! ways to fill each person’s preference profile and a total of 2n − 2k people. Next, we calculate the number of profiles with at least one pair of soulmates and subtract it from the total number of profiles for people not in the subset.

There are \binom{n−k}{1}^{2} ways to pick a pair of soulmates out of n−k men and n−k women, and their profiles can be completed in ((n − 1)!)^{2} ways. Everyone else’s profiles can be completed in (n!)^{2n−2k−2} ways, but in completing these other profiles, we overcount the number of profiles with more than one pair of soulmates. Since the profiles with at least 2 pairs of soulmates are counted twice, we must subtract these \binom{n−k}{2}^{2} · 2! · ((n − 1)!)^{4} · (n!)^{2n−2k−4} profiles. But now, we undercount the profiles with three pairs of soulmates, so we add \binom{n–k}{3}^{2} · 3! · ((n–1)!)^{6} · (n!)^{2n−2k−6} profiles.

We continue in this fashion using the principle of inclusion-exclusion, and we get the complete formula:

S(k, n) = ∑_{i=0}^{n−k}(−1)^{i} · \binom{n − k}{i}^{2} · i! · ((n − 1)!)^{2i} · (n!)^{2n−2k−2i}.

Example 5. When k = n, we get S(n, n) = 1. If k = n − 1 instead, we get

S(n − 1, n) = (n!)^{2} − ((n − 1)!)^{2} = ((n − 1)!)^{2}(n^{2} − 1).

Now, we are ready to calculate our main function F (k, n).

Theorem 6. The formula for F (k, n) is

\binom{n}{k}^{2} · k! · ((n − 1)!)^{2k} · (∑_{i=0}^{n−k}(−1)^{i} · \binom{n − k}{i}^{2} · ((n − 1)!)^{2i} · i! · (n!)^{2n−2k−2i}) .

Proof. There are \binom{n}{k}^{2} ways to choose k pairs of people to be soulmates, and they can be matched to each other in k! ways. These soulmates’ profiles can be completed in ((n − 1)!)^{2k} ways. Now, all that remains is to complete the remaining 2(n − k) people’s profiles in such a way that there are no pairs of soulmates. We calculated this above as S(k, n).

Thus, the complete formula for the number of profiles with exactly k pairs of soulmates is

F (k, n) = \binom{n}{k}^{2} · k! · ((n − 1)!)^{2k} · S(k, n),

or, in the expanded form,

\binom{n}{k}^{2} · k! · ((n − 1)!)^{2k} · (∑_{i=0}^{n−k}(−1)^{i} · \binom{n − k}{i}^{2} · ((n − 1)!)^{2i} · i! · (n!)^{2n−2k−2i}) .

We evaluate the function F (k, n) for k and n below 5 in Table 1. Rows correspond to a fixed n, and columns correspond to a fixed k.

0  1  2  3  4 1  0  1 2  2  12  2 3  9984  27072  9216  384 4 28419102720 55736377344 23460876288 2418647040 40310784 ; Table 1: F (k, n).

There are several sequences here that deserve our separate attention.

4.1 Special cases

4.1.1 Love is in the air: n pairs of soulmates

Suppose we have exactly n pairs of soulmates. Our formula gives

F (n, n) = ((n − 1)!)^{2n}n!.

The number of preference profiles for n men and n women with n pairs of soulmates is now sequence \underline{A343698}. It starts as follows:

1, 2, 384, 40310784, 7608405715845120, ….

For such profiles, each person has exactly one valid partner: their soulmate. Consequently, the only stable matching is where each soulmate pair is married. For these profiles, the Gale-Shapley algorithm ends in one round, whether it is men-proposing or womenproposing. Also, the resulting stable matching has the best possible egalitarian cost, 2n.

4.1.2 n − 1 pairs of soulmates

For n − 1 pairs of soulmates, the formula becomes

((n − 1)!)^{2n+1} · n^{2} · (n^{2} − 1).

The sequence of preference profiles with n − 1 pairs of soulmates is now sequence \underline{A343699}:

0, 12, 9216, 2418647040, 913008685901414400, ….

Proposition 7. Profiles with n − 1 pairs of soulmates have exactly one stable matching. When used on these preference profiles, the men-proposing Gale-Shapley algorithm ends in j rounds, where the man in the non-soulmate pair ranks his eventual wife j.

Proof. Soulmates must be matched with each other; after that, two people are left, and they cannot avoid being together as a couple. As a result, we get a unique stable matching.

In the first round of the men-proposing Gale-Shapley algorithm, each of the n − 1 men in the n − 1 soulmate pairs propose to their first choices, and then they stay engaged for all the rounds. So, the only person left proposing is the man in the non-soulmate pair. He gets to his true partner on the j-th round, where j corresponds to his ranking of her.

4.1.3 No soulmates

To calculate the number of profiles without any pairs of soulmates, we plug in k = 0 into the formula for S(k, n). We get

\binom{n}{0}^{2} · 0! · ((n − 1)!)^{0} · (∑_{i=0}^{n−0}(−1)^{i} · \binom{n − 0}{i}^{2} · ((n − 1)!)^{2i} · i! · (n!)^{2n−20−2i}) .

Simplifying, we have

∑_{i=0}^{n}(−1)^{i} · \binom{n}{i}^{2} · ((n − 1)!)^{2i} · i! · (n!)^{2n−2i}.

The number of profiles without soulmates is now sequence \underline{A343700}, which starts as follows:

0, 2, 9984, 28419102720, 175302739963548794880, ….

Such profiles are useful for calculating M(n), which is the maximum possible number of stable matchings. Indeed, consider a profile for n men and n women with soulmates m_{1} and w_{1}. The soulmates have to be together. So, the number of different stable matchings for this profile is the same as the number of stable matchings for n − 1 men and n − 1 women when we exclude m_{1} and w_{1}. Because the sequence M(n) is strictly increasing [5], profiles with M(n) possible matchings cannot have soulmates for n > 1.

4.2 Tastes really differ

Let us go back to profiles where men’s preferences form a Latin square and see what happens if we require k pairs of soulmates. We denote the number of Latin squares of size n as L_{n}.

Theorem 8. The number of preference profiles in a stable matching problem with n men and n women, where there are exactly k pairs of soulmates and the men’s preferences form a Latin square, is

L_{n} · \binom{n}{k} · (n − 1)^{n−k} · ((n − 1)!)^{n}.

Proof. Since the preference profiles for men form a Latin square, every woman will have exactly one man who ranks her first. Therefore, if we want k pairs of soulmates, there are \binom{n}{k} ways to pick the k women for the soulmate pairs. After that, we have (n − 1)! ways to complete the profiles for every woman with a soulmate, and (n − 1)(n − 1)! ways to complete the profiles for every woman that does not have a soulmate. Since we have L_{n} ways to choose the profiles for men, this gives us a total of

L_{n} · \binom{n}{k} · ((n − 1)!)^{k} · (n − 1)^{n−k}((n − 1)!)^{n−k} = L_{n} · \binom{n}{k} · (n − 1)^{n−k} · ((n − 1)!)^{n}

preference profiles that have k pairs of soulmates.

We summarize the results for small values of n and k in Table 2. The columns correspond to different n, and rows correspond to different k. As expected, the total for a given n is sequence \underline{A343696}, which counts the number of profiles when men’s tastes really differ.

There are two special sequences to consider. The first one is the number of preference profiles where men’s tastes really differ and there are n soulmates. It corresponds to the case k = n, and the formula for it is

L_{n} · ((n − 1)!)^{n}.

1 2 3  4  5
0  0 2 768 60466176 1315033086689280
1  1 4 1152 80621568 1643791358361600
2 — 2 576 40310784 821895679180800
3 — — 96 8957952 205473919795200
4 — — —  746496  25684239974400
5 — — —  —  1284211998720
Total 1 8 2592 191102976 4013162496000000

Table 2: Distribution of preference profiles by the number of soulmate pairs when men’s tastes form a Latin square.

The number of preference profiles when men’s tastes really differ, and there are n pairs of soulmates is now sequence \underline{A344662}:

1, 2, 96, 746496, 1284211998720, 2427160677580800000000, ….

The second special sequence is the sequence counting the number of profiles where the men’s tastes really differ and there are 0 soulmates. In this case, the formula is

L_{n} · (n − 1)^{n} · ((n − 1)!)^{n}.

The sequence which counts the number of profiles where the men’s tastes really differ, with 0 soulmate pairs, is now sequence \underline{A344663}:

0, 2, 768, 60466176, 1315033086689280, 37924385587200000000000000, ….

Now we look at the case when both men’s and women’s preference profiles form Latin squares and where there are k pairs of soulmates.

Theorem 9. The number of preference profiles in a stable matching problem with n men and n women where there are exactly k pairs of soulmates, and both the men’s and women’s preference profiles form Latin squares is

\frac{L_{n}^{2}}{n!} · \binom{n}{k} · (∑_{i=0}^{n−k}(−1)^{i} \frac{(n − k)!}{i!}) .

Proof. We have L_{n} ways to choose men’s preference profiles. Now, we calculate the number of ways for women to pick their first choices.

We have \binom{n}{k} ways to pick which women will be married in pairs of soulmates. After that, we need to ensure that there are no other soulmate pairs. Among the n − k women without soulmates, the people that they rank first will be some permutation of the n−k men that are not soulmates. This is because in a Latin preference profile, all of the people who are ranked first must be different, and all of the men in a soulmate pair have already been ranked first by someone, so they cannot be ranked first again. We need these n − k men and women to not have any pairs of soulmates, so we need our permutation to be a derangement. We denote the number of derangements of size i as D_{i}.

This gives us that there are \binom{n}{k} · D_{n−k} possible ways to pick the women’s first choices. The women’s preference profiles can then be completed in \frac{L_{n}}{n!} ways. Therefore, we have \frac{L_{n}}{n!} · \binom{n}{k} · D_{n−k} preference profiles for women, which gives us a total of

\frac{L_{n}^{2}}{n!} · \binom{n}{k} · D_{n−k} = \frac{L_{n}^{2}}{n!} · \binom{n}{k} · (∑_{i=0}^{n−k}(−1)^{i} \frac{(n − k)!}{i!})

preference profiles with k soulmates.

We summarize the results for small values of n in Table 3. The columns correspond to different n and rows to different k.

1 2 3  4  5
0 0 2 48 124416 9537454080
1 1 0 72 110592 9754214400
2 * 2 0 82944 4335206400
3 * * 24 0 2167603200
4 * * * 13824  0
5 * * * * 216760320
Total 1 4 144 331776 26011238400

Table 3: Distribution of the number of soulmates when men’s and women’s tastes really differ.

Notice the zeroes on the diagonal. When men’s and women’s preferences form Latin squares, every man and woman must be ranked first exactly once; thus, there cannot be exactly n–1 pairs of soulmates. This is also reflected in the formula since if we want to have n − 1 pairs of soulmates, we would be multiplying by the number of derangements of size 1, which is 0.

As expected, the total in each column is sequence \underline{A343697}. But we also have two more sequences of note. The first sequence is the number of preference profiles when men’s and women’s tastes really differ, and there are n pairs of soulmates. It corresponds to the case k = n, and the formula simplifies to

\frac{L_{n}^{2}}{n!} .

This is the number of Latin squares multiplied by the number of Latin squares up to relabeling the digits. The sequence counting the number of preference profiles where both men’s and women’s preferences form Latin squares and there are n pairs of soulmates is now sequence \underline{A344664}, and it starts as follows:

1, 2, 24, 13824, 216760320, 917676490752000, 749944260264355430400000, ….

Additionally, in the case with no pairs of soulmates, the formula simplifies to

\frac{L_{n}^{2}}{n!} · (∑_{i=0}^{n}(−1)^{i} \frac{n!}{i!}) .

The sequence counting the number of preference profiles where both men’s and women’s preferences form Latin squares and there are no soulmates is now \underline{A344665}, and it starts as follows:

0, 2, 48, 124416, 9537454080, 243184270049280000, ….

5 Distribution for the number of stable matchings

Given a preference profile, we can calculate the total number of stable matchings.

Example 10. For n = 2, the following preference profile has two possible matchings, both of which are stable: First man: [1, 2], second man: [2, 1], first woman: [2, 1], second woman: [1, 2].

We wrote a program to calculate the number of stable matchings for every profile for n ≤ 4. The results are summarized in Table 4, where the columns correspond to different n. Row k shows how many different profiles have exactly k stable matchings. For example, there are 144 profiles for n = 4 that result in 10 distinct stable matchings.

1 2  3  4
1 1 14 34080 65867261184
2 0 2 11484 35927285472
3 0 0 1092 7303612896
4 0 0  0  861578352
5 0 0  0  111479616
6 0 0  0  3478608
7 0 0  0  581472
8 0 0  0  36432
9 0 0  0  0
10 0 0  0  144
Total 1 16 46656 110075314176

Table 4: Distribution for the number of stable matchings.

We submitted four sequences to the OEIS related to this table.

The first sequence is the number of preference profiles for 3 men and 3 women that generate n possible stable matchings, which is now sequence \underline{A344666}. It is a finite sequence of three terms:

34080, 11484, 1092.

The second sequence, now \underline{A344667}, is the number of preference profiles for 4 men and 4 women that generate n possible stable matchings. It is a finite sequence with 10 terms:

65867261184, 35927285472, 7303612896, 861578352, 111479616, 3478608, 581472, 36432, 0, 144.

We also submitted two infinite sequences. The first sequence, now sequence \underline{A344668}, corresponds to the first row. It is the number of profiles for n men and n women that result in one stable matching:

1, 14, 34080, 65867261184, ….

The second sequence, now sequence \underline{A344669}, is the number of profiles for n men and n women that result in the maximum number of stable matchings. It is the last non-zero term in each column:

1, 2, 1092, 144, ….

5.1 Soulmates

Suppose we have a pair of soulmates. Since they have to be married to each other, we can remove them from consideration and look at the other couples. It follows that the maximum number of stable matchings when there is exactly one pair of soulmates is M(n−1). Similarly, if there are k pairs of soulmates, the maximum possible number of stable matchings is M(n − k).

Example 11. We know that for n = 2, the maximum possible number of stable matchings is 2. This means for n = 3, the maximum number of stable matchings with at least one couple of soulmates is also 2.

Table 5 shows the number of profiles for a given n where there is a soulmate pair and a given number of stable matchings. The leftmost column represents the number of stable matchings, while the top row is n.

1 2  3
1 1 14 30840
2 0 0 5832
Total 1 14 36672

Table 5: Distribution for the number of stable matchings with at least one pair of soulmates.

6 Special Cases

6.1 A hell-pair and a hell-couple

Suppose we have two people that rank each other as n. We call such a pair a hell-pair, and if they end up getting married, we call them a hell-couple. Such a pair has an egalitarian cost of 2n. Additionally, replacing ranking i with n + 1 − i is a bijection that swaps soulmates with hell-pairs. Thus, the sequence counting the number of profiles with k hell-pairs is the same as the corresponding sequence with k pairs of soulmates.

Is it possible to have a hell-couple in a stable matching? Yes, it is. For example, two people who are ranked last by everyone else have to be together no matter what mutual ranking they have. This means any mutual ranking of two people in a married couple is possible.

Proposition 12. In a stable matching, having more than one hell-couple is impossible.

Proof. Suppose we have two hell-couples (m_{1}, w_{1}) and (m_{2}, w_{2}). Then (m_{1}, w_{2}) and (m_{2}, w_{1}) are rogue couples, making the matching unstable.

Suppose there is a hell-couple in a stable matching. A person in this hell situation is ready to run away with anyone who agrees. This means that in a stable matching, every other person values the member of the hell-couple of the opposite gender less than their partner. In particular, no one can rank a member of a hell-couple first.

Proposition 13. If a preference profile has a stable matching with a hell-couple, all possible stable matchings have that hell-couple.

Proof. We have a preference profile with a stable matching in which two people, man m_{1} and woman w_{1}, form a hell-couple. We know that the men-proposing Gale-Shapley algorithm is woman-pessimal, meaning that women are always matched with the man they prefer least out of all their valid partners. This means that if we were to apply the men-proposing Gale-Shapley algorithm to this preference profile, we must have w_{1} matched with m_{1} since w_{1} prefers m_{1} least, and we are given that they are valid partners. Additionally, the menproposing Gale-Shapley algorithm is man-optimal, meaning that men are always matched with the person they prefer most out of their valid partners. This means w_{1} is the only valid partner for m_{1}. Similarly, m_{1} is the only valid partner for w_{1}. Thus, they form a couple in any stable matching.

It follows that if any of a profile’s stable matching has a hell-couple, the possible number of matchings for such a profile does not exceed M(n − 1).

Consider the sequence describing the number of profiles such that there exists a stable matching with a hell-couple. We calculated this sequence, which is now sequence \underline{A344670}, by a program, and it starts as follows:

1, 4, 4536, 5113774080, ….

Consider pairs containing a preference profile and one of its stable matchings. We calculated the sequence of the number of these pairs that generate a hell-couple. That is, each profile that generates a hell-couple in a matching was counted with multiplicity equaling the number of matchings that generate this hell-couple. As per Proposition 13, the multiplicity is the number of possible stable matchings for this profile. The sequence, which is now sequence \underline{A344671}, starts as follows:

1, 4, 4608, 5317484544, ….

6.2 Outcasts

It might be that the opposite notion to soulmates is not a hell-pair but rather the outcasts. We call two people the outcasts if they are ranked n by every person of the opposite gender who is not in this pair. In a stable matching, two outcasts have to be paired with each other. This is independent of their mutual rankings, so they might be soulmates, or a hell-couple, or anything in between.

We can have at most one pair of outcasts (unless n = 2) since everyone except the two outcasts ranks them last. We want to calculate the number of profiles with at least one pair of outcasts.

Proposition 14. The number of preference profiles with n men and n women such that there exists at least one pair of outcasts is

n^{4} · ((n − 1)!)^{2n} for n ≠ 2, and 14 for n = 2.

Proof. The statement is true for n = 1. Suppose n > 2. Then we have \binom{n}{1}^{2} = n^{2} ways to pick the two outcasts, then (n!)^{2} ways to complete the outcasts’ preference profiles, and finally ((n − 1)!)^{2n−2} ways to complete everyone else’s profile. Therefore, we have

n^{2} · (n!)^{2} · ((n − 1)!)^{2n−2} = n^{4} · ((n − 1)!)^{2n}

ways to have a pair of outcasts for n > 2.

However, when n = 2, the above formula double-counts the cases with two outcast pairs. We can pick the two pairs in 2! = 2 ways, and from there, we only have 1 way to complete the preference profile, so there are 2 preference profiles that have two pairs of outcasts. Subtracting these from the previous number to avoid double-counting, we get that there are 14 preference profiles with at least one pair of outcasts for n = 2.

The formula for the number of outcasts is

n^{4} · ((n − 1)!)^{2n} for n ≠ 2, and 14 for n = 2.

The first few terms of this sequence counting the number of preference profiles that have outcasts, which is now sequence \underline{A344689}, are as follows:

1, 14, 5184, 429981696, 39627113103360000, ….

6.3 Outcast-hell pair

In order for us to have an outcast-hell pair, we need to pick two people and have everyone rank them last. Note that this means there can only be one outcast-hell pair. Moreover, in such a scenario, we can have at most one hell-pair, and the people in it must be outcasts. We can pick two people to be outcasts in \binom{n}{1}^{2} = n^{2} ways, and since everyone ranks them last, we can complete everyone’s preference profiles in ((n − 1)!)^{2n} ways, so for any n, we have n^{2} · ((n − 1)!)^{2n} preference profiles with an outcast-hell pair. Notice that, by symmetry, this is the same as the number of profiles with a pair of people such that everyone ranks them first. This is sequence \underline{A343474}:

1, 4, 576, 26873856, 1585084524134400, ….

Except for the second term, the number of outcast profiles equals n^{2} times the number of outcast-hell pair profiles. This makes sense, as the only difference is that the members of the outcast pair can rank each other any way they want.

7 Symmetries

We can relabel men, relabel women, and swap men with women without changing the number or type of matchings.

We can relabel men in n! ways. This is equivalent to fixing the first woman’s preferences to be 1, 2, 3, …, n. Because of this symmetry, the total number of profiles has to be divisible by n!.

In addition, we can relabel the women, excluding the first, in the order of the preferences of the first man. This effectively means we can shuffle the men and all the women but the first. Therefore, profiles come in groups of n!(n − 1)! profiles, which result in the same matchings but use different orderings of men and women.

7.1 Distinct men’s profiles up to relabeling

We calculate the number of different men’s profiles up to relabeling men for small values of n.

Suppose n = 1. Then, there is only one woman and only one man, so there can only be one possible set of preference profiles.

Suppose n = 2. If both men prefer the same woman, this woman can be either woman 1 or 2. If they prefer different women, we can shuffle them so that the first man prefers woman 1. So, there are 3 distinct men’s profiles in total.

We now present a general formula. There are n! possible profiles and n men, so we are choosing n preference profiles from a list of size n!, with repeats allowed, and the order in which the elements are chosen does not matter. Therefore, the total number of ways to do so is

\binom{n! + n − 1}{n}.

The sequence of the number of different men’s profiles up to relabeling men is now sequence \underline{A344690}, which starts as follows:

1, 3, 56, 17550, 225150024, 197554684517400, 16458566311785642529680, ….

We can think of this sequence as the number of n-multisets chosen from the set of all permutations of n elements.

8 The egalitarian cost distribution for small values of n

The egalitarian cost depends on a matching. Given a preference profile, having different stable matchings with different egalitarian costs is possible. Interestingly, if n = 2 or 3, and there are several stable matchings, the egalitarian cost is the same for all these matchings. This does not hold true for larger n.

Suppose n = 2. If there is one stable matching, there are 2 profiles with an egalitarian cost of 4, 8 profiles with an egalitarian cost of 5, and 4 profiles with an egalitarian cost of 6. If there are two stable matchings, there are two profiles with an egalitarian cost of 6. Thus, we have two sequences. The number of profiles such that the matching has an egalitarian cost g: 2, 8, 6. The number of possible matchings for different profiles such that the egalitarian cost is g: 2, 8, 8.

Suppose n = 3. We know that 34080 profiles have one stable matching, 11484 profiles have two matchings, and 1092 profiles have 3 matchings.

Possible egalitarian costs range from 6 to 12, inclusive. If the profile has a matching with an egalitarian cost of 6, then this matching is unique, and all the couples are soulmates. We already calculated the number of such profiles as 384. If the egalitarian cost is 7 for one of the matchings, then the matching is unique too with two soulmate couples.

We cannot have a total egalitarian cost of 18. If there was a matching of egalitarian cost 18, all couples would have to be hell-couples. In this case, any pair of people not in a couple form a rogue pair, making the matching unstable.

When a profile has multiple matchings, the matchings may have different total egalitarian costs, as seen in the following example.

Example 15. Consider a profile where the following matrices describe women’s and men’s preferences, respectively:

(\begin{matrix}3 & 1 & 2 \\ 1 & 2 & 3 \\ 1 & 2 & 3 \end{matrix}) (\begin{matrix}1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 2 & 1 \end{matrix}) .

The men-proposing Gale-Shapley algorithm ends with a total egalitarian cost of 12. The couples are man 1 and woman 1, man 2 and woman 3, and man 3 and woman 2. The women-proposing algorithm ends with a total egalitarian cost of 11. The couples are the following: woman 1 and man 3, woman 2 and man 1, and woman 3 and man 2.

Using a program, we calculated the number of preference profiles in the stable marriage problem with 3 men and 3 women such that a stable matching with egalitarian cost n exists. The egalitarian cost for stable matchings ranges from 6 to 12 inclusive:

384, 2304, 7416, 13860, 15912, 10836, 3564.

We did a similar calculation for n = 4, where the egalitarian cost ranges from 8 to 20: 40310784, 322486272, 1394454528, 4263542784, 9856161792, 17805053952, 25557163776, 29223099648, 26437927680, 18541903680, 9633334320, 3379380192, 626260608.

We combined all these numbers into one sequence \underline{A344691}: an irregular table, where T (n, k) is the number of preference profiles in the stable marriage problem with n men and n women such that there exists a stable matching with an egalitarian cost of k.

One might notice that the sum of T (3, k) over different k is 54276, larger than the total number of preference profiles, which is 46656. This result implies that there exist profiles generating matchings with different egalitarian costs. This sum is also different from the total number of matchings with different profiles: Since 34080 profiles have one stable matching, 11484 profiles have two matchings, and 1092 profiles have 3 matchings, the total number of matchings with different profiles is

1 · 34080 + 2 · 11484 + 3 · 1092 = 60324.

This suggests another sequence, which counts different matchings with a given egalitarian cost rather than different profiles. In other words, for a given egalitarian cost and profile that can generate a matching with this egalitarian cost, we count this profile with the weight equaling the number of different matchings with the given egalitarian cost.

The irregular table T′(n, k) is combined in sequence \underline{A344692}: the number of different stable matchings for different profiles for n men and n women with an egalitarian cost of k. For n = 3 and egalitarian costs ranging from 6 to 12, we get the following numbers:

384, 2304, 7488, 14592, 18072, 13104, 4380.

The total, as expected, equals 60324. For n = 4 the egalitarian cost ranges from 12 to 20 and the values of T′(n, k) are as follows: 40310784, 322486272, 1397440512, 4299816960, 10080681984, 18632540160, 27586068480, 32664453120, 30544625664, 21941452800, 11480334336, 3963617280, 707788800. It is not surprising that

T (n, 2n) = T′(n, 2n) and T (n, 2n + 1) = T′(n, 2n + 1).

If the egalitarian cost is 2n or 2n + 1, there are n or n − 1 pairs of soulmates, respectively. In both cases, there is only one stable matching per profile.

9 Acknowledgments

This project was done as part of MIT PRIMES STEP, a program that allows students in grades 6 through 9 to try research in mathematics. Tanya Khovanova is the mentor of this project. We are grateful to PRIMES STEP for this opportunity. We are grateful to Dan Eilers for pointing out that one of our references to sequences was to a wrong sequence and for providing the correct link.

References

[1] M. Borodin, E. Chen, A. Duncan, T. Khovanova, B. Litchev, J. Liu, V. Moroz, M. Qian, R. Raghavan, G. Rastogi, and M. Voigt, The stable matching problem and Sudoku, Arxiv preprint arXiv:2108.02654 [math.HO]. Available at https://arxiv.org/abs/

   2108.02654, 2021.

[2] D. Gale and L. S. Shapley, College admissions and the stability of marriage, Amer. Math. Monthly, 69 (1962), 9–15.

[3] D. Gusfield and R. W. Irving, The Stable Marriage Problem: Structure and Algorithms, MIT Press, 1989.

[4] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2023.

[5] E. G. Thurber, Concerning the maximum number of stable matchings in the stable marriage problem, Discrete Math. 248 (2002) 195–219.

2020 Mathematics Subject Classification: Primary 05A99. Keywords: stable matching problem, Gale-Shapley algorithm, preference profile.

(Concerned with sequences \underline{A000142}, \underline{A001044}, \underline{A002860}, \underline{A091868}, \underline{A185141}, \underline{A338665}, \underline{A340890}, \underline{A342573}, \underline{A343474}, \underline{A343475}, \underline{A343692}, \underline{A343693}, \underline{A343694}, \underline{A343695}, \underline{A343696}, \underline{A343697}, \underline{A343698}, \underline{A343699}, \underline{A343700}, \underline{A344662}, \underline{A344663}, \underline{A344664}, \underline{A344665}, \underline{A344666}, \underline{A344667}, \underline{A344668}, \underline{A344669}, \underline{A344670}, \underline{A344671}, \underline{A344689}, \underline{A344690}, \underline{A344691}, \underline{A344692}, \underline{A344693}, \underline{A345679}, and \underline{A351413}.)

Received January 10 2022; revised versions received September 22 2023; October 29 2023; January 15 2024. Published in Journal of Integer Sequences, January 16 2024.

Return to Journal of Integer Sequences home page.