Finding Robust Solutions to Stable Marriage

1 Introduction

Heraclitus, the Greek philosopher is quoted as saying that "Change is the only constant". Therefore, it is essential to build robust systems that can be repaired by only minor changes in case of an unforeseen event [Sussman, 2007]. Although it is usually difficult to provide robustness to a complex problem, as it may be computationally expensive, a robust solution reduces the cost of future repairs.

This paper focuses on matching problems under preferences, where the aim is to find an assignment between two disjoint sets of agents while respecting an optimality criterion. Each agent has an ordinal preference ranking over agents of the other set. These types of problems have been widely studied by different research communities such as computer scientists and economists over the years; in fact, the 2012 Nobel Prize for Economics was awarded to Shapley and Roth for their work on stable allocations. Some of the variants can be listed as assigning residents to hospitals (HR), matching men and women to find stable marriages (SM) [Gale and Shapley, 1962; Gusfield and Irving, 1989], and finding donors for kidney patients [Roth et al., 2005].

Stable Marriage (SM) [Gale and Shapley, 1962] is the first and the most studied variant of these problems. In SM, the sets of agents correspond to men and women. The goal is to find a matching M between men and women where each person is matched to at most one partner from the opposite sex such that there is no man and woman that prefers each other to their situations in M. Such a matching is called stable. We primarily work on the stable marriage problem, but the problem is also meaningful in the context of other matching variants.

We introduce the notion of (a, b)-supermatches as a measure of robustness for SM. A stable matching M is called an (a, b)-supermatch if any a agents decide to break their matches in M, thereby breaking a pairs, it is possible to "repair" M (i.e., find another stable matching) by changing the assignments of those a agents and at most b others. This concept is inspired by the notion of (a, b)-supermodels in Boolean satisfiability [Ginsberg et al., 1998] and super solutions in constraint programming [Hebrard et al., 2004; Hebrard, 2007]. When we mention a (or b) as the number of agents, we always refer to the agents from the same set.

In order to give additional insight into the problem we motivate robustness on the Hospital/Residents (HR) problem. The HR problem is a one-to-many generalization of SM. In HR, each hospital has a capacity and a preference list in which they rank the residents. Similarly, each resident has a preference list over the hospitals. A (1, b)-supermatch means that if a resident wants to leave his assigned hospital or a hospital does not want to have one of its current residents, it is possible to move that resident to another hospital by also moving at most b other residents to other hospitals. By minimising b, we can ensure that the required number of additional relocations to provide a repair is minimal and therefore the solution is robust. In practice, the most robust matching minimises the cost for recovering from unwanted and unforeseen events.

The first contribution of this paper is a polynomial time procedure to verify whether a given stable matching is a (1, b)-supermatch. Next, based on this procedure, we design a constraint programming (CP) model, as well as local search (LS) and genetic algorithm (GA) to find the most robust stable matching based on the polynomial time procedure. Last, we give empirical evidence that the local search algorithm is by far the most efficient approach to tackle this problem.

The structure of the paper is as follows. In Section 2, the notations and the basics of the stable marriage problem are introduced. In Section 3 our polynomial-time method is proposed. Next, we give our meta-heuristic algorithms in Section 4. Last, we present our experimental study on random instances in Section 5. The reader is referred to our technical report in [Genc et al., 2017b] for full details including the CP model.

2 Background &Notations

The Stable Marriage problem takes as input a set of men U = {m1,m2, . . . ,mn1 } and a set of women W = {w1,w2, . . . ,wn2 } where each person has an ordinal preference list over people of the opposite sex. For the sake of simplicity, we suppose in the rest of the paper that n1 = n2 (denoted by n), and that each person expresses a complete preference ranking over the set of the opposite sex. We also use m to denote a man in U, and w to denote a woman in W. For a complete background, we refer the reader to [Gusfield and Irving, 1989; Manlove, 2013].

A matching M is a one-to-one correspondence between men and women. For each man m, M(m) = w is called the partner of m in M. In the latter case, we denote by M(w) = m. We shall sometimes abuse notation by considering M as a set of pairs. In that case, a pair 〈m, w〉 ∈ M iff M(m) = w. A pair 〈m, w〉 is said to be blocking a matching M if m prefers w to M(m) and w prefers m to M(w). A matching M is called stable if there exists no blocking pair for M. A pair 〈m, w〉 is said to be stable if it appears in a stable matching. Also, a pair 〈m,w〉 is fixed if 〈m,w〉 appears in every stable matching.

The structure that represents all stable matchings forms a lattice M. In this lattice, the man-optimal matching is denoted by M0 and the woman-optimal (man-pessimal) matching is denoted by Mz . A stable matching Mi dominates a stable matching Mj , denoted by Mi ⪯ Mj , if every man prefers his partner in Mi to Mj or is indifferent between them. The size of a lattice can be exponential as the number of all stable matchings can be exponential [Irving and Leather, 1986]. Therefore, making use of this structure is not practical.

Let M be a stable matching. A rotation ρ = (〈mk0 ,wk0 〉, 〈mk1 ,wk1 〉, . . . , 〈mkl-1 ,wkl-1 〉) (where l ∈ N∗ ) is an ordered list of pairs in M such that changing the partner of each manmki fromwki to wki+1 (the operation +1 is modulo l) leads to a stable matching M/ρ. The latter is said to be obtained after eliminating ρ fromM. In this case, we say that 〈mki ,wki 〉 is eliminated by ρ, 〈mki ,wki+1 〉 is produced by ρ, and that ρ is exposed in M. For each 〈m,w〉 such that 〈m,w〉 /∈ M0, there exists a unique rotation ρpm,w that produces 〈m,w〉. Similarly, if 〈m,w〉 /∈ Mz there is a unique rotation ρem,w that eliminates 〈m,w〉. Note that it is always the case that M (strictly) dominates M/ρ.

There exists a partial order for rotations. A rotation ρ′ is said to precede another rotation ρ (denoted by ρ′ ≺≺ ρ), if ρ′ is eliminated in every sequence of eliminations that starts at M0 and ends at a stable matching in which ρ is exposed [Gusfield and Irving, 1989]. Note that this relation is transitive, that is, ρ′′ ≺≺ ρ′ ∧ ρ′ ≺≺ ρ =⇒ ρ′′ ≺≺ ρ. Two rotations ρ and ρ′ are said to be incomparable if ρ does not precede ρ′ and vice versa. The structure that represents all rotations and their partial order is a directed graph called rotation poset denoted by Π = (V, E). Each rotation corresponds to a vertex in V and there exists an edge from ρ to ρ′ if ρ precedes ρ′ . The number of rotations is bounded by n(n - 1)/2 and the number of arcs is O(n2 ) [Gusfield and Irving, 1989]. It should be noted that the construction of Π can be done in O(n2 ).

Predecessors of a rotation ρ in a rotation poset are denoted by N -(ρ) and successors are denoted by N +(ρ). Later, we shall need transitivity to complete these lists. Therefore, we denote by N - t (ρ) (respectively N + t (ρ)) the predecessors (respectively successors) of a rotation ρ including transitivity.

A closed subset S is a set of rotations such that for any rotation ρ in S, if there exists a rotation ρ′ that precedes ρ then ρ′ is also in S.

Below is a theorem and a corollary from [Gusfield and Irving, 1989] mainly used in some proofs in the next section. We slightly change few notations.

Theorem 1 (Theorem 2.5.7). i) There is a one-one correspondence between the closed subsets of Π and the stable matchings of M. ii) S is the closed subset of rotations of Π corresponding to a stable matching M if and only if S is the (unique) set of rotations on every M0-chain in M ending at M. Further, M can be generated fromM0 by eliminating the rotations in their order along any of these paths, and these are the only ways to generate M by rotation eliminations starting fromM0. iii) If S and S′ are the unique sets of rotations corresponding to distinct stable matchings M and M ′ , then M dominates M ′ if and only if S ⊂ S′ .

Corollary 1 (Corollary 3.2.1). Every man-woman pair 〈m,w〉 is in at most one rotation. Hence there are at most n(n - 1)/2 rotations in an instance of the stable marriage problem of size n.

By Theorem 1, every closed subset in the rotation poset corresponds to a stable matching. We denote by X(S) the set of men that are included in at least one of the rotations in S.

We introduce here a notion that is important to our measure of robustness. Let Mi and Mj be two stable matchings. The distance d(Mi,Mj) is the number of men that have different partners in Mi and Mj. A matching Mk is closer to Mi than Mj if d(Mi,Mk) < d(Mi,Mj). Let a, b ∈ N. A stable matching M is said to be an (a, b)-supermatch if for any set Ψ ⊂ M of a stable pairs that are not fixed, there exists a stable matching M ′ such that M ′ ∩ Ψ = ∅ and d(M,M ′ ) - a ≤ b.

3 Checking (1, b)-supermatch in Polynomial Time

A preliminary version of this section appeared in [Genc et al., 2017a]. In this section we first recall the basics, and then show how to find or verify the closest stable matching of a given stable matching with an unwanted couple. Throughout this section, we suppose that M is the given stable matching, S its closed subset, and 〈m,w〉 ∈ M is a non-fixed (stable) pair to remove fromM.

The closest matching to M that does not include 〈m,w〉 is a matching M ∗ in which either 〈m,w〉 was eliminated or not produced in any sequence of rotation eliminations starting fromM0 leading to M ∗ . Hence, if 〈m,w〉 /∈ M0 then ρpm,w exists, and there is a set of stable matchings Su that dominate M and do not include 〈m,w〉. Similarly, if 〈m,w〉 /∈ Mz then ρem,w exists, and there is a set of stable matchings Sd, dominated by M and not including 〈m, w〉.

If 〈m,w〉 /∈ M0, we define a specific set of rotations S∗m UP as follows:

If 〈m,w〉 /∈ Mz, we define a specific set of rotations S∗m DOWN as follows:

Observe first that S∗m UP and S∗m DOWN are in fact closed subsets since S is a closed subset. Let M ∗m UP (respectively M ∗m DOWN ) be the stable matching corresponding to S∗m UP (respectively S∗m DOWN ). By construction, we have M ∗m UP ∈ Su and M ∗m DOWN ∈ Sd. We show later that any stable matching Mi /∈ {M ∗m UP ,M ∗m DOWN } that does not include the pair 〈m, w〉 cannot be closer toM thanM ∗m UP or M ∗m DOWN .

Let us illustrate these terms on a sample stable marriage instance. Consider the stable marriage instance specified by the preference lists of 7 men/women in Table 1. For the sake of clarity, we denote each man mi with i and each woman wj with j.

Figure 1 represents the rotation poset and all the rotations associated with this sample. In Figure 2, we give the lattice of all stable matchings. There exists two vectors for each stable matching. The first vector represents the set of men and the second vector represents the partner of each man in the matching. Each edge fromM toM ′ on the lattice is labelled with the rotation ρ such that M ′ is obtained after exposing ρ in M.

As an example, let current stable matching be M5, and the closed subset associated with it be S5 = {ρ0, ρ1, ρ2}. Table 2 illustrates for each man m the matchings S∗m UP and S∗m DOWN if they exist.

m0 0 6 5 2 4 1 3 w0 2 1 6 4 5 3 0

m1 6 1 4 5 0 2 3 w1 0 4 3 5 2 6 1

m2 6 0 3 1 5 4 2 w2 2 5 0 4 3 1 6

m3 3 2 0 1 4 6 5 w3 6 1 2 3 4 0 5

m4 1 2 0 3 4 5 6 w4 4 6 0 5 3 1 2

m5 6 1 0 3 5 4 2 w5 3 1 2 6 5 4 0

m6 2 5 0 6 4 3 1 w6 4 6 2 1 3 0 5

We give few lemmas in order to show that the closest stable matching to M when breaking the pair 〈m, w〉 is either S∗m UP or S∗m DOWN .

Lemma 1. Given two incomparable rotations ρ and ρ′ , X({ρ}) ∩ X({ρ′ }) = ∅.

Proof. By definition of incomparability, if two rotations are incomparable, it means that they modify a set of men who do not require modifications from the other first. Therefore the sets of men are distinct.

Lemma 2. Given three stable matchings Mi,Mj and Mk where Mi ⪯ Mj ⪯ Mk, then d(Mj,Mk) ≤ d(Mi,Mk) and d(Mi, Mj ) ≤ d(Mi, Mk).

Proof. Using the properties of domination and the closed subsets in Theorem 1, we can infer Si ⊂ Sj ⊂ Sk.

Assume to the contrary that d(Mj,Mk) > d(Mi,Mk). This situation occurs only if a set of pairs that are present in Mi are eliminated to obtain Mj and then re-matched with the same partners they had in Mi to get Mk. However, this contradicts Corollary 1. For similar reasons, d(Mi,Mj) < d(Mi, Mk).

The case where stable matchings have the same distance such as d(Mi,Mj) = d(Mi,Mk), if the rotation set in the difference sets Sj \ Si, Sk \ Si, and Sk \ Sj modify the same set of men.

Lemma 3. If there exists a stable matchingMx that does not contain 〈m, w〉, dominates M and different from M ∗m UP , then Mx dominates M ∗m UP .

Proof. M ∗m UP ⪯ M by definition. Suppose by contradiction that there exists an Mx such that 〈m,w〉 ̸∈ Mx and M ∗m UP ⪯ Mx ⪯M. It implies that S∗m UP ⊂ Sx ⊂ S. In this case, (Sx \ S∗m UP ) ⊂ {{ρpm,w } ∪ {N + t (ρpm,w ) ∩ S}}. However, this set contains ρpm,w and the rotations preceded by ρpm,w . Adding any rotation from this set to Sx results in a contradiction by either adding 〈m,w〉 to the matching, thereby not breaking that couple, or because the resulting set is not a closed subset.

Lemma 4. If there exists a stable matchingMx that does not contain 〈m,w〉 dominated by M but different fromM ∗m DOWN , then M ∗m DOWN dominates Mx.

Proof. Similar to the proof above, suppose that there exists an Mx such that 〈m,w〉 ̸∈ Mx and M ⪯ Mx ⪯ M ∗m DOWN . We have S ⊂ Sx ⊂ S∗m DOWN . It implies (Sx \ S) ⊂ {{ρem,w } ∪ {N - t (ρem,w ) \ S}}. This set contains the rotation ρem,w that eliminates the pair and the rotations preceding ρem,w . In order to add ρem,w all other rotations must be added to form a closed subset. If all rotations are added, S = S∗m DOWN which results in a contradiction.

Lemma 5. For any stable matching Mi incomparable with M such that Mi does not contain the pair 〈m,w〉, M ∗m UP is closer toM thanMi.

Proof. Let Si be the closed subset corresponding to Mi, and S be that corresponding to M.

First, we consider the case in which Si ∩ S = ∅. If the closed subsets have no rotations in common the rotations in these sets are incomparable. Using Lemma 1, X(Si) ∩ X(S) = ∅. Therefore, d(Mi,M) = |X(Si)| + |X(S)|, whereas d(M ∗m UP ,M) ≤ |X(S)|.

Second, we consider the case in which Si ∩ S ̸= ∅. Let Mc be the closest dominating stable matching of both Mi and M ∗m UP , along with Sc as its corresponding closed subset. Using Lemma 2 we know that d(M ∗m UP ,Ms) ≤ d(Mc,Ms), where d(Mc, Ms) = |X(S \ Sc)|.

Using Lemma 1 we know that X(Si \Sc)∩X(S \Sc) = ∅. Therefore, d(Mi,M) = |X(Si \Sc)|+|X(S \Sc)|. By substituting the formula above, d(Mi,M) ≥ |X(Si \ Sc)| + d(M ∗m UP ,M). Using the fact that |X(Si \ Sc)| > 0 from the definition of Mi, we can conclude that d(Mi,M) > d(M ∗m UP ,M).

The following theorem is a direct consequence of Lemmas 3, 4, 5.

Theorem 2. The closest stable matching of a stable matching M given the unwanted pair 〈m,w〉 is either M ∗m UP or M ∗m DOWN .

We show that checking if a stable matching is a (1, b)- supermatch can be performed in O(n × |V|) time after a O(n2 + |V|2 ) preprocessing step. First, the pre-processing step consists of building the poset graph (O(n2 )), the lists N - t (ρ), N + t (ρ) for each rotation ρ (O(|V|2 )), and ρem,w and ρpm,w for each pair 〈m,w〉 whenever applicable (O(n2 )). Next, we compute S∗m UP and S∗m DOWN for each man. Note that S∗m UP and S∗m DOWN can be constructed in O(|V|) time (by definition of S∗m UP and S∗m DOWN ) for each man m. Note that d(M ∗m UP ,M) is equal to the number of men participating in the rotations that are eliminated from S to obtain S∗m UP . Similarly, d(M ∗m DOWN ,M) is equal to the number of men participating in the rotations that are added S to obtain S∗m DOWN . Last, if b < d(M ∗m UP ,M) - 1 and b < d(M ∗m DOWN , M) - 1, we know that it is impossible to repair M when m needs to change his partner with at most b other changes. Otherwise, M is a (1, b)-supermatch.

As an illustration, Table 3 shows the stable matchings corresponding to the closed subsets given in Table 2 and the distances between the current stable matching M5 to each one of them. The distances are denoted as dmup and dmdown in the table, where for each man m, dmup = d(M5,M ∗m UP ) and dmdown = d(M5,M ∗m DOWN ), respectively. If M ∗m UP does not exist for a man m, then dmup is denoted by ∞ (a similar notation is used when M ∗m DOWN does not exist). Last, bm represents the repairing cost of each man m and calculated by bm = min(dmup , dmdown ) - 1.

The robustness of a stable matching is measured by the worst case repair cost over all men involved, b = max{bi | i ∈ {1...n}}. Hence, M5 is a (1,3)-supermatch.

4 Metaheuristics

In this section, we describe two models, namely Genetic Algorithm and Local Search using the polynomial time verification algorithm to find (1,b)-supermatches and subsequently the most robust stable matching.

4.1 Genetic Algorithm

Genetic algorithms are being used extensively in optimization problems as an alternative to traditional heuristics. They are compelling robust search and optimization tools, which work on the natural concept of evolution, based on natural genetics and natural selection. Holland introduced the GAs and he has also shown how to apply the process to various computationally difficult problems [Holland, 1975; 1992;

B¨ack, 1996]. The model that we propose to find the most robust stable matching is detailed as follows:

Initialization. A number of random stable matchings are generated for constructing the initial population. Recall that each closed subset in the rotation poset corresponds to a stable matching. The random stable matching generation is performed by selecting a random rotation from the rotation poset and adding all of its predecessors to the rotation set to construct a closed subset. Recall that the set of all predecessors of a given node is N - t (ρ).

Evaluation. For each stable matching Mi, we denote by bi its b value. At this step, we compute the value bi of each stable matching Mi in the population. Then, a fitness value vi = bi is assigned to each Mi in the population. Then, the values vi are normalised in the interval [0, 1].

Evolution. The evolution step consists in selecting stable matchings from the population using the roulette wheel selection method [Goldberg, 1989], then applying crossover and mutation on the selected matchings.

• Crossover. Given two stable matchings and their corresponding closed subsets S1 and S2, one random rotation is selected from each subset. Let ρ1 and ρ2 denote the randomly selected rotations. If ρ1 ̸∈ S2, then ρ1 and all its predecessors that are not included in S2 are added to S2 to form a new closed subset. This new closed subset corresponds to one of the children stable matchings produced by crossover. Similarly, the same process is repeated for S1 and another stable matching is obtained. If the rotations are already in the closed subsets, no action is taken.
• Mutation. Given the closed subset S of a stable matching, a random rotation ρ from V is selected. If ρ ̸∈ S, then ρ and all its required predecessors to form a closed subset are added to S. However, if ρ ∈ S then ρ and all its successors in S are removed from S. Removing the successors will also yield in a stable matching.

For each created stable matching, the method described in the end of Section 3 is called to compute the b value. Recall that this procedure takes O(n × |V|) time after a O(n2 + |V|2 ) preprocessing step. In order to speed up this process from a practical point of view, in our experiments an extra data structure is being used to memorize the fitness value of already generated stable matchings.

The algorithm repeats evolution phase until the termination criteria met and the phase consists of calling evaluation, crossover and mutation subsequently. In both crossover and mutation, the worst case time complexity for one call is bounded by O(|V|) since the set of all predecessors (respectively successors) of a given node is N - t (ρ) (respectively N + t (ρ)).

4.2 Local Search

In our local search model, we use the well-known iterated local search with restarts [St¨utzle, 1998; Lourenc¸o et al., 2010]. The first step of the algorithm is to find a random solution to start with. A random stable matching M is created by using the method defined in Initialization step in Section 4.1.

Then, a neighbouring stable matching set is created using the rotation poset.

A neighbour in this context is defined as a stable matching that differs only by one rotation from the closed subset of M. Let S denote the closed subset of M and Ls the set of leaf rotations in S. Removing one rotation ρi ∈ Ls from S corresponds to a dominating neighbour of M. Removing each ρi ∈ Ls one at a time corresponds to a different neighbour. Similarly, let Ns denote the set of rotations that are not included in S and either those rotations have an in-degree of 0 or all of their predecessors are in S. In the same manner, adding a rotation from Ns to S at a time corresponds to a neighbour of M.

Figure 3 illustrates a sample rotation poset, where the closed subset is S = {ρ0, ρ1, ρ3, ρ4, ρ5, ρ7}. Then, identification of the leaf nodes in this set would be as Ls = {ρ1, ρ4, ρ7}, since none of their children are included in S. Similarly, the neighbour rotations in Ns = {ρ2, ρ6} since all their parents are included in the closed subset S.

These two sets correspond to rotations, where removal of any rotation in Ls from S at a time does not require removal of any other rotations in order to obtain another closed subset, i.e. a neighbour. Likewise, adding any rotation fromNs to S does not require adding any additional rotations to obtain a closed subset.

At each iteration, if a neighbour has lower b than M, in other words, it is a more robust solution, the search continues by finding the neighbours of the new solution. The best solution is kept as the best solution found so far in the whole search process. There is an iteration limit, that indicates the depth of search for neighbours of a randomly created stable matching. After the iteration limit is met, a new random stable matching is generated and the neighbour search continues with that stable matching. If there is no improvement in the best solution for a predetermined number of iterations (cutoff limit), the search terminates.

Notice that there can be at most |V| neighbours of a stable matching. Thus, creating neighbours and finding their respective b values is O(n × |V|2 ).

5 Experiments

We experimentally evaluate the three models for finding the most robust stable matching. The CP model is implemented in Choco 4.0.1 [Prud'homme et al., 2016] and the two metaheuristics are implemented in Java. All experiments were performed on DELL M600 with 2.66 Ghz processors under Linux.

We ran each model with 4 different randomization seeds for each instance. The time limit is fixed to 20 minutes for every run. An additional cut-off is used for local search (LS) and genetic algorithm (GA) as follows: if the solution quality does not improve for 10000 iterations, we terminate the search. The genetic algorithm applies a crossover at each iteration unless the roulette wheel selection selects the fittest stable matching from the population. Additionally, the probability of applying mutation on a randomly selected stable matching is fixed as 80%. For local search, we chose to restart the local search with a randomly generated stable matching every 50 iterations. Last, the CP model (CP) uses the weighted degree heuristic [Boussemart et al., 2004] with geometric restarts.

We use two sets of random instances. The first set contains 500 instances. The number of men for this set is in the set {300+50∗k} where k ∈ {1, 5}. The second set contains 600 large instances of size {1200+50 ∗ k} where k ∈ {1, 6}. We generated 100 instances for each size for both benchmarks.

In Figures 4 and 5 we plot the normalized objective value of the best solution found by the search model h ∈ {CP,GA, LS} (x-axis) after a given time (y-axis). Let h(I) be the objective value of the best solution found using model h on instance I and lb(I) (resp. ub(I)) the lowest (resp. highest) objective value found by any model on I. The formula below gives a normalized score in the interval [0, 1]:

The value of score(h, I) is equal to 1 if h has found the best solution for this instance among all models, decreases as h(I) gets further from the optimal objective value, and is equal to 0 if and only if h did not find any solution for I.

Note that the CP model runs out of memory for large instances. Therefore, we do not plot it in Figure 5.

The outcome from both figures is clear. Local search is efficient both in the quality of the solutions, and in runtime. Indeed, in the first plot, the best solutions are found by LS and CP. However, CP takes much longer time. Note that in Figure 4, CP and LS both find almost always the same objective, and in fact CP claims that the solution is optimal in all instances except one.

The GA model does not seem to be well suited for this problem. In the first data set it does not find the best solutions in all instances. Moreover, it takes much longer time than CP and LS for finding good quality solutions.

The results in Figure 5 are more spectacular for local search. Local search does not always find the best solutions since the normalised objective ratio does not exceed 90%. However, the overall performance is clearly better than GA in both quality and runtime.

6 Conclusions

We studied the notion of robustness in stable matching problems by using the notion of (a, b)-supermatch. We first showed that the problem of finding a stable matching Mi that is closest to a given stable matching M if a pair (man,woman) decides to break up in M can be found in polynomial time. Then, we used essentially this procedure to model the problem of finding the most robust stable matching using a CP formulation, local search, and genetic algorithm. Last, we empirically evaluated these models on randomly generated instances and showed that local search is by far the best model to find robust solutions.

To the best of our knowledge, this notion of robustness in stable matchings has never been proposed before. We hope that the proposed problem will get some attention in the future as it represents a challenge in real-world settings.

Acknowledgments

This publication has emanated from research conducted with the financial support of Science Foundation Ireland (SFI) under Grant Number SFI/12/RC/2289.