The smi (smi) comprises a set of men \(U\)  and a set of women \(W\) . Each man ranks a subset of women in preference order and vice versa. A man \(m_i\) , finds a woman \(w_j\)  acceptable if \(w_j\)  appears on \(m_i\) 's preference list and vice versa. A matching \(M\)  in this context is an assignment of men to women such that no man or woman is assigned to more than one person, and if \((m_i,w_j) \in M\) , then \(m_i\)  finds \(w_j\)  acceptable and \(w_j\)  finds \(m_i\)  acceptable. An example smi instance \(I_0\)  with 8 men and women is taken from [1]}'s book [1]} and is given as Figure REF . Let \(M(m_i)\)  denote \(m_i\) 's assigned partner in \(M\) , and similarly, let \(M(w_j)\)  denote \(w_j\) 's assigned partner in \(M\) . A matching \(M\)  is stable if there is no man-woman pair \((m_i,w_j)\)  who would rather be assigned to each other than to their assigned partners in \(M\)  (if any). Denote by \(\mathcal {M}_S\) , the set of all stable matchings. By the “Rural Hospitals" Theorem [3]}, the same set of men and women are assigned in all stable matchings of \(\mathcal {M}_S\) . For the remainder of this paper, we assume smi instances have been pre-processed to remove men and women unassigned in any stable matching. Thus we can assume that the number of men and women is equal and we denote this number by \(n\) .
<FIGURE>