# Polynomial Time Presolve Algorithms for Rotation-Based Models Solving the Robust Stable Matching Problem

Sulian Le Bozec-Chiffoleau, Charles Prud'Homme, Gilles Simonin

► To cite this version:

Sulian Le Bozec-Chiffoleau, Charles Prud'Homme, Gilles Simonin. Polynomial Time Presolve Algorithms for Rotation-Based Models Solving the Robust Stable Matching Problem. IJCAI 2024: Thirty-Third International Joint Conference on Artificial Intelligence, Aug 2024, Jeju, South Korea. pp.2860-2867, 10.24963/ijcai.2024/317. hal-04716981

HAL Id: hal-04716981

https://hal.science/hal-04716981v1

Submitted on 19 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Polynomial Time Presolve Algorithms for Rotation-Based Models Solving the Robust Stable Matching Problem

Sulian Le Bozec-Chiffoleau, Charles Prud'homme and Gilles Simonin

TASC, Institut Mines Telecom Atlantique, LS2N UMR 6004, Nantes, France
{sulian.le-bozec-chiffoleau, charles.prudhomme, gilles.simonin}@imt-atlantique.fr

## Abstract

The Robust Stable Matching (RSM) problem involves finding a stable matching that allows getting another stable matching within a minimum number of changes when a pair becomes forbidden. It has been shown that such a problem is NP-Hard. In this paper, we enrich the mathematical model for the RSM problem based on new theoretical properties. We derive from these properties new polynomial time pre-solving algorithms which both reduce the search space and speed up the exploration. We also extend our results to the instances of the Many-to-Many problem and give its corresponding constraint programming (CP) model. We show how the use of our algorithms improve the state-of-the-art results and make it possible to obtain proofs of optimality on large instances via the CP model.

## 1 Introduction

Over the last few decades, quantified social choice has become a key topic, as human preferences have to be considered in our optimised and automated solutions. The notion of matching under preferences is a significant example of an algorithmic approach for problems in economics (see the 2012 Nobel Prize in Economics awarded to Shapley and Roth for their work on stable allocations), finance and informatics [Roth, 1982; Gale and Shapley, 1962; Manlove, 2013]. Several practical applications of these combinatorial problems have emerged, such as kidney exchange [Biró and McDermid, 2008], college admission [Gale and Shapley, 1962] or majority voting [Dasgupta and Maskin, 2008]. The Stable Marriage problem (SM) is the most studied of these matching problems and is composed of two sets of agents (usually called men and women) having preferences over each other, and consists of finding a one-to-one stable matching. For ease of exploration of the search space, stable matchings are described by pair rotations. There are several optimality criteria over stable matchings, such as egalitarian matching or maximum popular matching, and more recently, a few works have explored the notion of robustness in stable matchings [Jacobovic, 2016;

Mai and Vazirani, 2018]. In this paper, we focus on the notion of (a,b)-supermatch introduced by [Genc, 2019] and inspired by the (a,b)-supermodels of [Ginsberg et al., 1998] and the super solutions in Constraint Programming (CP) [Hebrard et al., 2004].

An (a,b)-supermatch is a stable matching from which another stable matching can be found with less than *a* + *b* changes when *a* pairs become forbidden without changing the lists of preferences. We study the case where *a* = 1, whose optimisation problem is the Robust Stable Matching problem (RSM) and for which the decision problem is NP-complete [Genc et al., 2019]. Studies on the hospital/residents problem (HR), a one-to-many matching problem [Manlove et al., 2007], but also on popular matchings [Chisca et al., 2016] and stable matchings with cyclic preferences [Cseh et al., 2021] have shown the interest of using CP to provide generic models based on permutations in graph structures and preference properties in SM problems. This motivated us to propose a CP model as an exact method for solving the RSM problem.

In this paper, we propose a mathematical model for the RSM problem and provide pre-solving algorithms that compute an upper-bound of the optimal value and that reduce the search space and speed up its exploration. Furthermore, we generalise our results to the Many-to-Many (MM) problem instances, where both men and women can have several partners, and provide a CP model for solving the RSM problem on these extended instances.

First, we recall in Section 2 some properties of the Stable Marriage problem [Gusfield and Irving, 1989], then we present in Section 3 the RSM problem introduced by [Genc et al., 2017]. In this section, we also present our theoretical results and presolve algorithms. Then, in Section 4, we extend our results to the instances of the MM problem, and in Section 5 we present our CP model. Finally, we report in Section 6 our experiments on the RSM problem for SM, HR and MM problem instances.

## 2 Background: The Stable Marriage Problem

An instance $\mathcal{I}$ of the Stable Marriage problem (SM) [Gusfield and Irving, 1989] is a complete bipartite graph $(U \cup W, E)$ between men and women, with men having preferences over women and inversely. For a more detailed introduction to the Stable Marriage problem, see Section 1.3.4 in [Manlove,

<footnote>The Technical Appendix and the code is available via {$hal-04569962$}</footnote>
<table><caption>Table 1: An SM instance (Instance 1) from [Genc, 2019]</caption><thead><tr><th>m<sub>0</sub></th><th>0</th><th>6</th><th>5</th><th>2</th><th>4</th><th>1</th><th>3</th><th>w<sub>0</sub></th><th>2</th><th>1</th><th>6</th><th>4</th><th>5</th><th>3</th><th>0</th></tr></thead><tbody><tr><th>m<sub>1</sub></th><td>6</td><td>1</td><td>4</td><td>5</td><td>0</td><td>2</td><td>3</td><td>w<sub>1</sub></td><td>0</td><td>4</td><td>3</td><td>5</td><td>2</td><td>6</td><td>1</td></tr><tr><th>m<sub>2</sub></th><td>6</td><td>0</td><td>3</td><td>1</td><td>5</td><td>4</td><td>2</td><td>w<sub>2</sub></td><td>2</td><td>5</td><td>0</td><td>4</td><td>3</td><td>1</td><td>6</td></tr><tr><th>m<sub>3</sub></th><td>3</td><td>2</td><td>0</td><td>1</td><td>4</td><td>6</td><td>5</td><td>w<sub>3</sub></td><td>6</td><td>1</td><td>2</td><td>3</td><td>4</td><td>0</td><td>5</td></tr><tr><th>m<sub>4</sub></th><td>1</td><td>2</td><td>0</td><td>3</td><td>4</td><td>5</td><td>6</td><td>w<sub>4</sub></td><td>4</td><td>6</td><td>0</td><td>5</td><td>3</td><td>1</td><td>2</td></tr><tr><th>m<sub>5</sub></th><td>6</td><td>1</td><td>0</td><td>3</td><td>5</td><td>4</td><td>2</td><td>w<sub>5</sub></td><td>3</td><td>1</td><td>2</td><td>6</td><td>5</td><td>4</td><td>0</td></tr><tr><th>m<sub>6</sub></th><td>2</td><td>5</td><td>0</td><td>6</td><td>4</td><td>3</td><td>1</td><td>w<sub>6</sub></td><td>4</td><td>6</td><td>2</td><td>1</td><td>3</td><td>0</td><td>5</td></tr></tbody></table>

2013]. Preferences are represented by a permutation of {1, ..., n} where n is the number of men (and also women in our case) and is referred to as the size of the instance. In SM, the preference lists are complete and contain no ties (See Table 1 for an example). We usually denote a man by m and a woman by w. A stable matching is a matching that has no blocking pair.

**Definition 1 (Blocking pair SM).** Let $\mathcal{I}$ be an SM instance and M a matching. A pair $(m, w) \in E \setminus M$ is said to be a blocking pair for M iff the following conditions hold:

- m prefers w to his partner in M, or m has no partner in M.

- w prefers m to her partner in M, or w has no partner in M.

A stable matching always exists [Gale and Shapley, 1962] and the set of stable matchings $M(\mathcal{I})$ forms a distributive lattice (see Fig. 1), where $M_0$ is the man-optimal stable matching and $M_Z$ is the woman-optimal (man-pessimally) stable matching. $M_0$ and $M_Z$ can be found in $O(n^2)$ time with Gale-Shapley algorithm, for example in Instance 1, $M_0$ is defined by the pairs $\{(0, 5), (1, 4), (2, 6), (3, 3), (4, 1), (5, 0), (6, 2)\}$. The number of stable matchings is potentially exponential [Irving and Leather, 1986]; therefore it is not convenient to directly manipulate the set of stable matchings.

A rotation $\rho$ is a sequence of pairs $((m_{k_0}, w_{k_0}), ..., (m_{k_l}, w_{k_l}))$, with $l \in \mathbb{N}^*$ and $k_l \in \{1, ..., n\}$, that represents the changes to operate in a stable matching to obtain another stable matching. In a rotation, the pairs $(m_{k_i}, w_{k_i})$ are eliminated and the pairs $(m_{k_{i+1}}, w_{k_{i+1}})$ (modulo $l$) are produced (or generated). We denote $M' \setminus \rho$ the operation of eliminating a rotation $\rho$ from a stable matching $M$ (which means we apply the changes represented by $\rho$). There is a partial order $\triangleleft$ on the set of rotations $\mathcal{R}(\mathcal{I})$; indeed some rotations have to be eliminated before some others to get a stable matching. We call rotation digraph $\mathcal{D}(\mathcal{I}) = (\mathcal{V}, \mathcal{A})$ the Hasse diagram representing the partially ordered set $(\mathcal{R}(\mathcal{I}), \triangleleft)$. We denote $\mathcal{N}^{-}(\rho) = \{\rho' \in \mathcal{R}(\mathcal{I}) : \rho' \triangleleft \rho\}$ the predecessors of $\rho$, and $\mathcal{N}^{+}(\rho) = \{\rho' \in \mathcal{R}(\mathcal{I}) : \rho' \triangleleft \rho'\}$ the successors of $\rho$. We denote $\mathcal{I}(\rho)$ the set of rotations incomparable with $\rho$.

A fundamental result ([Gusfield and Irving, 1989]) is that there is a one-one correspondence between the stable matchings of $M(\mathcal{I})$ and the closed subsets of $(\mathcal{R}(\mathcal{I}), \triangleleft)$. Indeed, each stable matching $M$ is characterised by a closed subset of rotations $S_M$, and iteratively eliminating the rotations of $S_M$ (by respecting the partial order) from $M_0$ allow getting $M$, as illustrated by Fig. 1. For instance, $M_0$ is represented by the empty set, and $M_Z$ by $\mathcal{R}(\mathcal{I})$.

Another important result is that each pair is generated in at most one rotation, and eliminated in at most one rotation.

<figure><img src="image_2.png" /><figcaption>Figure 1: Stable matching lattice and rotation digraph of Instance 1</figcaption></figure>

One consequence is that the number of rotations is bounded by $n(n-1)/2$, where $n$ is the size of an SM instance. Also, the pairs that exist in at least one stable matching are called *stable pairs*, and the pairs that exist in all stable matchings are called *fixed pair*. In RSM we study the case where a pair becomes forbidden. Therefore, we denote $\mathcal{P}(\mathcal{I})$ the set of non-fixed stable pairs, which are the pairs that can be suppressed from a stable matching, that is there exists either a rotation producing it (denoted $\rho_p$) or a rotation eliminating it (denoted $\rho_e$). Then to suppress a non-fixed stable pair $(m, w)$ we can either exclude $\rho_p(m, w)$ or include $\rho_e(m, w)$ in its characterising closed subset of $\mathcal{R}(\mathcal{I})$. Note that for pairs in $M_0$ there is no rotation that produces them, and for pairs in $M_Z$ there is no rotation that eliminates them.

**Example 1.** If we are on $M_6$ (Figure 1) defined by the pairs $\{(0, 4), (1, 5), (2, 0), (3, 3), (4, 1), (5, 2), (6, 6)\}$ and we want to suppress the pair $(1, 5)$, we can either include $\rho_5$ which eliminates $(1, 5)$ or exclude $\rho_1$ which generates $(1, 5)$. However, excluding $\rho_1$ implies excluding $\rho_2$ and $\rho_4$ to maintain the closed subset property. This leads to change four additional pairs in $M_6$ (the men $\{0, 1, 2, 5, 6\}$ have a new partner), while including $\rho_5$ only leads to change one additional pair (the men $\{1, 3\}$ have a new partner).

# 3 The Robust Stable Matching Problem

## 3.1 Definitions and First Properties

In our study, we consider the following NP-HARD problem introduced by [Genc et al., 2017]:

**Name:** Robust Stable Matching (RSM)

**Instance:** An SM instance

**Objective:** Finding a (1,b)-supermatch with the smallest b.

The distance between two stable matchings corresponds to the number of pairs that differ between them:

**Definition 2 (Distance).** Let $\mathcal{I}$ be an SM instance. The distance $D$ between two stable matchings $M$ and $M'$ is defined as follows: $D(M, M') = |M \setminus M'|$. Thus $D(M, M') = D(M', M)$ and $D(M, M) = 0$.

In practice, we will manipulate the closed subsets of $\mathcal{R}(\mathcal{I})$, so we need to adapt the definition of the distance. Also, one can notice that the number of pairs that change is equal to the number of men (or women) that have a new partner, because a stable matching is a one-to-one matching:
<figure><img src="image_3.png" /><figcaption>Figure 2: Visual representation of $S_{\rho}^{U}$ and $S_{\rho}^{D}$ for a given $\rho$</figcaption></figure>

**Definition 3 (Characterised distance).** Let $\mathcal{I}$ an SM instance. Let $S_M$ and $S_{M'}$ two closed subsets of $\mathcal{R}(\mathcal{I})$. The characterised distance $d$ is defined as follows: $d(S_M, S_{M'}) = |\cup_{\rho \in S_M \Delta S_{M'}} \mathcal{H}(\rho)|$. Where $\mathcal{H}(\rho)$ is the set of men concerned by the rotation $\rho$, and $S_M \Delta S_{M'}$ is the symmetric difference between $S_M$ and $S_{M'}$.

Then, with $M$ and $M'$ two stable matchings, $S_M$ and $S_{M'}$ their characterising closed subsets of $\mathcal{R}(\mathcal{I})$, we have $D(M, M') = d(S_M, S_{M'})$. With Definition 3 we can compute the characterised distance $d$ in $\mathcal{O}(|V|)$ time. It also has a number of interesting properties that are easy to demonstrate:

**Lemma 1.** (Increasing property) Let A, B, C and D be four closed subsets of $\mathcal{R}(\mathcal{I})$. If $A \Delta B \subseteq C \Delta D$ then $d(A, B) \le d(C, D)$.

**Lemma 2.** Let $S_M, S_{M'}$ and $S$ be three closed subsets of $\mathcal{R}(\mathcal{I})$. $S_{M'} \subseteq S_M \Rightarrow d(S_{M'}, S_{M'} \cup S) \ge d(S_M, S_M \cup S)$.

**Lemma 3.** Let $S_M, S_{M'}$ and $S$ be three closed subsets of $\mathcal{R}(\mathcal{I})$. $S_M \subseteq S_{M'} \Rightarrow d(S_{M'}, S_{M'} \cap S) \ge d(S_M, S_M \cap S)$.

Now, we define some particular closed subsets required to express several important results.

**Definition 4 (UP and DOWN).** For each $\rho \in \mathcal{R}(\mathcal{I})$, the closed subsets $S_{\rho}^{U}$ and $S_{\rho}^{D}$ are defined as follows:

- $S_{\rho}^{U}$ is the maximal closed subset of rotations excluding $\rho$.

- $S_{\rho}^{D}$ is the minimal closed subset of rotations including $\rho$.

We denote $S^{\text{up}} = \{S_{\rho}^{U} : \rho \in \mathcal{R}(\mathcal{I})\}$ and $S^{\text{down}} = \{S_{\rho}^{D} : \rho \in \mathcal{R}(\mathcal{I})\}$

**Remark.** Let $\rho \in \mathcal{R}(\mathcal{I})$. $S_{\rho}^{U} = \mathcal{R}(\mathcal{I}) \setminus (\mathcal{N}^{+}(\rho) \cup \{\rho\}) = \mathcal{N}^{-}(\rho) \cup \mathcal{I}(\rho)$ and $S_{\rho}^{D} = \mathcal{N}^{-}(\rho) \cup \{\rho\}$ (See Fig. 2). Therefore, $S^{\text{up}}$ and $S^{\text{down}}$ can be computed in $\mathcal{O}(|V|^3)$ time when knowing $\mathcal{D}(\mathcal{I})$.

**Theorem 1.** Let $M \in \mathcal{M}(\mathcal{I})$ and $S_M$ be the closed subset characterising $M$. Let $(m, w) \in M$ and $\rho_p$ (resp. $\rho_e$) be the rotation that produces $(m, w)$ (resp. eliminates). Note that one of these rotations may not exist. The nearest stable matching to $M$ and not containing $(m, w)$ is characterised by either $S_{\rho_p}^U \cap S_M$ or $S_{\rho_e}^D \cup S_M$.

*Proof.* Let $S_{M'}$ be a closed subset excluding $\rho_p$, then $S_{M'} \subseteq S_{\rho_p}^U$ and so $S_M \Delta (S_M \cap S_{\rho_p}^U) \subseteq S_M \Delta S_{M'}$. Hence $d(S_M, S_M \cap S_{\rho_p}^U) \le d(S_M, S_{M'})$ by Lemma 1.

Let $S_{M''}$ be a closed subset including $\rho_e$, then $S_{\rho_e}^D \subseteq S_{M''}$ and so $S_M \Delta (S_M \cup S_{\rho_e}^D) \subseteq S_M \Delta S_{M''}$. Hence $d(S_M, S_M \cup S_{\rho_e}^D) \le d(S_M, S_{M''})$ by Lemma 1.

<figure><img src="image_4.png" /><figcaption>Figure 3: Illustration of Theorem 1</figcaption></figure>

Finally, every stable matching that does not contain $(m, w)$ is characterised by including $\rho_e$ or excluding $\rho_p$. $\square$

Theorem 1 restates an important result from [Genc et al., 2017], but relies on our definition of the sets $S^{\text{up}}$ and $S^{\text{down}}$ (Definition 4).

## 3.2 Mathematical Model

We call $\mathcal{T}(\mathcal{I})$ the set of transitional pairs, the pairs for which there is a rotation that eliminates them and a rotation that creates them. Therefore $\mathcal{T}(\mathcal{I}) = \mathcal{P}(\mathcal{I}) \setminus (M_0 \cup M_Z)$. Also, let $M_0^F = M_0 \cap \mathcal{P}(\mathcal{I})$ be the pairs of $M_0$ that can be forbidden, and $M_Z^F = M_Z \cap \mathcal{P}(\mathcal{I})$ the pairs of $M_Z$ that can be forbidden. Thus $\mathcal{P}(\mathcal{I})$ is the disjoint union of $M_0^F$, $M_Z^F$ and $\mathcal{T}(\mathcal{I})$.

According to Theorem 1, the cost of suppressing a pair $(m, w)$ from a stable matching $M$ is defined as follows:

$$b_M(m, w) = \begin{cases} d(S_M, S_{\rho_e}^D \cup S_M) & \text{if } (m, w) \in M_0^F \\ d(S_M, S_{\rho_p}^U \cap S_M) & \text{if } (m, w) \in M_Z^F \\ \min(d(S_M, S_{\rho_p}^U \cap S_M), d(S_M, S_{\rho_e}^D \cup S_M)) & \text{if } (m, w) \in \mathcal{T}(\mathcal{I}) \end{cases}$$

where $S_M$ is the closed subset of rotations characterising $M$.

**Remark.** Let $\mathcal{I}$ be an SM instance and $M$ a stable matching. $\forall (m, w) \in \mathcal{P}(\mathcal{I}), (m, w) \notin M \Rightarrow b_M(m, w) = 0$.

Then, the robust score, or robust cost, of a stable matching $M$ is defined as follows:

$$b(M) = \max\{b_M(m, w) : (m, w) \in \mathcal{P}(\mathcal{I})\} - 1$$

Finally, the RSM problem consists in finding a stable matching $M^*$ that minimises the robust cost:

$$M^* = \underset{M \in \mathcal{M}(\mathcal{I})}{\operatorname{argmin}} \{b(M) : M \in \mathcal{M}(\mathcal{I})\}$$

And the optimal value is $b^* = b(M^*)$.

## 3.3 Upper-Bound

Since we are studying a minimisation problem, we can evaluate the robust score of each stable matching to obtain an upper-bound on the optimal value. With $S^{\text{up}}$ and $S^{\text{down}}$ we have access to many closed subsets for evaluation.

However, we only want to select a few number of stable matchings to get an upper-bound faster. To do so, we choose to evaluate $M_0$, $M_Z$ and a median stable matching. Intuitively, a median stable matching is located in the "middle" of the partial order on $\mathcal{M}(\mathcal{I})$. So with $M_0$ which is at the "beginning" and $M_Z$ at the "end", we roughly cover $\mathcal{M}(\mathcal{I})$. Here are two existing theorems about median stable matchings, slightly reformulated.
**Theorem 2** ([Teo and Sethuraman, 1998]). Let $\mathcal{T} \subseteq \mathcal{M}(\mathcal{I})$ and $t = |\mathcal{T}|$. Let $j \in \{1, ..., t\}$ and let $\alpha_{j,\mathcal{T}}$ denote the set of pairs obtained by assigning each man to his $j^{th}$ preferred woman in the multiset of all women he is matched to in the stable matchings of $\mathcal{T}$. Then $\alpha_{j,\mathcal{T}}$ is a stable matching.

When $t$ is odd, $\alpha_{\frac{t+1}{2},\mathcal{T}}$ is called the unique median stable matching of $\mathcal{T}$. When $t$ is even, $\alpha_{\frac{t}{2},\mathcal{T}}$ (resp. $\alpha_{\frac{t}{2}+1,\mathcal{T}}$) is called the lower (resp. upper) median stable matching of $\mathcal{T}$.

**Theorem 3** ([Cheng, 2010]). Let $\mathcal{T} \subseteq \mathcal{M}(\mathcal{I})$ and $t = |\mathcal{T}|$. For each $\rho \in \mathcal{R}(\mathcal{I})$, let $\bar{n}_{\rho,\mathcal{T}} = |\{M \in \mathcal{T} : \rho \notin S_M\}|$. Then $\forall j \in \{1, ..., t\}, \bar{R}_{j,\mathcal{T}}(\mathcal{I}) = \{\rho \in \mathcal{R}(\mathcal{I}) : \bar{n}_{\rho,\mathcal{T}} < j\}$ is a closed subset and characterises $\alpha_{j,\mathcal{T}}$.

Theorem 3 allows to find a median stable matching for a subset of $\mathcal{M}(\mathcal{I})$ by analysing the rotations. Let $S_{down}^{up}$ be the multiset bringing together the closed subsets in $S^{up}$ and $S^{down}$ (with possible repetitions). Let $\mathcal{T}_{down}^{up}$ denote the multiset of stable matchings characterised by the closed subsets of $S^{up}$. We want to easily find the lower median stable matching of $\mathcal{T}_{down}^{up}$, which we denote $M_{down}^{up}$.

**Theorem 4.** $M_{down}^{up}$ is characterised by $S_{M_{down}^{up}} = \{\rho \in \mathcal{R}(\mathcal{I}) : |S_{\rho}^{U}| + |S_{\rho}^{D}| < |\mathcal{R}(\mathcal{I})|\}$.

*Proof.* Let $\rho \in \mathcal{R}(\mathcal{I})$. As a reminder, for each $\rho' \in \mathcal{R}(\mathcal{I})$, $S_{\rho'}^{U} = \mathcal{N}^{-}(\rho') \cup \mathcal{I}(\rho')$ and $S_{\rho'}^{D} = \mathcal{N}^{-}(\rho') \cup \{\rho'\}$.

$\mathcal{R}(\mathcal{I})$ is the disjoint union of $\mathcal{N}^{+}(\rho)$, $\mathcal{N}^{-}(\rho)$, $\mathcal{I}(\rho)$ and $\{\rho\}$, so we analyse each case to count the number of closed subsets in $S_{down}^{up}$ that do not contain $\rho$ (see Fig. 4).

- Let $\rho^{+} \in \mathcal{N}^{+}(\rho)$, $\rho \in S_{\rho^{+}}^{U}$ and $\rho \in S_{\rho^{+}}^{D}$.

- Let $\rho^{-} \in \mathcal{N}^{-}(\rho)$, $\rho \notin S_{\rho^{-}}^{U}$ and $\rho \notin S_{\rho^{-}}^{D}$.

- Let $\rho^{i} \in \mathcal{I}(\rho)$, $\rho \in S_{\rho^{i}}^{U}$ and $\rho \notin S_{\rho^{i}}^{D}$.

- Also, $\rho \notin S_{\rho}^{U}$ and $\rho \in S_{\rho}^{D}$.

We deduce that $\bar{n}_{\rho,\mathcal{T}_{down}^{up}} = 2 \times |\mathcal{N}^{-}(\rho)| + |\mathcal{I}(\rho)| + 1 = |S_{\rho}^{U}| + |S_{\rho}^{D}|$. Finally, $|\mathcal{T}_{down}^{up}| = 2 \times |\mathcal{R}(\mathcal{I})|$. So $S_{M_{down}^{up}} = \bar{R}_{\frac{t}{2},\mathcal{T}_{down}^{up}}$ (with $t = |\mathcal{T}_{down}^{up}|$), and by Theorem 3 it characterises $\alpha_{\frac{t}{2},\mathcal{T}_{down}^{up}}$ (which is $M_{down}^{up}$). □

Theorem 4 allows to find $S_{M_{down}^{up}}$ in $\mathcal{O}(|\mathcal{V}|)$ time when $S^{up}$ and $S^{down}$ are already known. Thus we can easily compute the robust score of $M_0$, $M_Z$ and $M_{down}^{up}$, and provide an upper-bound $\bar{b}$ of the optimal value $b^*$.

<figure><img src="image_5.png" /><figcaption>Figure 4: Visual representation of $\rho^{+}$, $\rho^{-}$ and $\rho^{i}$</figcaption></figure>

## 3.4 Computing the Robust Score Faster

Evaluating the robust score of a stable matching consists in finding the highest cost of the suppression of a pair, which implies calculating several distance values as we can see in the mathematical formulation (Section 3.2). Thus, computing the robust score can be done in $\mathcal{O}(n \times |\mathcal{V}|)$ time. However, we show that some pairs may always be more expensive to suppress than others. Therefore we might not need to calculate all the distances to get the robust cost. The theorems below explain in which case we can safely ignore some rotations or pairs. As a reminder, the only way to suppress a pair $(m_0, w_0) \in M_0^F$ is by including the rotation $\rho_0$ eliminating this pair. And the only way to suppress a pair $(m_Z, w_Z) \in M_Z^F$ is by excluding the rotation $\rho_Z$ producing this pair. Also, $S_M$ denotes the closed subset of rotations characterising the stable matching $M$.

**Theorem 5.** Let $\mathcal{I}$ be an SM instance.

$$ \forall(m_0, w_0) \in M_0^F, \forall M \in \mathcal{M}(\mathcal{I}), \forall(m, w) \in \mathcal{P}(\mathcal{I}), \\ \rho_e(m, w) \triangleleft \rho_0 \implies b_M(m, w) \leq b_M(m_0, w_0) $$

where $\rho_0$ is the rotation eliminating $(m_0, w_0)$.

*Proof.* We assume that $\rho_e(m, w) \triangleleft \rho_0$, then $S_{\rho_e(m,w)}^D \subseteq S_{\rho_0}^D$ and so $S_M \Delta(S_{\rho_e(m,w)}^D \cup S_M) \subseteq S_M \Delta(S_{\rho_0}^D \cup S_M)$. Hence $d(S_M, S_{\rho_e(m,w)}^D \cup S_M) \leq d(S_M, S_{\rho_0}^D \cup S_M)$ by Lemma 1, thus $b_M(m, w) \leq b_M(m_0, w_0)$. □

**Theorem 6.** Let $\mathcal{I}$ be an SM instance.

$$ \forall(m_Z, w_Z) \in M_Z^F, \forall M \in \mathcal{M}(\mathcal{I}), \forall(m, w) \in \mathcal{P}(\mathcal{I}), \\ \rho_Z \triangleleft \rho_p(m, w) \implies b_M(m, w) \leq b_M(m_Z, w_Z) $$

where $\rho_Z$ is the rotation producing $(m_Z, w_Z)$.

*Proof.* We assume that $\rho_Z \triangleleft \rho_p(m, w)$, then $S_{\rho_Z}^U \subseteq S_{\rho_p(m,w)}^U$ and so $S_M \Delta(S_{\rho_p(m,w)}^U \cap S_M) \subseteq S_M \Delta(S_{\rho_Z}^U \cap S_M)$. Hence $d(S_M, S_{\rho_p(m,w)}^U \cap S_M) \leq d(S_M, S_{\rho_Z}^U \cap S_M)$ by Lemma 1, thus $b_M(m, w) \leq b_M(m_Z, w_Z)$. □

**Theorem 7.** Let $\mathcal{I}$ be an SM instance.

$\forall(m, w) \in \mathcal{T}(\mathcal{I}), \forall M \in \mathcal{M}(\mathcal{I}), \forall(m', w') \in \mathcal{T}(\mathcal{I})$ such that $\rho_p \triangleleft \rho_p(m', w')$ and $\rho_e(m', w') \triangleleft \rho_e$, we got $b_M(m', w') \leq b_M(m, w)$ where $\rho_p$ is the rotation producing $(m, w)$, and $\rho_e$ is the rotation eliminating $(m, w)$.

*Proof.* In the proofs of Theorems 5 and 6 we have shown that $d(S_M, S_{\rho_e(m',w')}^D \cup S_M) \leq d(S_M, S_{\rho_e}^D \cup S_M)$ and $d(S_M, S_{\rho_p(m',w')}^U \cap S_M) \leq d(S_M, S_{\rho_p}^U \cap S_M)$. Therefore $b_M(m', w') \leq b_M(m, w)$. □

Based on Theorems 5, 6 and 7, Algorithm 1 computes a reduced set $\mathcal{R}^{up}$ (resp. $\mathcal{R}^{down}$) of rotations we need to exclude (resp. include), as well as a reduced set $\mathcal{P}_r$ of pairs we need to consider to compute the robust score of any stable matching.

Algorithm 1 starts by initialising the different variables in lines 1-4. Then, the loop at line 5 applies Theorem 5 to reduce $\mathcal{R}^{down}$, the one at line 8 applies Theorem 6 to reduce $\mathcal{R}^{up}$, and the one at line 11 applies Theorem 7 to reduce $\mathcal{P}_r$. The loop at line 16 checks if all up (resp. down) rotations generate (resp. eliminate) an irrelevant transitive pair, and if that is the case then it suppresses this rotation from $\mathcal{R}^{up}$ (resp. $\mathcal{R}^{down}$).
**Algorithm 1 Relevant pairs and rotations**

**Require:** An instance $\mathcal{I}$ of SM, $\mathcal{D}(\mathcal{I})$, $S^{\text{up}}$ and $S^{\text{down}}$

**Ensure:** Creating the sets $\mathcal{R}^{\text{up}}$, $\mathcal{R}^{\text{down}}$ and $\mathcal{P}_r$

1: $\mathcal{R}^{\text{up}}, \mathcal{R}^{\text{down}}, \mathcal{P}_r \leftarrow \mathcal{R}(\mathcal{I}), \mathcal{R}(\mathcal{I}), \mathcal{P}(\mathcal{I})$

2: **for** $\rho \in \mathcal{R}(\mathcal{I})$ **do**

3: $H_{\rho}^{\text{up}} \leftarrow |\mathcal{H}(\rho)|$

4: $H_{\rho}^{\text{down}} \leftarrow |\mathcal{H}(\rho)|$

5: **for** $(m, w) \in M_0^F$ **do**

6: **for** $\rho \in \mathcal{N}^-(\rho_e(m, w))$ **do**

7: $\mathcal{R}^{\text{down}} \leftarrow \mathcal{R}^{\text{down}} \setminus \{\rho\}$

8: **for** $(m, w) \in M_Z^F$ **do**

9: **for** $\rho \in \mathcal{N}^+(\rho_p(m, w))$ **do**

10: $\mathcal{R}^{\text{up}} \leftarrow \mathcal{R}^{\text{up}} \setminus \{\rho\}$

11: **for** $((m, w), (m', w')) \in \mathcal{T}(\mathcal{I})^2$ **do**

12: **if** $\rho_p(m, w) \triangleleft \rho_p(m', w')$ **and** $\rho_e(m', w') \triangleleft \rho_e(m, w)$ **then**

13: $\mathcal{P}_r \leftarrow \mathcal{P}_r \setminus (m', w')$

14: $H_{\rho_p(m', w')}^{\text{up}} \leftarrow H_{\rho_p(m', w')}^{\text{up}} - 1$

15: $H_{\rho_e(m', w')}^{\text{down}} \leftarrow H_{\rho_e(m', w')}^{\text{down}} - 1$

16: **for** $\rho \in \mathcal{R}(\mathcal{I})$ **do**

17: **if** $H_{\rho}^{\text{up}} = 0$ **then**

18: $\mathcal{R}^{\text{up}} \leftarrow \mathcal{R}^{\text{up}} \setminus \{\rho\}$

19: **if** $H_{\rho}^{\text{down}} = 0$ **then**

20: $\mathcal{R}^{\text{down}} \leftarrow \mathcal{R}^{\text{down}} \setminus \{\rho\}$

21: **for** $(m, w) \in \mathcal{P}(\mathcal{I})$ **do**

22: **if** $\rho_p(m, w) \notin \mathcal{R}^{\text{up}}$ **or** $\rho_e(m, w) \notin \mathcal{R}^{\text{down}}$ **then**

23: $\mathcal{P}_r \leftarrow \mathcal{P}_r \setminus (m, w)$

**return** $\mathcal{R}^{\text{up}}, \mathcal{R}^{\text{down}}, \mathcal{P}_r$

Finally, the loop at line 21 checks $\mathcal{R}^{\text{up}}$ and $\mathcal{R}^{\text{down}}$ to update $\mathcal{P}_r$. Since $\mathcal{T}(\mathcal{I})$ has a size bounded by $n^2$, Algorithm 1 has a time complexity of $\mathcal{O}(n^4)$ in the worst case.

**3.5 Reducing the Size of the Search Space**

The main difficulty of the stable marriage problems lies in the potentially exponential number of stable matchings [Irving and Leather, 1986], so that the search space can be very vast. By knowing an upper-bound $\bar{b}$ of the optimal value $b^*$ of the RSM problem, we show that it is possible to reduce the size of the search space. Indeed, in the theorems below we show that some rotations are present in every optimal solution, and some others in none of them.

**Theorem 8.** Let $S_{M^*}$ be the closed subset of rotations characterising an optimal solution $M^*$, and let $\bar{b}$ be an upper-bound of $b^*$. Let $\rho \in \mathcal{R}(\mathcal{I})$ and $\rho_0$ be the rotation eliminating a pair $(m_0, w_0) \in M_0^F$.

$$ \text{Then, } d(S_{\rho}^{U}, S_{\rho}^{U} \cup S_{\rho_0}^{D}) > \bar{b} + 1 \implies \rho \in S_{M^*} $$

*Proof.* Let us prove the contraposition. We assume that $\rho \notin S_{M^*}$, then $S_{M^*} \subseteq S_{\rho}^U$. Firstly, by definition $b_{M^*}(m_0, w_0) = d(S_{M^*}, S_{\rho_0}^D)$, and then $b^* \ge d(S_{M^*}, S_{M^*} \cup S_{\rho_0}^D) - 1$. Secondly, according to Lemma 2, we have $d(S_{M^*}, S_{M^*} \cup S_{\rho_0}^D) \ge d(S_{\rho}^D, S_{\rho}^D \cap S_{\rho_0}^U)$. Therefore we deduce that $d(S_{\rho}^D, S_{\rho}^D \cap S_{\rho_0}^U) \le b^* + 1$ and so $d(S_{\rho}^D, S_{\rho}^D \cap S_{\rho_0}^U) \le \bar{b} + 1$.

**Algorithm 2 Lower and upper-bound of $S_{M^*}$**

**Require:** An instance $\mathcal{I}$ of SM, $\mathcal{D}(\mathcal{I})$, $S^{\text{up}}$ and $S^{\text{down}}$

**Ensure:** Getting $S_{LB}$ and $S_{UB}$

1: $S_{LB}, S_{UB} \leftarrow \emptyset, \mathcal{R}(\mathcal{I})$

2: **for** $(m, w) \in M_0^F: \rho_e(m, w) \in \mathcal{R}^{\text{down}}$ **do**

3: **for** $\rho \in S_{\rho_e(m, w)}^D$ **do**

4: **if** $d(S_{\rho}^U, S_{\rho}^U \cup S_{\rho_e(m, w)}^D) > \bar{b} + 1$ **then**

5: $S_{LB} \leftarrow S_{LB} \cup \{\rho\}$

6: **for** $(m, w) \in M_Z^F: \rho_p(m, w) \in \mathcal{R}^{\text{up}}$ **do**

7: **for** $\rho \in \mathcal{R}(\mathcal{I}) \setminus S_{\rho_p(m, w)}^U$ **do**

8: **if** $d(S_{\rho}^D, S_{\rho}^D \cap S_{\rho_p(m, w)}^U) > \bar{b} + 1$ **then**

9: $S_{UB} \leftarrow S_{UB} \setminus \{\rho\}$

**return** $S_{LB}, S_{UB}$

$$ d(S_{\rho}^{U}, S_{\rho}^{U} \cup S_{\rho_0}^{D}) \le b^* + 1 \text{ and so } d(S_{\rho}^{U}, S_{\rho}^{U} \cup S_{\rho_0}^{D}) \le \bar{b} + 1. \quad \square $$

**Theorem 9.** Let $S_{M^*}$ be the closed subset of rotations characterising an optimal solution $M^*$, and let $\bar{b}$ be an upper-bound of $b^*$. Let $\rho \in \mathcal{R}(\mathcal{I})$ and $\rho_Z$ be the rotation producing a pair $(m_Z, w_Z) \in M_Z^F$. Then, $d(S_{\rho}^D, S_{\rho}^D \cap S_{\rho_Z}^U) > \bar{b} + 1 \implies \rho \notin S_{M^*}$.

*Proof.* Let us prove the contraposition. We assume that $\rho \in S_{M^*}$, then $S_{\rho}^D \subseteq S_{M^*}$. Firstly, by definition $b_{M^*}(m_Z, w_Z) = d(S_{M^*}, S_{M^*} \cap S_{\rho_Z}^U)$, and then $b^* \ge d(S_{M^*}, S_{M^*} \cap S_{\rho_Z}^U) - 1$. Secondly, according to Lemma 3, we have $d(S_{M^*}, S_{M^*} \cap S_{\rho_Z}^U) \ge d(S_{\rho}^D, S_{\rho}^D \cap S_{\rho_Z}^U)$. Therefore we deduce that $d(S_{\rho}^D, S_{\rho}^D \cap S_{\rho_Z}^U) \le b^* + 1$ and so $d(S_{\rho}^D, S_{\rho}^D \cap S_{\rho_Z}^U) \le \bar{b} + 1$.

Based on Theorems 8 and 9, Algorithm 2 returns a lower-bound $S_{LB}$ and an upper-bound $S_{UB}$ on the closed subset $S_{M^*}$ characterising an optimal solution $M^*$.

**Remark.** Let $(m, w) \in M_0^F$ and $\rho \in \mathcal{R}(\mathcal{I})$, if $\rho \notin S_{\rho_e(m, w)}^D$ then $d(S_{\rho}^U, S_{\rho}^U \cup S_{\rho_e(m, w)}^D) = 0$.

Let $(m, w) \in M_Z^F$ and $\rho \in \mathcal{R}(\mathcal{I})$, if $\rho \in S_{\rho_p(m, w)}^U$ then $d(S_{\rho}^D, S_{\rho}^D \cap S_{\rho_p(m, w)}^U) = 0$.

Algorithm 2 starts by initialising $S_{LB}$ and $S_{UB}$, then it consists of two main loops: one to increase $S_{LB}$ and the other to decrease $S_{UB}$. The first one is based on Theorem 8 to add elements to $S_{LB}$, and on Theorem 5 to compute only the relevant distances and quicken the algorithm. Similarly, the second main loop is based on Theorems 9 and 6 to rapidly suppress elements from $S_{UB}$. Also, since the distance is computed in $\mathcal{O}(|V|^2)$ time, Algorithm 2 has a time complexity of $\mathcal{O}(n \times |V|^2)$ in the worst case.

Algorithms 1 and 2 have shown their efficiency as we explain in Section 6. But in the next Section, we prove that our results also hold for a larger family of instances.
# 4 Generalisation to Many-to-Many Instances

## 4.1 The Many-to-Many Problem (MM)

As for the SM problem, an instance of the Many-to-Many problem is a complete bipartite graph $(U \cup W, E)$ between men and women, with men having preferences over women and inversely. However, in the MM problem, both men and women can have several partners up to a maximum number called capacity. Each individual can have his own capacity. Similarly to the SM problem, the MM problem consists in finding a stable matching, which is a matching that has no blocking pair. Yet the definition of a blocking pair is slightly different:

**Definition 5 (Blocking pair MM).** Let $\mathcal{I}$ be an MM instance and M a matching. A pair $(m, w) \in E \setminus M$ is said to be a blocking pair for M iff the following conditions hold:
– *m* prefers *w* to his least preferred partner in M, or *m* has fewer partners in M than his capacity.

– *w* prefers *m* to her least preferred partner in M, or *w* has fewer partners in M than her capacity.

The MM problem generalises the SM problem but also the HR problem, where only one side can have several partners, and some works [Baïou and Balinski, 2000; Bansal et al., 2007; Eirinakis et al., 2012] have shown that a lot of results on SM also hold for MM. We reuse the same notations as for the SM problem that we recall now.

The set of stable matchings $\mathcal{M}(\mathcal{I})$ forms a lattice, with the existence of $M_0$ and $M_Z$. The partially ordered set of rotations (also called meta-rotations) $(\mathcal{R}(\mathcal{I}), \triangleleft)$ exists too, and the stable matchings are characterised by the closed subsets of rotations. Each rotation generating a pair is a predecessor of the rotation eliminating it. Each pair has at most one rotation generating it and one rotation eliminating it. Each rotation generates as much pairs as it eliminates. Given two incomparable rotations, the sets of pairs they generate or eliminate are disjoint. These papers provide algorithms to get $M_0$, $M_Z$ and the rotation digraph $\mathcal{D}(\mathcal{I}) = (\mathcal{V}, \mathcal{A})$ in $\mathcal{O}(n^4)$ time that we will reuse in Section 6.

## 4.2 Robustness in MM

The distance between two stable matchings is the same as for SM (Definition 2), and we can extend it to the MM instances. However, we have to consider a generalised version of the characterised distance in SM (Definition 3):

**Definition 6 (Generalised characterised distance).** Let $\mathcal{I}$ be an MM instance. Let $S_M$ and $S_{M'}$ two closed subsets of $\mathcal{R}(\mathcal{I})$. The generalised characterised distance $d_G$ is defined as follows: $d_G(S_M, S_{M'}) = |\bigcup_{\rho \in S_M \Delta S_{M'}} \mathcal{G}(\rho) \setminus \bigcup_{\rho \in S_M \Delta S_{M'}} \mathcal{E}(\rho)|$, where $\mathcal{G}(\rho)$ (resp. $\mathcal{E}(\rho)$) is the set of pairs generated (resp. eliminated) by the meta-rotation $\rho$.

This distance is the number of newly generated and not eliminated pairs in the process of going from $S_M$ to $S_{M'}$ (and inversely).

**Remark.** $D(M, M') = d_G(S_M, S_{M'})$

**Lemma 4.** (Increasing property) Let A, B, C and D be four closed subsets of $\mathcal{R}(\mathcal{I})$. If $A \Delta B \subseteq C \Delta D$ then $d_G(A, B) \le d_G(C, D)$.

*Proof.* As for SM instances, the more rotations we apply the more pairs we change. Due to the lack of space, the complete proof is detailed in the Technical Appendix. ☐

All the theoretical results and algorithms obtained for the RSM problem on SM rely on the properties of the rotation digraph and the increasing property (Lemma 1). Since the MM instances also have a meta-rotation digraph with the same properties, and the generalised characterised distance $d_G$ verifies the increasing property too (Lemma 4), we can affirm that the theoretical results and algorithms obtained for the RSM problem on SM instances also hold for MM instances. Note that for the complexity of Algorithms 1 and 2 we have to replace *n* by $n \times c$, where *c* is the highest capacity.

# 5 A Constraint Programming Model

We present hereafter a CP model based on the set variables [Gervet, 1995; Gervet, 1997], and exploiting the algorithms 1 and 2 to solve the RSM problem extended to the MM instances. Before describing the model, we need to define the following two constraints. First, $\text{CLOSED SUBSET}(S, X)$ ensures that $S$ is a closed subset of the partially ordered space $X$. Then, $\text{INDEX UNION}(\mathcal{I}, \mathcal{E}, (R_i)_{i \in \mathcal{J}})$ ensures that $\mathcal{E} = \bigcup_{i \in \mathcal{I}} R_i$ with $\mathcal{I} \subseteq \mathcal{J}$. More details on these two constraints are given in the Technical Appendix.

The Model 1 is a formulation of the RSM problem. The set variable $S_M$ characterises the robust stable matching we are looking for. $S_M$ is bounded by $S_{LB}$ and $S_{UB}$ (2). (3) ensures that $S_M$ is a closed subset of $\mathcal{R}(\mathcal{I})$ represented by its Hasse diagram $\mathcal{D}(\mathcal{I})$. The variables with up as exponent, resp. down, are used to compute the cost of excluding, resp. including, a given rotation. The set variable $\Delta_{\rho}^{up}$, resp. $\Delta_{\rho}^{down}$, corresponds to the set of rotations that differs between $S_M$ and the nearest closed subset to $S_M$ excluding $\rho$ (4), resp. including $\rho$ (5). The set variable $\mathcal{G}_{\rho}^{up}$, resp. $\mathcal{G}_{\rho}^{down}$, represents the set of pairs generated by the rotations in $\Delta_{\rho}^{up}$ (6), resp. $\Delta_{\rho}^{down}$ (7). The set variable $\mathcal{E}_{\rho}^{up}$, resp. $\mathcal{E}_{\rho}^{down}$, represents the set of pairs eliminated by the rotations in $\Delta_{\rho}^{up}$ (8), resp. $\Delta_{\rho}^{down}$ (9). The integer variable $D_{\rho}^{up}$, resp. $D_{\rho}^{down}$, counts the number of pairs in $\mathcal{G}_{\rho}^{up} \setminus \mathcal{E}_{\rho}^{up}$ (10), resp. $\mathcal{G}_{\rho}^{down} \setminus \mathcal{E}_{\rho}^{down}$ (11). The $b_M$ integer variables link a pair to the rotations that generate and eliminate it. The integer variable $b_M(\tau)$ represents the cost of forbidding a pair $\tau = (m, w)$ in $M$ (12). Finally, the objective is to minimise the highest cost (1). Without our preprocessing algorithms, Model 1 uses the initial values of $S_{LB}$, $S_{UB}$, $\mathcal{R}^{up}$, $\mathcal{R}^{down}$ and $P_r$ (Algorithm 1, Line 1 and Algorithm 2, Line 1).

Note that our branching strategy consists in branching only on $S_M$. Indeed, if $S_M$ is completely instantiated, all the other variables are fixed during propagation.

# 6 Experimental Results

In this section we conduct experiments on two models: a local search algorithm with random restarts LS from [Genc, 2019] (which is the state-of-the-art method for solving the RSM problem) implemented in Java (openjdk version 21.0.1) and generalised to the MM instances, and the CP model CP
### Model 1 A model of the RSM problem.

$$ \text{Minimise } \max\{b_M(m, w) : (m, w) \in \mathcal{P}_r\} - 1 \quad (1) $$

$$ \text{s.t.:} \quad S_{LB} \subseteq S_M \subseteq S_{UB} \quad (2) $$

$$ \text{CLOSED SUBSET}(S_M, \mathcal{D}(\mathcal{I})) \quad (3) $$

$$ \Delta_{\rho}^{up} = S_M \setminus S_{\rho}^{U}, \quad \forall \rho \in \mathcal{R}^{up} \quad (4) $$

$$ \Delta_{\rho}^{down} = S_{\rho}^{D} \setminus S_M, \quad \forall \rho \in \mathcal{R}^{down} \quad (5) $$

$$ \text{INDEX UNION}(\Delta_{\rho}^{up}, \mathcal{G}_{\rho}^{up}, (\mathcal{G}(\rho))_{\rho \in \mathcal{R}(\mathcal{I})}), \quad \forall \rho \in \mathcal{R}^{up} \quad (6) $$

$$ \text{INDEX UNION}(\Delta_{\rho}^{down}, \mathcal{G}_{\rho}^{down}, (\mathcal{G}(\rho))_{\rho \in \mathcal{R}(\mathcal{I})}), \forall \rho \in \mathcal{R}^{down} \quad (7) $$

$$ \text{INDEX UNION}(\Delta_{\rho}^{up}, \mathcal{E}_{\rho}^{up}, (\mathcal{E}(\rho))_{\rho \in \mathcal{R}(\mathcal{I})}), \quad \forall \rho \in \mathcal{R}^{up} \quad (8) $$

$$ \text{INDEX UNION}(\Delta_{\rho}^{down}, \mathcal{E}_{\rho}^{down}, (\mathcal{E}(\rho))_{\rho \in \mathcal{R}(\mathcal{I})}), \forall \rho \in \mathcal{R}^{down} \quad (9) $$

$$ D_{\rho}^{up} = |\mathcal{G}_{\rho}^{up} \setminus \mathcal{E}_{\rho}^{up}|, \quad \forall \rho \in \mathcal{R}^{up} \quad (10) $$

$$ D_{\rho}^{down} = |\mathcal{G}_{\rho}^{down} \setminus \mathcal{E}_{\rho}^{down}|, \quad \forall \rho \in \mathcal{R}^{down} \quad (11) $$

$$ b_M(\tau) = \begin{cases} D_{\rho_e(\tau)}^{down} & \forall \tau \in M_0^F \cap \mathcal{P}_r \\ D_{\rho_p(\tau)}^{up} & \forall \tau \in M_2^F \cap \mathcal{P}_r \\ \min(D_{\rho_p(\tau)}^{up}, D_{\rho_e(\tau)}^{down}) & \forall \tau \in \mathcal{T}(\mathcal{I}) \cap \mathcal{P}_r \end{cases} \quad (12) $$

we provided in this paper and solved with Choco-solver [Prud'homme and Fages, 2022]. For both models, we consider two configurations: one where we only run PP1 (the preprocessing step allowing getting $M_0$, $M_2$ and $\mathcal{D}(\mathcal{I})$, that every rotation-based model has in common), and one where we run PP1 and our preprocessing step PP2 which consists of getting $\bar{b}$ and running Algorithms 1 and 2. We consider instances of SM (men and women have at most one partner), HR (only men can have several partners) and MM (both men and women can have several partners). For each instance size, we randomly generate 10 instances following a uniform distribution and report the mean statistics. This is the way instances of SM, HR and MM are usually generated in the literature [Genc, 2019; Manlove et al., 2007; Eirinakis et al., 2012]. We use an Intel(R) Xeon(R) Gold 6230 CPU with 2.10GHz and 3Go allocated RAM, and under Ubuntu 20.04.4 LTS.

For all instances, *n* is the number of men, *m* the number of women (equals to *n* when unspecified) and *c* the capacity (equals to 1 when unspecified). In the column *PP*, the value 1 indicates that *PP1* is executed, the value 1+2 indicates that *PP1* and *PP2* are executed. The column *time* shows any cumulative preprocessing time. Then, the column *space* represents the size of the search space, it is equal to $|\mathcal{R}(\mathcal{I})|$ in the first configuration, and to $|S_{UB}| - |S_{LB}|$ in the second one. $b_{LS}$ and $time_{LS}$ (resp. $b_{CP}$ and $time_{CP}$) indicate the best value found and the time required to obtain it with *LS* (resp. *CP*). *proof*<sub>CP</sub> indicates the time *CP* requires to prove the optimality once the best solution is found. When the optimal solution has been found for each of the 10 instances, the average value is labelled with “†”. When the optimality of the solution has been proven on all 10 instances, “†” is replaced by “‡”. All the time measures are in seconds.

In Tables 2–4, we observe the great improvements we have made on both models in all instances thanks to our preprocessing step. Indeed, when using the presolve algorithms, *LS*

<table><caption>Table 2: Experiments on SM instances</caption><thead><tr><th>n</th><th>PP</th><th>time</th><th>space</th><th>bar</th><th>b<sub>LS</sub></th><th>b<sub>CP</sub></th><th>time<sub>LS</sub></th><th>time<sub>CP</sub></th><th>proof<sub>CP</sub></th></tr></thead><tbody><tr><td rowspan="2">500</td><td>1</td><td>0.85</td><td>92.8</td><td>-</td><td>346.2</td><td>345.8<sup>†</sup></td><td>112.04</td><td>4.10</td><td>1.29</td></tr><tr><td>1+2</td><td>0.95</td><td><b>5.7</b></td><td>354.8</td><td>346</td><td><b>345.8<sup>†</sup></b></td><td>0.15</td><td>0.039</td><td>0.039</td></tr><tr><td rowspan="2">1000</td><td>1</td><td>6.42</td><td>150</td><td>-</td><td>756.8</td><td>755.8<sup>†</sup></td><td>191.07</td><td>33.27</td><td>10.47</td></tr><tr><td>1+2</td><td>6.75</td><td><b>12.1</b></td><td>778.3</td><td>755.8<sup>†</sup></td><td>755.8<sup>†</sup></td><td>0.94</td><td><b>0.29</b></td><td>0.02</td></tr><tr><td rowspan="2">2000</td><td>1</td><td>51.99</td><td>267.3</td><td>-</td><td>1756.6</td><td>1637</td><td>226.65</td><td>380.62</td><td>TimeOut</td></tr><tr><td>1+2</td><td>53.40</td><td><b>11.1</b></td><td>1650</td><td>1633</td><td><b>1632.9<sup>†</sup></b></td><td>2.62</td><td>1.34</td><td>0.03</td></tr></tbody></table>

<table><caption>Table 3: Experiments on HR instances</caption><thead><tr><th>n-m-c</th><th>PP</th><th>time</th><th>space</th><th>bar</th><th>b<sub>LS</sub></th><th>b<sub>CP</sub></th><th>time<sub>LS</sub></th><th>time<sub>CP</sub></th><th>proof<sub>CP</sub></th></tr></thead><tbody><tr><td>280-40-7</td><td>1</td><td>0.08</td><td>63.2</td><td>-</td><td>127.3</td><td>127.2<sup>†</sup></td><td>4.64</td><td>0.80</td><td>0.29</td></tr><tr><td>500-63-8</td><td>1+2</td><td>0.13</td><td><b>2.6</b></td><td>131.3</td><td>127.5</td><td><b>127.2<sup>†</sup></b></td><td>4.0E-4</td><td>0.006</td><td>0.005</td></tr><tr><td>840-70-12</td><td>1</td><td>0.22</td><td>130.2</td><td>-</td><td>289.1<sup>†</sup></td><td>289.1<sup>†</sup></td><td>76.95</td><td>5.97</td><td>2.451</td></tr><tr><td></td><td>1+2</td><td>0.33</td><td><b>6.3</b></td><td>297.1</td><td>289.1<sup>†</sup></td><td>289.1<sup>†</sup></td><td>0.062</td><td><b>0.037</b></td><td>0.005</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td>478.8</td><td>477.4<sup>†</sup></td><td>84.41</td><td>27.50</td><td>8.47</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td>477.7</td><td><b>477.4<sup>†</sup></b></td><td>1.5E-3</td><td>0.054</td><td>0.004</td></tr></tbody></table>

<table><caption>Table 4: Experiments on MM instances</caption><thead><tr><th>n-c</th><th>PP</th><th>time</th><th>space</th><th>bar</th><th>b<sub>LS</sub></th><th>b<sub>CP</sub></th><th>time<sub>LS</sub></th><th>time<sub>CP</sub></th><th>proof<sub>CP</sub></th></tr></thead><tbody><tr><td>100-3</td><td>1</td><td>0.08</td><td>69.3</td><td>-</td><td>154.3<sup>†</sup></td><td>154.3<sup>†</sup></td><td>23.53</td><td>1.01</td><td>0.39</td></tr><tr><td></td><td>1+2</td><td>0.12</td><td><b>5.8</b></td><td>162.9</td><td>154.3<sup>†</sup></td><td>154.3<sup>†</sup></td><td><b>0.005</b></td><td>0.011</td><td>0.010</td></tr><tr><td>300-5</td><td>1</td><td>0.53</td><td>302.6</td><td>-</td><td>986.5</td><td>972.1<sup>†</sup></td><td>143.08</td><td>170.28</td><td>49.69</td></tr><tr><td></td><td>1+2</td><td>0.96</td><td><b>9</b></td><td>984.1</td><td>972.2</td><td><b>972.1<sup>†</sup></b></td><td>0.63</td><td>0.33</td><td>0.01</td></tr><tr><td>500-10</td><td>1</td><td>2.38</td><td>879.3</td><td>-</td><td>4183.7</td><td>-</td><td>109.46</td><td>TimeOut</td><td>TimeOut</td></tr><tr><td></td><td>1+2</td><td>5.43</td><td><b>14.2</b></td><td>3504.2</td><td>3476.9<sup>†</sup></td><td>3476.9<sup>†</sup></td><td><b>0.14</b></td><td>3.14</td><td>0.05</td></tr></tbody></table>

and *CP* are much faster (up to several thousand times faster on average to get the best solution) and give optimal or near-optimal solutions. This is due to the great reduction of the search space, as we can see from the values of *space*, and to the acceleration of the evaluation speed (full results are in the Technical Appendix). The good quality of the upper-bound $\bar{b}$ (at most 5% away from the optimal value) is the reason why we can reduce this much the search space. Furthermore, our preprocessing time is very low and is largely compensated by the speed of the improved models. Finally, thanks to *PP2* our *CP* model is able to find and prove optimal solutions even for large instances for which *CP* without *PP2* timed out.

## 7 Conclusion

In this paper, we have established theoretical results on the Robust Stable Matching problem on SM instances. We have provided polynomial time algorithms for a preprocessing step that exploit these results. Also, we have generalised our theoretical results and algorithms to MM instances. We have shown experimentally that these algorithms allow to greatly improve the efficiency and the quality of any rotation-based model (via experiments on a heuristic and an exact method) solving the RSM problem on SM, HR and MM instances. The constraint programming model we provide, based on our presolve algorithms, is able to solve the problem exactly, even for large instances. In future work, it may be interesting to investigate the potential guarantees of these presolve algorithms, or possibly to find an approximate algorithm using a median stable matching. At last, this paper focuses on finding (1,b)-supermatches, so further studies could consider the general case of finding (a,b)-supermatches, for which we do not know any polynomial-time method to evaluate the robust score, and the possibility to use similar presolve algorithms.
# Acknowledgments

This publication has emanated from research conducted with the financial support of the Futur & Ruptures program co-granted by IMT, Institut Carnot TSN, Institut Carnot M.I.N.E.S. and Fondation Mines-Télécom.

# References

[Baïou and Balinski, 2000] Mourad Baïou and Michel Balinski. Many-to-many matching: stable polyandrous polygamy (or polygamous polyandry). *Discrete Applied Mathematics*, 101(1-3):1–12, 2000.

[Bansal et al., 2007] Vipul Bansal, Aseem Agrawal, and Varun S Malhotra. Polynomial time algorithm for an optimal stable assignment with multiple partners. *Theoretical Computer Science*, 379(3):317–328, 2007.

[Biró and McDermid, 2008] Peter Biró and Eric McDermid. Three-sided stable matchings with cyclic preferences and the kidney exchange problem. In *Proceedings of COMSOC: 2nd International Workshop on Computational Social Choice*, pages 97–108, 2008.

[Cheng, 2010] Christine T Cheng. Understanding the generalized median stable matchings. *Algorithmica*, 58:34–51, 2010.

[Chisca et al., 2016] Danuta Chisca, Mohamed Siala, Gilles Simonin, and Barry O'Sullivan. A cp-based approach for popular matching. In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 30, 2016.

[Cseh et al., 2021] Ágnes Cseh, Guillaume Escamocher, Begüm Genç, and Luis Quesada. A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences. 2021.

[Dasgupta and Maskin, 2008] Partha Dasgupta and Eric Maskin. On the robustness of majority rule. *Journal of the European Economic Association*, 6(5):949–973, 2008.

[Eirinakis et al., 2012] Pavlos Eirinakis, Dimitrios Magos, Ioannis Mourtos, and Panayiotis Miliotis. Finding all stable pairs and solutions to the many-to-many stable matching problem. *INFORMS Journal on Computing*, 24(2):245–259, 2012.

[Gale and Shapley, 1962] David Gale and Lloyd S Shapley. College admissions and the stability of marriage. *The American Mathematical Monthly*, 69(1):9–15, 1962.

[Genc et al., 2017] Begum Genc, Mohamed Siala, Gilles Simonin, and Barry O'Sullivan. Finding robust solutions to stable marriage. In *Proceedings of the 26th International Joint Conference on Artificial Intelligence*, pages 631–637, 2017.

[Genc et al., 2019] Begum Genc, Mohamed Siala, Gilles Simonin, and Barry O'Sullivan. Complexity study for the robust stable marriage problem. *Theoretical Computer Science*, 775:76–92, 2019.

[Genc, 2019] Begum Genc. *An approach to robustness in stable marriage and stable roommates problems*. PhD thesis, University College Cork, 2019.

[Gervet, 1995] Carmen Gervet. *Set Intervals in Constraint Logic Programming: Definition and implementation of a language*. PhD thesis, Université de Franche Comté Besançon, 1995.

[Gervet, 1997] Carmen Gervet. Interval propagation to reason about sets: Definition and implementation of a practical language. *Constraints*, 1:191–244, 1997.

[Ginsberg et al., 1998] Matthew L Ginsberg, Andrew J Parkes, and Amitabha Roy. Supermodels and robustness. In *AAAI/IAAI*, pages 334–339, 1998.

[Gusfield and Irving, 1989] Dan Gusfield and Robert W Irving. *The stable marriage problem: structure and algorithms*. MIT press, 1989.

[Hebrard et al., 2004] Emmanuel Hebrard, Brahim Hnich, and Toby Walsh. Super solutions in constraint programming. In *International conference on integration of artificial intelligence (AI) and operations research (OR) techniques in constraint programming*, pages 157–172. Springer, 2004.

[Irving and Leather, 1986] Robert W Irving and Paul Leather. The complexity of counting stable marriages. *SIAM Journal on Computing*, 15(3):655–667, 1986.

[Jacobovic, 2016] Royi Jacobovic. Perturbation robust stable matching. *arXiv e-prints*, pages arXiv:1612, 2016.

[Mai and Vazirani, 2018] Tung Mai and Vijay V. Vazirani. Finding Stable Matchings That Are Robust to Errors in the Input. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, *26th Annual European Symposium on Algorithms (ESA 2018)*, volume 112 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 60:1–60:11, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

[Manlove et al., 2007] David F Manlove, Gregg O'Malley, Patrick Prosser, and Chris Unsworth. A constraint programming approach to the hospitals/residents problem. In *Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: 4th International Conference, CPAIOR 2007, Brussels, Belgium, May 23-26, 2007. Proceedings 4*, pages 155–170. Springer, 2007.

[Manlove, 2013] David Manlove. *Algorithmics of matching under preferences*, volume 2. World Scientific, 2013.

[Prud'homme and Fages, 2022] Charles Prud'homme and Jean-Guillaume Fages. Choco-solver: A java library for constraint programming. *Journal of Open Source Software*, 7(78):4708, 2022.

[Roth, 1982] Alvin E Roth. The economics of matching: Stability and incentives. *Mathematics of operations research*, 7(4):617–628, 1982.

[Teo and Sethuraman, 1998] Chung-Piaw Teo and Jay Sethuraman. The geometry of fractional stable matchings and its applications. *Mathematics of Operations Research*, 23(4):874–891, 1998.