## 8 Results on SMTI Problems  
We generated random SMTI problem instances of a size of 100, by letting \(p_{2}\) vary in [0, 1.0], with step 0.1, and \(p_{1}\) vary in [0.1, 0.8], with step 0.1 (above 0.8, the preference lists start to be empty). For each parameter combination, we generated 100 problem instances. Moreover, the probability of the random walk is set to \(p\) = 20%, and the search step limit is \(s\) = 50,000. We start by showing the average size of the marriages returned by LTIU. In Figure 5, we see that LTIU almost always finds a perfect marriage (that is, a stable marriage with no singles). Even in settings with a large amount of incompleteness (that is, \(p_{1}=0.7\)-\(0.8\)), the algorithm finds very many marriages, with only two singles on average. We also consider the number of steps needed by our algorithm. From Figure 5, we can see that the number of steps is less than 2,000 most of the time, except for problems with a large amount of incompleteness (_i.e._, \(p_{1}=0.8\)). As expected, with \(p_{1}>0.6\), the algorithm requires more steps. In some cases, it reaches the step limit of 50,000. Moreover, as the percentage of ties rises, stability becomes easier to achieve, and thus, the number of steps tends to decrease slightly. From the results, we see that complete indifference (\(p_{2}\) = 1) is a special case. In this situation, the number of steps increases for almost every value of \(p_{1}\). This is because the algorithm makes most of its progress via random restarts. In these problems, every person (if accepted) is equally preferred to all others accepted. The only blocking pairs are those involving singles who both accept each other. Hence, after a few steps, all singles that can be married are matched; stability is reached, and the neighborhood becomes empty. The algorithm, therefore, randomly restarts. In this situation, it is very difficult to find a perfect matching, and the algorithm, therefore, often reaches the step limit. The algorithm is fast. It takes, on average, less than 40 s to give a result even for very difficult problems (see Figure 5(c)). As expected, with \(p_{2}=1\), the time increases for the same reason discussed above concerning the number of steps. Re-considering Figure 5(a) and the fact that all the marriages the algorithm finds are stable, we notice that most of the marriages are perfect. From Figure 5(d), we see that the average percentage of matchings that are perfect is almost always 100%, and this percentage only decreases when the incompleteness is large. We compared our local search approach to the one in [6]. In their experiments, they measured the maximum size of the stable marriages in problems of a size of 10, fixing \(p_{1}\) to 0.5 and varying \(p_{2}\) in [0,1]. We did similar experiments and obtained stable marriages of a very similar size to those reported in [6]. This means that although our algorithm is incomplete in principle, it always appears to find an optimal solution in practice, and for small sizes, it behaves like a complete algorithm in terms of the size of the returned marriage. However, it can also tackle problems of much larger sizes, still obtaining optimal solutions most of the time. We also considered the runtime behavior of our algorithm. In Figure 6(a), we show the average normalized number of blocking pairs and, in Figure 6(b), the average normalized number of singles of the best marriage as the execution proceeds. Although the step limit is 50,000, we only plot results for the first steps, because the rest is a long plateau that is not very interesting. We show the results only for \(p_{2}\) = 0.5. However, for a greater (resp., lower) number of ties, the curves are shifted slightly down  
Figure 5: LTIU varying \(p_{2}\) for different values of \(p_{1}\). (**a**) Average size of marriages; (**b**) average number of steps; (**c**) average execution time; (**d**) percentage of perfect matchings. (resp., up).