## 2 Preliminaries  
In the stable marriage model, there are \(n\) men: \(M=m_{1},\ldots m_{n}\); and women: \(W=w_{1},\ldots w_{n}\); each of them having a strict preference order on the members of the other gender. Let \(\mathcal{G}\) be a bipartite graph with color classes \(M\) and \(W\), and let \(E\)--the set of edges in \(\mathcal{G}\)--denote the possible marriages. In this work, _contract_ and _edge_ are synonyms of one another. They both describe a possible marriage or admission. The notion of a contract was introduced in [6]. Our model originally does not include money transfer or wages; the set of contracts is the set of edges of some underlying bipartite graph, \(\mathcal{G}\). However, we may allow multiple edges between two vertices of \(\mathcal{G}\), and by this, we can model discrete prices on the contracts, since discrete monetary transfers are equivalent to the possibility of multiple contracts. The notation \(w<_{m}w^{\prime}\) means that man \(m\) prefers woman \(w^{\prime}\) to \(w\). A subset, \(S\), of contracts is a _matching_ or _marriage scheme_ in \(\mathcal{G}\) if no vertex of \(\mathcal{G}\) is adjacent to more than one edge in \(S\). A matching \(S\subseteq E\) can also be described as an involution \(\mu:M\cup W\to M\cup W\), such that if \(m\) and \(w\) are married (that is, \((m,w)\in S\)), then \(\mu(m)=w\) and \(\mu(w)=m\), and for an unmatched agent, \(a\), we define \(\mu(a)=a\). A marriage scheme \(S\) is called _stable_ if, for any pair, \((m,w)\
otin S\), \(\mu(m)>_{m}w\) or \(\mu(w)>_{w}m\) holds. Men's preferences define a partial order on stable marriage schemes: \(S\geq_{M}S^{\prime}\), if \(\mu(m_{i})\geq_{m_{i}}\mu^{\prime}(m_{i})\), for all \(m_{i}\in M\) and \(S>_{M}S^{\prime}\), if \(S\geq_{M}S^{\prime}\) and there exists a man \(m_{i}\) such that \(\mu(m_{i})>_{m_{i}}\mu^{\prime}(m_{i})\). Similarly, there is another partial ordering, \(\geq_{W}\), defined by the women. It is well known that a marriage scheme is unanimously better for men, if and only if it is unanimously worse for women. **Definition 1**. : We call a stable matching \(S\)_male-optimal_ (_female-optimal_) if it is better for the men (women) than any other stable matching: \(S\geq_{M}S^{\prime}\) (\(S\geq_{W}S^{\prime}\)) for every stable matching, \(S^{\prime}\). A stable matching, \(S\), is _male-pessimal_ (_female-pessimal_) if \(S\leq_{M}S^{\prime}\) (\(S\leq_{W}S^{\prime}\)) for every stable matching, \(S^{\prime}\). The Gale-Shapley (or deferred acceptance) algorithm consists of rounds. In each round, every unengaged man proposes to the most-preferred woman to whom he has not yet proposed. Each woman then considers all her suitors and keeps her most preferred one and refuses the others. In the next round, all rejected men continue proposing to their next choice. The algorithm terminates if no new proposal occurs. This happens after at most \(const\cdot n^{2}\) steps, since every man proposes to every women at most once. The outcome of the algorithm is always a stable marriage scheme. **Theorem 1**. : _[_1_]_ _The stable marriage scheme given by the deferred acceptance algorithm is male-optimal and female-pessimal._  
[PERSON] in [7] attributes the observation to [PERSON] that stable marriages form a distributive lattice. **Theorem 2** ([PERSON]). : _Assume that \(S_{1}\) and \(S_{2}\) are two stable marriage schemes. Let every men choose the better of his partners in \(S_{1}\) and \(S_{2}\). This way, we get a stable matching that we denote by \(S_{1}\lor S_{2}\)._  
If the women choose their better partner, we get stable matching \(S_{1}\wedge S_{2}\). It follows that stable marriages form a lattice. Our models are based on the choice functions that we describe next. We shall see that \"traditional\" models nicely fit this non-traditional framework. **Definition 2**. : Set function \(F:2^{E}\to 2^{E}\) is called a _choice function_ if \(F(A)\subseteq A\) holds for any subset, \(A\), of ground set \(E\).