## 7 Results on SM Problems
### Sampling the Stable Marriage Lattice  
We also evaluated the ability of SML2 to sample the lattice of stable marriages of a given SM problem. To do this, we randomly generated 100 SM problems for each size between 10 and 100, with step 10. Then, we ran the SML2 algorithm 500 times on each instance. To evaluate the sampling capabilities of SML2, we first measured the distance of the found stable marriages (on average) from the male-optimal marriage (the one that would be returned by the GS algorithm). Given a SM problem instance, \(P\), consider a stable marriage, \(M\), for \(P\). The distance of \(M\) from \(M_{m}\) is the number of arcs from \(M\) to \(M_{m}\) in the Hasse diagram of the stable marriage lattice for \(P\). This diagram can be computed in \(O(n^{2}+n|S|)\) time [10], where \(S\) is the set of all possible stable marriages of a given SM instance. For each SM problem instance, we compute the average normalized distance from the male-optimal marriage considering 500 runs. Notice that normalizations  
Figure 2: Results using SML2. (**a**) Blocking pair ratio during the execution; (**b**) number of steps necessary to find a stable marriage. is needed since different SM instances with the same size may have a different number of stable lattices. Then, we compute the average \(D_{m}\) (With this measure, we want to evaluate how far from the two extremes of the lattice the marriages we find are. However, it is possible to give other definitions of stable matchings that belong to the middle of the lattice, such as the one presented in [44].) of these distances over all the 100 problems with the same size, which is, therefore, formally defined as \(D_{m}=\frac{1}{100}\sum_{j=1}^{100}\frac{1}{500}\sum_{i=1}^{500}\frac{d_{m}(M _{i},P_{j})}{d_{m}(M_{i},P_{j})+d_{w}(M_{i},P_{j})}\), where \(d_{m}(M_{i},P_{j})\) (resp., \(d_{w}(M_{i},P_{j})\)) is the distance of \(M_{i}\) from the male (resp., female)-optimal marriage in the lattice of an SM instance \(P_{j}\). If \(D_{m}=0\), this means that all the stable marriages returned coincide with the male-optimal marriage. On the other extreme, if \(D_{m}=1\), this means that all stable marriages returned coincide with the female-optimal one. Figure 3(a) shows that, for the stable marriages returned by algorithm SML2, the average distance from the male-optimal is around 0.5. This is encouraging, but not completely informative, since an algorithm that returns the same stable marriage all the time, with a distance of 0.5 from the male-optimal would also have \(D_{m}=0.5\). To have more informative results, we consider the entropy of the stable marriages returned by SML2. This measures the randomness in the solutions. Let \(f(M_{i})\) be the frequency that SML2 finds a marriage, \(M_{i}\) (for \(i\) in \([1,|S|]\)), that is: \(f(M_{i})=\frac{1}{500}\sum_{j=1}^{500}\mathbb{1}_{M_{i}}(j)\), where \(\mathbb{1}_{M_{i}}(j)\) is the indicator function that returns one if in the \(j\)-th execution the algorithm finds \(M_{i}\), and zero otherwise. The entropy, \(E(P)\), for each SM instance, \(P\) (i.e., for each lattice), of the size, \(k\), is then: \(E(P)=-\sum_{i=1\in\{1..|S|\}}f(M_{i})\log_{2}(f(M_{i}))\). In an ideal case, when each stable marriage in the lattice has a uniform probability of \(1/k!\) to be reached, the entropy is \(\log_{2}(|S|)\) bits. On the other hand, the worst case is when the same stable marriage is always returned, and the entropy is, thus, zero bits. As we want a measure what is independent of the problem's size, we consider a normalized entropy, that is, \(E(P)/\log_{2}(|S|)\), which is in [0,1]. As we have 100 different problems for each size, we compute the average of the normalized entropies for each class of problems with the same size: \(E_{n}=\frac{1}{100}\sum_{i=1}^{100}E(P_{i})/\log_{2}(|S_{i}|)\), where \(S_{i}\) is the set of stable marriages of \(P_{i}\). Figure 3(b) shows that SML2 is not far from the ideal behavior.