## 2 Related Work
### Stable Marriage Problem  
A stable marriage (SM) problem instance [1] consists of matching members of two different sets, usually called men and women. When there are \(n\) men and \(n\) women, the SM problem is said to have size \(n\). Each person strictly ranks all members of the opposite sex. The goal is to match the men with the women, so that there are no two people of the opposite sex who would both rather marry each other than their current partners. If there are no such pairs (called blocking pairs), the marriage is _\"stable\"_. **Definition 1** (Marriage): _Given an SM instance \(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 shown in Table 1, where each person is followed by his/her preference list in decreasing order. 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^{\prime}\) be two stable marriages. \(M\) dominates \(M^{\prime}\) iff every man has a partner in \(M\) who is at least as good as the one he has in \(M^{\prime}\)._ \begin{table}
\begin{tabular}{c c} \hline \hline
**Men’s preference lists** & **Women’s preference lists** \\ \hline
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 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: An example of a stable marriage (SM) instance of a size of eight. Under the partial order given by the dominance relation, the set of stable marriages forms a distributive lattice [5]. [PERSON] and [PERSON] give a polynomial time algorithm (GS) to find the stable marriage at the top (or bottom) of this lattice [2]. The top of such a lattice is the male optimal stable marriage, \(M_{m}\), which 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 \(M_{m}\). The GS algorithm can also be used to find the female optimal stable marriage, \(M_{w}\) (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 [10,11]. A different approach is to investigate non-deterministic procedures that can generate a random stable marriage from the lattice with a distribution that is as uniform as possible. In [40], the authors use a Markov chain approach to sample the stable marriage lattice.