## 9 Local Search by Swapping Ties
### Experimental Evaluation  
We generated SMTI problem instances as in the previous section, except for the probability of ties (\(p_{2}\)). For example, if we generate a problem of size \(n\) = 100, with a probability of incompleteness \(p_{1}\) = 0.1 and probability of ties \(p_{2}\) = 0.2, then, since \(p_{1}\) = 0.1, the average length of the preference lists will be 90. Additionally, since \(p_{2}\) = 0.2, each preference list will have about nine ties of a length two. We generated 100 problems for each combination of \(n\), \(p_{1}\) and \(p_{2}\) varying \(n\) in {10, 30, 50, 70, 90}, \(p_{1}\) in [0.1, 0.8] and \(p_{2}\) in [0.1, 1.0] and fixing a limit of 20,000 steps. We ran our algorithms, LSTt and LSTk, on this test set, and we also compared the results against our LTIU algorithm. We first measured the average size (normalized w.r.t.the size of the problem) of the stable marriages returned by our algorithms. All three algorithms find larger marriages when the number of ties increasesand when the incompleteness in preference lists decreases. In fact, with more ties and longer preference lists, there is less probability of having a blocking pair and more chances for singles to get married. For instance, Figure 7(a) shows the results for LSTk when \(n\) = 10 and \(k\) = 50%. The results for LSTt and LTIU are very similar. Only for \(p_{1}\) = 0.7-0.8 and high values of \(p_{2}\), LTIU finds slightly smaller marriages. Figure 7(b) shows a comparison of the three algorithms on problems of a size of 10 and 30. For \(n\) = 10, the size of the marriages vary at most only 0.02 comparing LSTk _versus_ LSTt (LTIU gives practically the same results as LSTt) when we vary the size of the problems. We can also notice that the size of the marriages tends to increase when the size of the problems increases. For instance, Figure 7(c) shows the results for LSTt, and it easy to see that, for the same values of the other parameters, it finds larger marriages as \(n\) increases. The same results are obtained by the other algorithms. We conjecture that the reason for this behavior is that, considering SMI instances, the probability of having a certain person in at least one preference list, say \(P_{l}\), is very high, even with small sizes and a lot of incompleteness. More precisely, the probability of having a person, \(p\), in at least one preference list in an SMI of size \(n\), denoted by \(P_{l}(n,p_{1})\), is \(1-p_{1}^{n}\). Moreover, the probability to be in exactly \(k\) lists is:  
\[\left[(1-p_{1})^{k}\cdot p_{1}^{n-k}\right]\binom{n}{k} \tag{1}\]  
Then, the probability to be in at least \(k\) lists is:  
\[\sum_{i=k}^{n}\left\{\left[(1-p_{1})^{i}\cdot p_{1}^{n-i}\right]\binom{n}{i}\right\} \tag{2}\]  
Finally, since our generator rejects problems with empty preference lists, in our test set, each person is always in at least one preference list. Thus, the probability to be in at least \(k\) lists becomes:  
\[P(n,p_{1},k)=\frac{\sum_{i=k}^{n}\left\{\left[(1-p_{1})^{i}\cdot p_{1}^{n-i} \right]\binom{n}{i}\right\}}{1-p_{1}^{n}} \tag{3}\]  
For example, Figure 8 shows how slowly \(P(n,p_{1},5)\) decreases when varying \(p_{1}\) for different values of \(n\). Thus, in general, the probability for a person to be in more than one preference list rises with the size of the problem. Therefore, having a perfect matching or a marriage with very high cardinality is more probable in bigger problems than in smaller ones. Figure 8: Probability for a person to be in at least five preference lists varying \(p_{1}\). Figure 7: Normalized average size of marriages for LSTk, LSTt and LTIU. (**a**) Normalized average size of marriages found by LSTk using \(k=50\%\) on Stable Marriage with Ties and Incomplete lists (SMTIs) of a size of 10; (**b**) normalized average size for LSTk, LSTt and LTIU on problems of size 10 and 30. Fixing \(p_{1}\) = 0.8, \(k=50\%\) and \(t=0.5\); (**c**) normalized average size for LSTt varying \(n\) and fixing \(p_{1}\) = 0.8 and \(t=0.5\).