## 1 Introduction  
The stable marriage problem (SM) [1] is a well-known problem of matching men to women to achieve a certain type of \"stability\". Each person expresses a strict preference ordering over the members of the opposite sex. The goal is to match men to women so that there are no two people of the opposite sex who would both rather be matched with each other than with their current partners. The stable marriage problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, sailors to ships, primary school students to secondary schools, as well as in market trading. Surprisingly, such a stable marriage always exists, and one can be found in polynomial time. [PERSON] and [PERSON] give an algorithm, which is linear in the size of the input, to solve this problem based on a series of proposals of the men to the women (or _vice versa_) [2]. There are many variants of the traditional formulation of the stable marriage problem. Some of the most useful in practice include incomplete preference lists (SMI), which allow one to model unacceptability for certain members of the other sex, and preference lists with ties (SMT), which model indifference in the preference ordering. With an SMI problem, the goal is to find a stable marriage in which the married people accept each other. It is known that all solutions of an SMI problem have the same size (that is, number of married people) [3]. In SMT problems, instead, solutions are stable marriages where everybody is married. Both of these variants are polynomial to solve. In real world situations, both ties and incomplete preference lists may be needed. Unfortunately, when we allow both, the problem becomes NP-hard [4]. In an SMTI (Stable Marriage with Ties and Incomplete lists) problem, there may be several stable marriages of different sizes, and solving the problem means finding a stable marriage of maximum size. In this paper, we investigate the use of a local search approach to tackle both the classical and the NP-hard variants of the problem. In particular, when we consider the classical problem, we investigate the fairness of stable marriage procedures based on local search, _i.e._, we investigate how well these procedures sample the lattice of stable marriages. On the other hand, for SMTI problems, we focus on efficiency in terms of time and effectiveness at finding large stable marriages. Our algorithms are based on the same schema: they start from a randomly chosen marriage, and at each step, we move to a neighbor marriage by minimizing the distance to stability, which is measured by the number of unstable pairs. To avoid redundant computation due to the possibly large number of unstable pairs, we consider only those that are undominated, since their elimination minimizes the distance to stability. Random moves are also used, to avoid stagnation in local minima. The algorithms stop when they find a solution or when a given limit on the number of steps is reached. A solution for an SMTI instance is a perfect stable matching (that is, a stable marriage with no singles), whereas, for an SM instance, a solution is just a stable marriage. For the SM problem, we performed experiments on randomly generated problems with up to 500 men and women. It is interesting to notice that our algorithm always finds a stable marriage. Furthermore, its runtime behavior shows that the number of steps grows as little as \(O(n\log(n))\)[5]. We also tested the fairness of our algorithm at generating stable marriages, measuring how well the algorithm samples the set of all stable marriages. As it is non-deterministic, it should ideally return any of the possible stable marriages with equal probability. We measure this capability in the form of an entropy that should be as close to that of a uniform sample as possible. The computed entropy is about 70% of that of a uniform sample, and even higher on problems with small size.