Then, to ensure gender neutrality in our algorithm3, in the next step we swap genders and do the same.

Due to their ability to restart, our algorithms have the PAC (probabilistically approximate complete property) [11]. That is, as their runtime goes to infinity, the probability that the algorithm returns an optimal solution goes to one. If the algorithm starts at a stable marriage, the algorithms will perform a random restart, which will end up in an optimal solution with probability greater than zero. On the other hand, if the algorithm starts from a non-stable marriage, we perform one or more steps in which we remove a blocking pair. This sequences of blocking pair removal have been shown to converge to a stable marriage with non-zero probability in the context of SMs with incomplete preference lists [12].

The proof of this result can be adapted to our context, as we have ties in the preference lists. Since a stable marriage can be reached with non-zero probability, and as we have argued above that from any stable marriage random restarting will reach an optimal solution with non-zero probability, the PAC property holds.

## 4 Experimental Setting

Problems are generated using the same method as in [4]. The generator takes three parameters: the problem's size n, the probability of incompleteness p1 and the probability of ties p2. Given a triple (n, p1, p2), a SMTI problem with n men and n women is generated, as follows:

1. For each man and woman, we generate a random preference list of size n, i.e., a permutation of n persons; 2. We then iterate over each man's preference list: for a man mi and for each women wj in his preference list, with probability p1 we delete wj from mi's preference list and delete mi from wj 's preference list. In this way we get a possibly incomplete preference list.

3. If any man or woman has an empty preference list, we discard the problem and go to step 1.

4. We iterate over each person's (men and women's) preference list as follows:
for a man mi and for each woman in his preference list, in position j ≥ 2, with probability p2 we set the preference for that woman as the preference for the woman in position j − 1 (thus putting the two women in a tie).
Note that this method generates SMTI problems in which the acceptance is symmetric. In fact, if a woman w is not acceptable for a man m, m is removed from w's preference list. This does not introduce any loss of generality because, even if such a removal is not performed, m and w cannot be matched together in any stable marriage.

Notice also that this generator will not construct a SMTI problem in which a man (resp., woman) has in his preference list only women (resp., men) who 3 Gender neutrality is usually considered a desirable feature in a stable marriage procedure.