Definition 1 (Marriage) Given an SM P of size n, a marriage M is a one-to-one matching of the men and the women. If a man m and a woman w are matched in M*, we write* M(m) = w and M(w) = m. Definition 2 (Blocking pair) Given a marriage M*, a pair* (m, w), where m *is a man* and w is a woman, is a blocking pair iff m and w are not partners in M, but m *prefers* w to M(m) and w *prefers* m to M(w).

Definition 3 (Stable Marriage) A marriage M *is stable iff it has no blocking pairs.*
A convenient and widely used SM representation is showed in Table 1, where each person is followed by his/her preference list in decreasing order.

| men's preference lists   | women's preference lists   |
|--------------------------|----------------------------|
| 1: 5 7 1 2 6 8 4 3       | 1: 5 3 7 6 1 2 8 4         |
| 2: 2 3 7 5 4 1 8 6       | 2: 8 6 3 5 7 2 1 4         |
| 3: 8 5 1 4 6 2 3 7       | 3: 1 5 6 2 4 8 7 3         |
| 4: 3 2 7 4 1 6 8 5       | 4: 8 7 3 2 4 1 5 6         |
| 5: 7 2 5 1 3 6 8 4       | 5: 6 4 7 3 8 1 2 5         |
| 6: 1 6 7 5 8 4 2 3       | 6: 2 8 5 4 6 3 7 1         |
| 7: 2 5 7 6 3 4 8 1       | 7: 7 5 2 1 8 6 4 3         |
| 8: 3 8 4 5 7 2 6 1       | 8: 7 4 1 5 2 3 6 8         |

Table 1: An example of an SM of size 8.

For example, Table 1 shows that man 1 prefers woman 5 to woman 7 to woman 1 and so on. It is known that, at least one stable marriage exists for every SM problem. For a given SM instance, we can define a partial order relation on the set of stable marriages.

Definition 4 (Dominance) Let M and M′be two stable marriages. M dominates M′iff every man has a partner in M *who is at least as good as the one he has in* M′.

Under the partial order given by the dominance relation, the set of stable marriages forms a distributive lattice [11]. Gale and Shapley give a polynomial time algorithm (GS) to find the stable marriage at the top (or bottom) of this lattice [2]. The top of such lattice is the male optimal stable marriage Mm, that is optimal from the men's point of view. This means that there are no other stable marriages in which each man is married with the same woman or with a woman he prefers to the one in Mm. The GS algorithm can also be used to find the female optimal stable marriage Mw (that is the bottom of the stable marriage lattice), which is optimal from the women's perspective, by just replacing men with women
(and vice versa) before applying the algorithm. A clear way to represent this lattice is a Hasse diagram representing the transitive reduction of the partial order relation. Figure 1 shows the Hasse diagram of the SM in Table 1.

A common concern with the standard Gale-Shapley algorithm is that it unfairly favors one sex at the expense of the other. This gives rise to the problem of finding "fairer" stable marriages. Previous work on finding fair marriages has focused on algorithms for optimizing an objective function that captures the happiness of both genders [7, 9]. A different approach is to investigate non-deterministic procedures that can generate a random stable marriage from the lattice with a distribution which is as uniform as possible.

In [1] the authors use a Markov chain approach to sample the stable marriage lattice.

More precisely, the edges of the lattice dictate exactly how to formalize the moves to walk from one stable marriage to another one, so that there are at most a linear number of moves