## Appendix
Using Lemma 5 again, if \(\underline{t}^{\prime}\) was valid, then \(\underline{t}_{0}^{\prime}\) would be \(C_{j}\)-valid. Therefore, \(\underline{t}^{\prime}\) is not valid; therefore, \(\underline{t}\) is indeed stable. To show that \(\underline{t}\) is minimal, suppose that there is a stable score limit, \(\underline{t}^{1}\), such that \(\underline{t}_{0}\leq\underline{t}^{1}\), but \(\underline{t}\
ot\leq\underline{t}^{1}\), _i.e._, \(t_{j}^{1}<t_{j}\) for some \(j\). Let:  
\[T^{\prime}=\{\underline{x}\in\mathbb{N}^{n}:x_{i}\leq t_{i}^{1}\quad\forall i \in\{1,\ldots m\}\}\]  
Since \(\underline{t}\
otin T^{\prime}\), but \(\underline{t}_{0}\in T^{\prime}\), there is a step such that when we leave \(T^{\prime}\), we move from \(\underline{w}^{1}\) to \(\underline{w}^{2}\). There is a college, \(C_{i}\), where \(\underline{w}_{i}^{1}=\underline{t}_{i}^{1}\). For other colleges, \(\underline{w}_{k}^{1}\leq\underline{t}_{k}^{1}\); so, by Lemma 5, \(\underline{w}^{1}\) was \(C_{i}\)-stable. Therefore, \(C_{i}\) does not want to increase its score limit. Therefore, \(\underline{s}_{A}\) is the smallest of all stable score vectors; so, every student gets accepted at as many colleges as possible, and they choose what is best for them. Therefore, \(\underline{s}_{A}\) is applicant-optimal. Figure 7 is showing a possible layout. Figure 6: Score-decreasing algorithm. Proof of Theorem 7.: In this proof, we return to the algorithm versions where colleges increase/lower their score limits as much as they can. We call the set of realized contracts at some score vector _enrollment_. Each of the \(n\) students can go to one of the \(m\) colleges or remain unmatched. Therefore, there are at most \(n^{m+1}\) possible enrollments. In the score-decreasing algorithm, the applicants always change to better. In the score-increasing algorithm, the students' positions get worse. Therefore, we cannot return to an earlier enrollment in these algorithms. If we order all enrollments according to the applicants' preference order, the longest chain contains \(n(m+1)\) enrollments. It goes from \"everyone gets the best college\" to \"everyone gets the worst college\". In the score-decreasing algorithm, college \(C_{i}\) may lower its score limit without changing the enrollment, taking the same students as before. If all \(m\) colleges do the same, we get the minimal score vector for that given enrollment; next time it came to college \(C_{i}\), it has to change to a different enrollment or stop. Therefore, in the algorithm, there can be at most \(m\) consecutive steps without changing the enrollment. Therefore, the number of steps is \(O(m^{2}n)\). In the score-increasing algorithm, every step will change the enrollment; hence, if \(C_{i}\) increase its score limit, the set of students going to \(C_{i}\) was infeasible before this step and feasible after the step. Thus, the number of steps is \(O(mn)\). Proof of Theorem 11.: _(i) First, we show that for any given stable set \(S\) there is a unique four-stable pair \((A,B)\)._  
Suppose that there are two different stable pairs for \(S\): \((A,B)\) and \((A^{\prime},B^{\prime})\). We can assume that there exists a \(b\) for which \(b\in B\), but \(b\
otin B^{\prime}\). Since \(S\subseteq B^{\prime}\), it follows that \(b\
otin S\). Moreover \(b\in F(A\cup\{b\})\), but \(b\
otin F(A^{\prime}\cup\{b\})\), because \(b\in F(A\cup\{b\})\Leftrightarrow b\
otin B\). By \(A^{\prime}\setminus S=\overline{F}(A^{\prime})\subseteq\overline{F}(A^{\prime} \cup\{b\})\), we get \(F(A^{\prime}\cup\{b\})\subseteq S\subseteq A^{\prime}\cup\{b\}\); hence \(F(A^{\prime}\cup\{b\})=S\). We know that \((A^{\prime}\cup\{b\})\setminus S=\overline{F}(A^{\prime}\cup\{b\})\) and \(A\setminus S=\overline{F}(A)\). Since \(F\) is substitutable, \(\overline{F}(A^{\prime}\cup A\cup\{b\})\) contains both sets, \((A^{\prime}\cup A\cup\{b\})\setminus S\subseteq\overline{F}(A^{\prime}\cup A \cup\{b\})\); so, \(F(A^{\prime}\cup A\cup\{b\})\subseteq S\).