## 3 Stability Concepts
### Dominating Stability  
In the original stable marriage model, a matching is stable, if it dominates every other contract; so, for every \(e=(m,w)\
otin S\), either \(\mu(m)>_{m}e\) or \(\mu(w)>_{w}e\). A natural generalization of the notion is dominating stability. In the article of [PERSON] and [PERSON] [6], they defined stable allocations similar to our dominating stability definition. They said that a doctor-hospital allocation is stable if there is no blocking contract set. Unfortunately, it turns out that for non-path-independent choice functions, a dominating stable solution might not exist. Although this is the direct generalization of the original stability notion of [PERSON] and [PERSON], it seems that in practical applications, this notion does not help too much. **Definition 7**. : We say that a contract set, \(X\), is _\(F\)-dominated_ by \(S\) if \(F(S\cup X)\cap X=\emptyset\). This means if the agent can choose from the union of sets \(S\) and \(X\), he will choose \(S\) or a subset of \(S\). Based on this, we introduce the dominating function:  
**Definition 8**. : For choice function \(F:2^{X}\to 2^{X}\), let _dominating function_:  
\[\mathcal{D}_{F}(A):=\{x\in X:x\
otin F(A\cup\{x\})\}\]  
denote the set of contracts \(F\)-dominated by \(A\). Note that \(\mathcal{D}_{F}(A)\cap A=\overline{F}(A)\). **Statement 2**. : _If \(F\) is a substitutable choice function, then \(\mathcal{D}_{\mathcal{F}}\) is monotone._  
Proof. : Let \(A\subseteq B\). If \(x\in\mathcal{D}_{F}(A)\) then \(x\
otin F(A\cup\{x\})\Rightarrow x\in\overline{F}(A\cup\{x\})\). Since \(F\) is substitutable, \(x\in\overline{F}(B\cup\{x\})\Rightarrow x\
otin F(B\cup\{x\})\) so \(x\in\mathcal{D}_{F}(B)\). Examples for choice functions and corresponding dominating functions:  
**Example 3**. : \(F_{1}=Q_{1}\)_: There are two students interested in the same college, with equal scores, but the quota is one. If someone applies alone, he is accepted, but if both of them apply, the college rejects both. \(F_{2}=Q_{2}\): There are two students applying for the same college, with equal scores. The quota is two, so everybody is accepted. \(F_{3}\): There are two students applying for the same college. \(a\) is better then \(b\), and the quota is one. Therefore, the college chooses \(a\)._  
The dominating function has some properties that will be useful later. **Lemma 1**. : _If \(F\) is substitutable and path independent, then \(F(A)=S\Leftrightarrow\mathcal{D}_{F}(S)\cap A=A\setminus S\). This means the set, \(A\setminus S\), is dominated by \(S\) if and only if each contract, \(c\in A\setminus S\), is dominated by \(S\)._  
**Lemma 2**. : _If \(F\) is substitutable, path independent and \(F(A)=S\), then \(\mathcal{D}_{F}(A)=\mathcal{D}_{F}(S)\)._  
**Definition 9**. : Subset \(S\) of \(E\) is _dominating stable_, if \(\mathcal{D}_{F}(S)\cup\mathcal{D}_{G}(S)=E\setminus S\). Therefore, every \(e\
otin S\) is either \(F\)-dominated or \(G\)-dominated by \(S\). **Remark 2**. : _If \(S\) is dominating stable, then \(F(S)=S=G(S)\), so the set, \(S\), is acceptable for both sides._  
Proof. : Suppose that \(s\in S\setminus F(S)\). Then, by definition, \(s\in\mathcal{D}_{F}(S)\), but \(\mathcal{D}_{F}(S)\subseteq E\setminus S\); a contradiction. For \(G\), a similar proof applies. **Example 4**. : _Men and women have strict preferences. \(F\) is the common choice function of men, and \(G\) is the common choice function of women, which choose the single best option for every player. If \(S\) is dominating stable, then from \(F(S)=S=G(S)\), set \(S\) is a matching, and for every \(e=mw\
otin S\), contract \(e\
otin F(S\cup\{e\})\) or \(e\
otin G(S\cup\{e\})\), so that one of \(m\) or \(w\) does not want to choose \(mw\) instead of his/her current marriage. Therefore, in this case dominating stability is equivalent to the original stable marriage definition of [PERSON] and [PERSON]._  
Note that even for substitutable \(F\) and \(G\), a dominating stable solution does not always exists. **Example 5**.