## Appendix  
Proof of Lemma 1.: If \(F(A)=S\), then for every \(x\in A\setminus S\), we have \(S\subset(S\cup\{x\})\subseteq A\). Therefore, by \(F\) path independence, \(F(S\cup\{x\})=S\); so \(\mathcal{D}_{F}(S)\supseteq A\setminus S\). Consequently, \(F(A)\cap\mathcal{D}_{F}(S)=A\setminus S\). If \(\mathcal{D}_{F}(S)\cap A=A\setminus S\), then \(\overline{F}(S\cup\{x\})=x\), for every \(x\in A\setminus S\); so, from substitutability, \(x\in\overline{F}(A)\). Thus, \(\overline{F}(A)\supseteq A\setminus S\), which means \(F(A)\subseteq S\). By the path independence of \(F\), we have \(F(A)\subseteq S\subseteq A\Rightarrow F(A)=F(S)=S\)  
Proof of Lemma 2.: We have seen that \(\mathcal{D}_{F}\) is monotone; hence \(\mathcal{D}_{F}(S)\subseteq\mathcal{D}_{F}(A)\). If \(x\in\mathcal{D}_{F}(A)\), then \(F(A\cup\{x\})\subseteq A\subseteq(A\cup\{x\})\); so \(F(A\cup\{x\})=F(A)=S\) by the path independency. Therefore, \(F(A\cup\{x\})\subseteq S\cup\{x\}\subseteq A\cup\{x\}\); hence \(F(S\cup\{x\})=F(A\cup\{x\})=S\). This means \(S\) dominates any \(x\in\mathcal{D}_{F}(A)\), _i.e._, \(\mathcal{D}_{F}(A)=\mathcal{D}_{F}(S)\). The proof of statement 3 is included in the proof of Theorem 11. Proof of Lemma 5.: If \(A_{i}\) is a student of \(C_{j}\) when the score vector is \(\underline{t}\) (_i.e._, \(A_{i}C_{j}\in F(P(\underline{t}))\)), then \(A_{i}\) can leave \(C_{j}\) at \(\underline{t}^{\prime}\) if she does not reach \(t^{\prime}_{j}\) or got a better opportunity at another college. If student \(A_{l}\) does not go to college \(C_{j}\) at the score vector, \(\underline{t}\), (\(A_{l}C_{j}\
otin F(P(\underline{t}))\)), then she will not go to \(C_{j}\) under score vector \(\underline{t}^{\prime}\), because if \(A_{l}\) does not reach \(t_{j}\), then she does not reach the higher limit,\(t^{\prime}_{j}\). If \(A_{l}\) reaches \(t_{j}\), but chooses better college \(C_{k}\) instead, since \(t^{\prime}_{k}\leq t_{k}\), she will stay in college \(C_{k}\). Therefore, the set of students assigned to \(C_{j}\) with \(\underline{t}^{\prime}\) is the subset of the set of students going to \(C_{j}\) under \(\underline{t}\). \((F(P(\underline{t}^{\prime}))\cap E(C_{j}))\subseteq(F(P(\underline{t}))\cap E (C_{j}))\) The choice function, \(G_{j}\), of college \(C_{j}\) is substitutable. Therefore, \(F(P(\underline{t}))\cap E(C_{j})\) is valid; then, a subset of it is also valid. Therefore, \(\underline{t}^{\prime}\) is \(C_{j}\)-valid. Proof of Lemma 6.: Let the set of contracts above score vectors \(\underline{t}^{1}\) and \(\underline{t}^{2}\) be \(P(\underline{t}^{1})=A\) and \(P(\underline{t}^{2})=B\). Then, \(P(t_{min})=A\cup B\). Suppose that \(t^{1}_{j}=t^{min}_{j}\) for college \(C_{j}\). Since \(A\subseteq A\cup B\), from substitutability \(\overline{F}(A)\subseteq\overline{F}(A\cup B)\). Considering the set of contracts of college \(C_{j}\), \(E(C_{j})\cap A=E(C_{j})\cap(A\cup B)\), _i.e._, \(C_{j}\) accepts the same set of contracts with score vector \(\underline{t}^{1}\) as with \(\underline{t}^{min}\). Therefore, \(E(C_{j})\cap F(A)\supseteq E(C_{j})\cap F(A\cup B)\). Since \(G\) is substitutable, if a set is valid, then its subset is also valid. \(G(E(C_{j})\cap F(A))=E(C_{j})\cap F(A)\) so \(\overline{G}(E(C_{j})\cap F(A))=\emptyset\). For a smaller set, \(\overline{G}(E(C_{j})\cap F(A\cup B))=\emptyset\); so, \((A\cup B)\) is also valid for college \(C_{j}\). In other words, if we change the score limit from \(\underline{t}^{1}\) to \(\underline{t}^{min}\), college \(C_{j}\) keeps its score limit, while other colleges may decrease it. Applicants may leave \(C_{j}\), but no new students will arrive to \(C_{j}\); so, score limit \(\underline{t}^{min}\) is \(C_{j}\)-valid. We can use the same argument for every college; therefore \(\underline{t}^{min}\) is valid. In the proofs of Theorems 5 and 6, we use the alternative versions of the score-decreasing/increasing algorithms, where in every step, a college decreases/increases its score limit only by one.