## 3 Stability Concepts
### Generalized Score-Stability  
We can generalize the above framework, keeping the main property needed to ensure the existence of a stable solution, namely the loser-free property that allows us to extend the model in a way that is fairly generalized and has economically interesting choice functions. Let \(F\) be direct sum of substitutable choice functions of the applicants, and \(G\) is a direct sum of loser-free, substitutable choice functions of the colleges. Every college, \(C_{j}\), has a choice function, \(G_{j}\), over the contracts involving it, and \(G=G_{1}+\ldots G_{m}\). We say a set \(\{A_{i_{1}},A_{i_{2}},\ldots A_{i_{k}}\}\) of applicants is _feasible_ for college \(C_{j}\) if \(G_{j}(X)=X\) for the contract set \(X=\{A_{i_{1}}C_{j},A_{i_{2}}C_{j},\ldots A_{i_{k}}C_{j}\}\); otherwise, it is _infeasible_. Each contract, \(c\), has a score, \(s(c)\). **Lemma 3**. : _A choice function \(G:2^{E}\to 2^{E}\) is loser-free if and only if there exists a function \(P_{G}:2^{E}\to\mathbb{N}^{E}\), such that for every set \(A\subseteq E\) of contracts, \(P_{G}\) gives the score-limit, for which the accepted contracts above the score limit are exactly the set accepted by \(G(A)\)._  
Proof. : If \(G\) is loser-free, the set of accepted contracts from \(A\) are all above a score limit; let the maximal score limit they reach be \(P_{G}(A)\). On the other hand, if we have a given score limit by \(P_{G}\), no one can be missed out, while others with the same score get in; so, \(G\) must be loser-free. Let \(P:\mathbb{N}^{E}\to 2^{E}\) be a function, that codes the scores of the applicants: \(P(t)\) is the set of contracts above the score limit given by score vector \(\underline{t}\). \(P(\underline{t})=\{AC\in E:s(AC)\geq t(C)\}\). Therefore, \(P(\underline{0})=E\) and \(P\) is antitone on the scores: if \(\underline{t}_{1}\leq\underline{t}_{2}\), then \(P(\underline{t}_{1})\supseteq P(\underline{t}_{2})\). Note that \(P(P_{G}(A))\cap A=G(A)\) for every \(A\subseteq E\). There exists a score vector \(\underline{T}\) (a highest possible score of +1 for every college), where \(P(\underline{T})=\emptyset\). From contracts above the score limit, the students choose \(F(P(\underline{t}))\), and contract set \(G(F(P(\underline{t})))\) is acceptable for the colleges. Therefore, score vector \(\underline{t}\) is valid if and only if \(G(F(P(\underline{t})))=F(P(\underline{t}))\). The score vector, \(\underline{t}\), is critical if for any \(1\leq j\leq m\), the new score vector \((t_{1},t_{2},\ldots,t_{j-1},\)\(t_{j}-1,t_{j+1},\ldots,t_{m})\) is not valid for college \(C_{j}\), or \(t_{j}=0\). We call \(\underline{t}\) stable if it is both valid and critical. **Lemma 4**. : _If \(\underline{t}\) is valid, but \(\underline{t}^{\prime}=(t_{1},t_{2},\ldots,t_{j-1},t_{j}-1,t_{j+1},\ldots,t_{m})\) is not, then the only college that can get an infeasible set of students at score vector \(\underline{t}^{\prime}\) is college \(C_{j}\)._  
Proof. : The set of offered places increases at college \(C_{j}\) and stays unchanged at other colleges. For applicant \(A_{i}\), if she rejected a college, \(C_{k}\), earlier (where \(C_{k}\
eq C_{j}\)), she will also reject \(C_{k}\) when she has more choices, so colleges other than \(C_{j}\) cannot have too many students. With score limit \(\underline{t}\), the set of students going to college \(C_{k}\) is \(F(P(\underline{t}))\cap E(C_{k})\); denote it by \(Z\). Additionally, with score limit \(\underline{t}^{\prime}\), it is \(Z^{\prime}\). As we have seen, \(Z^{\prime}\subseteq Z\), and from the substitutability, \(G_{k}(Z)=Z\) implies \(G_{k}(Z^{\prime})=Z^{\prime}\). **Definition 13**. : We call a score vector \(\underline{t}\)\(C_{j}\)-_valid_, if it is acceptable for college \(C_{j}\), _i.e._, \(G_{j}(F(P(\underline{t})))=F(P(\underline{t}))\cap E(C_{j}))\). The following two lemmas help to understand how the set of the valid score vectors look:  
**Lemma 5**. : _Let \(\underline{t}\) and \(\underline{t}^{\prime}\) be two score vectors, and \(\underline{t}\) is \(C_{j}\)-valid.