# finding_robust_solutions_to_stable_marriage__116ef802.pdf

Finding Robust Solutions to Stable Marriage

Begum Genc1, Mohamed Siala1, Gilles Simonin2, Barry O Sullivan1

1 Insight, Centre for Data Analytics, Department of Computer Science, University College Cork, Ireland 2 TASC, Institut Mines Telecom Atlantique, LS2N UMR 6004, Nantes, France {begum.genc, mohamed.siala, barry.osullivan}@insight-centre.org, gilles.simonin@imt-atlantique.fr

We study the notion of robustness in stable matching problems. We ﬁrst deﬁne robustness by introducing (a, b)-supermatches. An (a, b)-supermatch is a stable matching in which if a pairs break up it is possible to ﬁnd another stable matching by changing the partners of those a pairs and at most b other pairs. In this context, we deﬁne the most robust stable matching as a (1, b)-supermatch where b is minimum. We show that checking whether a given stable matching is a (1, b)-supermatch can be done in polynomial time. Next, we use this procedure to design a constraint programming model, a local search approach, and a genetic algorithm to ﬁnd the most robust stable matching. Our empirical evaluation on large instances show that local search outperforms the other approaches.

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 difﬁcult 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 ﬁnd 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 ﬁnd stable marriages (SM) [Gale and Shapley, 1962; Gusﬁeld and Irving, 1989], and ﬁnding donors for kidney patients [Roth et al., 2005]. Stable Marriage (SM) [Gale and Shapley, 1962] is the ﬁrst and the most studied variant of these problems. In SM, the sets of agents correspond to men and women. The goal is to

ﬁnd 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., ﬁnd 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 satisﬁability [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 ﬁrst 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 ﬁnd 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 efﬁcient 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 Sec-

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

tion 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 [Gusﬁeld 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 ﬁxed 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 man mki from wki to wki+1 (the operation +1 is modulo l) leads to a stable matching M/ρ. The latter is said to be obtained after eliminating ρ from M. 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 [Gusﬁeld 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) [Gusﬁeld 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 [Gusﬁeld 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 from M0 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 from M0. 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 ﬁxed, 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 ﬁrst recall the basics, and then show how to ﬁnd 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-ﬁxed (stable) pair to remove from M. 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 from M0 leading to M . Hence, if m, w / M0 then ρpm,w exists, and there is a set of stable matchings Su that dominate

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

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 deﬁne a speciﬁc set of rotations S m UP as follows:

S m UP = S \ ({ρpm,w} {N + t (ρpm,w) S}). (1)

If m, w / Mz, we deﬁne a speciﬁc set of rotations S m DOWN as follows:

S m DOWN = S {ρem,w} {N t (ρem,w) \ S}. (2)

Observe ﬁrst 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 to M than M m UP or M m DOWN. Let us illustrate these terms on a sample stable marriage instance. Consider the stable marriage instance speciﬁed 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 ﬁrst vector represents the set of men and the second vector represents the partner of each man in the matching. Each edge from M to M 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

Table 1: Preference lists for men (left) and women (right) for a sample stable marriage instance of size 7.

Figure 1: Rotation poset of the instance given in Table 1.

Figure 2: The lattice of all stable matchings corresponding to the instance given in Table 1.

m, w ρpm,w ρem,w S m UP S m DOWN 0, 4 ρ2 ρ3 {ρ0, ρ1} {ρ0, ρ1, ρ2, ρ3} 1, 5 ρ1 ρ5 {ρ0} {ρ0, ρ1, ρ2, ρ4, ρ5} 2, 6 - ρ4 - {ρ0, ρ1, ρ2, ρ4} 3, 3 - ρ5 - {ρ0, ρ1, ρ2, ρ4, ρ5} 4, 1 - ρ3 - {ρ0,ρ1, ρ2, ρ3} 5, 2 ρ2 - {ρ0, ρ1} - 6, 0 ρ1 ρ4 {ρ0 } {ρ0, ρ1, ρ2, ρ4}

Table 2: The repair closed subsets S m UP and S m DOWN for M5.

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 deﬁnition of incomparability, if two rotations are incomparable, it means that they modify a set of men who do not require modiﬁcations from the other ﬁrst. 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).

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

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 matching Mx 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 deﬁnition. 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 ) n {ρpm,w} {N + t (ρpm,w) S} o . 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 matching Mx that does not contain m, w dominated by M but different from M 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) n {ρem,w} {N t (ρem,w) \ S} o . 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 to M than Mi.

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 deﬁnition 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.

m M m UP M m DOWN dm up dm down bm 0 M2 M8 2 2 1 1 M1 M7 4 4 3 2 - M6 2 1 3 - M7 4 3 4 - M8 2 1 5 M2 - 2 1 6 M1 M6 4 2 1

Table 3: The repair stable matchings M m UP and M m DOWN for each man in M5 and the distances between them.

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 deﬁnition 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 dm up and dm down in the table, where for each man m, dm up = d(M5, M m UP ) and dm down = d(M5, M m DOWN), respectively. If M m UP does not exist for a man m, then dm up 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(dm up, dm down) 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 veriﬁcation algorithm to ﬁnd (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 difﬁcult problems [Holland, 1975; 1992;

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

B ack, 1996]. The model that we propose to ﬁnd 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 ﬁtness 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 ﬁtness 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 ﬁrst step of the algorithm is to ﬁnd a random solution to start with. A random stable matching M is created by using the method deﬁned 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 deﬁned 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, identiﬁcation 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 from Ns 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 ﬁnding 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 ﬁnding their respective b values is O(n |V|2).

Figure 3: Illustration of the sets Ls (ρ1, ρ4, ρ7) and Ns (ρ2, ρ6) on a sample rotation poset for a given closed subset S.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

5 Experiments

We experimentally evaluate the three models for ﬁnding 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 ﬁxed 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 ﬁttest stable matching from the population. Additionally, the probability of applying mutation on a randomly selected stable matching is ﬁxed 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 ﬁrst 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]:

score(h, I) = ub(I) h(I) + 1

ub(I) lb(I) + 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 ﬁnd any solution for I.

0 0.2 0.4 0.6 0.8 1

Objective ratio

Figure 4: Search Efﬁciency on the First Set of Instances

0 0.2 0.4 0.6 0.8 1

Objective ratio

Figure 5: Search Efﬁciency on the Second Set of Instances

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 ﬁgures is clear. Local search is efﬁcient both in the quality of the solutions, and in runtime. Indeed, in the ﬁrst 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 ﬁnd 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 ﬁrst data set it does not ﬁnd the best solutions in all instances. Moreover, it takes much longer time than CP and LS for ﬁnding good quality solutions. The results in Figure 5 are more spectacular for local search. Local search does not always ﬁnd 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 ﬁrst showed that the problem of ﬁnding 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 ﬁnding 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 ﬁnd 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 ﬁnancial support of Science Foundation Ireland (SFI) under Grant Number SFI/12/RC/2289.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

References [B ack, 1996] Thomas B ack. Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, Oxford, UK, 1996. [Boussemart et al., 2004] Fr ed eric Boussemart, Fred Hemery, Christophe Lecoutre, and Lakhdar Sais. Boosting systematic search by weighting constraints. In Proceedings of the 16th European Conference on Artiﬁcial Intelligence ECAI, pages 146 150, 2004. [Gale and Shapley, 1962] D. Gale and L. S. Shapley. College Admissions and the Stability of Marriage. The American Mathematical Monthly, 69(1):9 15, January 1962. [Genc et al., 2017a] Begum Genc, Mohamed Siala, Barry O Sullivan, and Gilles Simonin. Robust stable marriage. In Proceedings of the Thirty-First AAAI Conference on Artiﬁcial Intelligence, February 4-9, 2017, San Francisco, California, USA., pages 4925 4926, 2017. [Genc et al., 2017b] Begum Genc, Mohamed Siala, Barry O Sullivan, and Gilles Simonin. Technical report on ﬁnding robust solutions to stable marriage. Co RR, abs/1705.09218, 2017. [Ginsberg et al., 1998] Matthew L. Ginsberg, Andrew J. Parkes, and Amitabha Roy. Supermodels and robustness. In In AAAI/IAAI, pages 334 339, 1998. [Goldberg, 1989] David E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition, 1989. [Gusﬁeld and Irving, 1989] Dan Gusﬁeld and Robert W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge, MA, USA, 1989. [Hebrard et al., 2004] Emmanuel Hebrard, Brahim Hnich, and Toby Walsh. Super solutions in constraint programming. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, First International Conference, CPAIOR 2004, Nice, France, April 20-22, 2004, Proceedings, pages 157 172, 2004. [Hebrard, 2007] Emmanuel Hebrard. Robust solutions for constraint satisfaction and optimisation under uncertainty. Ph D thesis, University of New South Wales, 2007. [Holland, 1975] J. H. Holland. Adaptation in Natural and Artiﬁcial Systems. University of Michigan Press, Ann Arbor, MI, USA, 1975. [Holland, 1992] John Holland. Adaptation in Natural and Artiﬁcial Systems. MIT Press, 1992. [Irving and Leather, 1986] Robert W Irving and Paul Leather. The complexity of counting stable marriages. SIAM J. Comput., 15(3):655 667, Aug 1986. [Lourenc o et al., 2010] Helena R. Lourenc o, Olivier C. Martin, and Thomas St utzle. Iterated Local Search: Framework and Applications Handbook of Metaheuristics. volume 146 of International Series in Operations Research

& Management Science, chapter 12, pages 363 397. Springer US, Boston, MA, 2010. [Manlove, 2013] D.F. Manlove. Algorithmics of Matching Under Preferences. Series on theoretical computer science. World Scientiﬁc, 2013. [Prud homme et al., 2016] Charles Prud homme, Jean Guillaume Fages, and Xavier Lorca. Choco Solver Documentation. TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING S.A.S., 2016. [Roth et al., 2005] Alvin Roth, Tayfun S onmez, and Utku Unver. Pairwise kidney exchange. Game theory and information, Econ WPA, 2005. [St utzle, 1998] Thomas St utzle. Local search algorithms for combinatorial problems: analysis, improvements, and new applications. Ph D thesis, TU Darmstadt, 1998. [Sussman, 2007] Gerald Jay Sussman. Building robust systems an essay, 2007.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)