## 4 Local Search on Stable Marriages  
We now present an adaptation of the local search schema to deal with the classical stable marriage problem. Then, we will point out the aspects that have to be changed to deal with SMTI problems. Given an SM instance, \(P\), we start from a randomly generated marriage, \(M\). Then, at each search step, we compute the set, \(BP\), of blocking pairs in \(M\) and compute the neighborhood, which is the set of all marriages obtained by removing one of the blocking pairs in \(BP\) from \(M\). Consider a blocking pair \(bp=(m,w)\) in \(M\), \(m^{\prime}=M(w)\) and \(w^{\prime}=M(m)\). Then, removing \(bp\) from \(M\) means obtaining a marriage, \(M^{\prime}\), in which \(m\) is married with \(w\) and \(m^{\prime}\) is married with \(w^{\prime}\), leaving the other pairs unchanged. To select the neighbor \(M^{\prime}\) of \(M\) to move to, we use an evaluation function, \(f:\mathcal{M}_{n}\to Z\), where \(\mathcal{M}_{n}\) is the set of all possible marriages of size \(n\), and \(f(M)=nbp(M)\). For each marriage, \(M\), \(nbp(M)\) is the number of blocking pairs in \(M\), and we move to one with the smallest value of \(f\). To avoid stagnation in a local minimum of the evaluation function, at each search step, we perform a random walk with probability \(p\) (where \(p\) is a parameter of the algorithm), which removes a randomly chosen blocking pair in \(BP\) from the current marriage, \(M\). In this way, we move to a randomly selected marriage in the neighborhood. The algorithm terminates if a stable marriage is found or when a maximal number of search steps or a timeout is reached. This basic algorithm, called SML, has been improved in the computation of the neighborhood, obtaining SML1. When SML moves from one marriage to another one, it takes as input the current marriage, \(M\), and the list \(PAIRS\) of its blocking pairs and returns the marriage in the neighborhood of \(M\) with the best value of the evaluation function, i.e., the one with the fewest blocking pairs. However, the number of such blocking pairs may be very large. Furthermore, some of them may be useless, since their removal would surely lead to new marriages that will not be chosen by the evaluation function. This is the case for the so-called _dominated_ blocking pairs. Algorithm SML1 considers only undominated blocking pairs. **Definition 9** (Dominance in blocking pairs): _Let \((m,w)\) and \((m,w^{\prime})\) be two blocking pairs. Then, \((m,w)\) dominates (from the men's point of view) \((m,w^{\prime})\) iff \(m\) prefers \(w\) to \(w^{\prime}\). There is an equivalent concept from the women's point of view._  
**Definition 10** (Undominated blocking pair): _A men- (resp., women-) undominated blocking pair is a blocking pair, such that there is no other blocking pair that dominates it from the men's (resp., women's) point of view._  
It is easy to see that, if \(M\) is an unstable marriage, \((m,w)\), a men- (resp., women-) undominated blocking pair in \(M\), \(m^{\prime}=M(w)\), \(w^{\prime}=M(m)\) and \(M^{\prime}\) is obtained from \(M\) by removing \((m,w)\), there are no blocking pairs in \(M^{\prime}\) in which \(m\) (resp., \(w\)) is involved. This property would not be true if we removed a dominated blocking pair. This is why we focus on the removal of undominated blocking pairs when we pass from one marriage to another in our local search algorithm. Considering again the SM in Table 1 and the marriage \(2\)\(7\)\(4\)\(8\)\(6\)\(3\)\(5\)\(1\), the blocking pair, \((m_{8},w_{4})\), dominates (from the men's point of view) \((m_{8},w_{2})\). If we remove \((m_{8},w_{2})\) from the marriage, \((m_{8},w_{4})\) will remain. On the other hand, removing \((m_{8},w_{4})\) also eliminates \((m_{8},w_{2})\). Thus, removing \((m_{8},w_{4})\) is more useful than removing \((m_{8},w_{2})\). By using the undominated blocking pairs instead of all the blocking pairs, we also limit the size of the neighborhood, since each man or woman is involved in at most one undominated blocking pair.