## Appendix
These modified algorithms also find stable solutions, as one step of the score decreasing or score increasing can be regarded as several steps of this modified algorithm. From Lemma 5, if score vector \(\underline{t}\) is valid and \(\underline{t}^{\prime}=(t_{1},\ldots t_{j-1},t_{j}-k\ldots t_{m})\) is also valid, then for every \(1\leq k^{\prime}\leq k\), \(\underline{t}^{\prime\prime}=(t_{1},\ldots t_{j-1},t_{j}-k^{\prime},\ldots t_{ m})\) is valid (it is \(C_{j}\)-valid, because \(t^{\prime}\) is valid, and valid for other colleges, because \(t\) is valid). From the maximal/minimal property of the output solution, we see that the output of the algorithm does not depend on what order by which the colleges modify their score limits. Note that these algorithms may use \(m(M+1)\) steps, for example, if we start decreasing from \(\underline{t}_{C}:=(M+1,\ldots,M+1)\)), but only \((0,\ldots,0)\) is a stable score vector. Proof of Theorem 5.: From the algorithm, the fact that no college can decrease its score limit implies that \(\underline{t}\) is a stable vector. Suppose that there exist a stable score vector \(\underline{t}^{1}\leq\underline{t}_{0}\), where \(\underline{t}^{1}\
ot\leq\underline{t}\). Therefore, \(\underline{t}=(t_{1},\ldots t_{m})\) and \(\underline{t}^{1}_{\overline{t}}=(t^{1}_{1},\ldots t^{1}_{m})\), and \(t^{1}_{i}>t_{i}\) for some \(i\). Define the set:  
\[T=\{\underline{x}\in\mathbb{N}^{m}:x_{j}\geq t^{1}_{j}\quad\forall j\in\{1, \ldots m\}\}\]  
The algorithm starts from \(\underline{t}_{0}\in T\) and ends in \(\underline{t}\
otin T\); so, there is a step, when the score vector leaves \(T\): from score vector \(\underline{w}^{1}=(w_{1},w_{2},\ldots t^{1}_{k}\ldots w_{m})\in T\), we move to \(\underline{w}^{2}=(w_{1},w_{2},\ldots t^{1}_{k}-1\ldots w_{m})\
otin T\). Since this step is possible, both \(\underline{w}^{1}\) and \(\underline{w}^{2}\) are valid score vectors. We know that \(\underline{w}^{1}\geq\underline{t}^{1}\). Using Lemma 6, both \(\underline{t}^{1}\) and \(\underline{w}^{2}\) are valid; so, their minimum \(\underline{w}^{3}=(t^{1}_{1},t^{1}_{2},\ldots t^{1}_{k}-1\ldots t^{1}_{m})\) is also valid. Therefore, \(\underline{w}^{3}\) is stable, and it can be reached from \(\underline{t}^{1}\) by lowering the score limit of \(C_{k}\). Therefore, \(\underline{t}^{1}\) is not critical, hence it cannot be stable; a contradiction. Since every stable score vector are less than or equal to \(\underline{t}_{0}=(M+1,\ldots M+1)\), the biggest of all stable score vectors is \(\underline{s}_{C}\). Every student is accepted by fewer colleges than in any other stable admissions; so, \(\underline{s}_{C}\) is applicant-pessimal. Figure 6 is showing a possible layout. Proof of Theorem 6.: It follows from the algorithm that \(\underline{t}\) is valid. Suppose that it is not stable, _i.e._, there is a college, \(C_{j}\), such that \(\underline{t}^{\prime}=(t_{1},t_{2},\ldots,t_{j-1},t_{j}-1,t_{j+1},\ldots,t_{m})\) is still valid. If \(t_{j}^{0}\leq t_{j}-1\), look at the step where college \(C_{j}\) raises its score from \(t_{j}-1\) to \(t_{j}\), moving from score vector \(\underline{v}^{1}\) to \(\underline{v}^{2}\). Since the score limits in the algorithm always increase, \(\underline{v}^{1}\leq\underline{t}\) and \(v_{j}^{1}=t_{j}-1\); therefore, \(\underline{v}^{1}\leq\underline{t}^{\prime}\). We can use Lemma 5: score limit \(\underline{t}^{\prime}\) is valid, so \(\underline{v}^{1}\) is also \(C_{j}\)-valid. However, then, the algorithm would not have increased \(\underline{v}^{1}\) to \(\underline{v}^{2}\); a contradiction; Therefore, \(\underline{t}\) is stable. If \(t_{j}^{0}=t_{j}\), since \(\underline{t}_{0}\) is critical, the score vector \(\underline{t}_{0}^{\prime}=(t_{1}^{0},t_{2}^{0},\ldots,t_{j-1}^{0},t_{j}^{0} -1,t_{j+1}^{0},\ldots,t_{m}^{0})\) is not valid for \(C_{j}\). From \(\underline{t}_{0}\leq\underline{t}\), we get that \(\underline{t}_{0}^{\prime}\leq\underline{t}^{\prime}\).