## Appendix
If \(A_{i}\) is not accepted at college \(C_{j}\) with score vector \(\underline{t}\), but she has a score of at least \(t_{j}-1\), then she will go to \(C_{j}\) if and only if \(C_{j}A_{i}\in J\), because she got only one new chance. Therefore, \(F(P(\underline{t}^{\prime}))\cap E(C_{j})=(F(P(\underline{t}))\cup J)\cap E(C_{j})\). Other colleges cannot have new students; so, they stay valid. From \(F(P(\underline{t}))\cup J\), the scoring function, \(P_{G_{j}}\), for college \(C_{j}\) chooses score limit \(t_{j}\); therefore, it also chooses \(t_{j}\) from \(F(P(\underline{t}^{\prime})\). Therefore, \(\underline{t}^{\prime}\) is not valid. Now, assume that \(\underline{t}\) is valid and critical. Therefore, \(G(F(P(\underline{t})))=F(P(\underline{t}))\); so, \(G(F(P(\underline{t}))\cup J)\) accepts contracts in \(F(P(\underline{t}))\) (because contracts in \(J\) do not reach score limit \(\underline{t}\)). Therefore, \(P_{G}(E\setminus D_{F}(P(\underline{t})))\leq\underline{t}\). As before, \(\underline{t}^{\prime}=(t_{1},t_{2},\ldots,t_{j-1},t_{j}-1,t_{j+1},\ldots,t_{m})\). Function \(P\) is antitone; so  
\(P(\underline{t})\subseteq P(\underline{t}^{\prime})\). Since \(\mathcal{D}_{F}\) is monotone, \(\mathcal{D}_{F}(P(\underline{t}))\subseteq\mathcal{D}_{F}(P(\underline{t}^{ \prime}))\); so, \(E\setminus\mathcal{D}_{F}(P(\underline{t}))\supseteq E\setminus\mathcal{D}_{F }(P(\underline{t}^{\prime}))\supseteq F(P(\underline{t}^{\prime}))\). As \(\underline{t}\) is critical, \(F(P(t^{\prime}))\) is infeasible for college \(C_{j}\); so, \(E\setminus\mathcal{D}_{F}(P(\underline{t}))\), too, and we get \(P_{G_{j}}(E\setminus D_{F}(P(\underline{t})))\geq t_{j}\). This is valid for every college; therefore, \(P_{G}(E\setminus D_{F}(P(\underline{t})))=\underline{t}\). We did not use that \(\mathcal{G}\) is simple in the second direction and in the \"valid\" part of the first direction; so, these parts remain true for general bipartite graphs. Proof of Statement 6.: (i)\(\Rightarrow\) (ii) If \(\underline{t}\) is a fixed point, \(\underline{t}=P_{G}(E\setminus\mathcal{D}_{F}(P(\underline{t})))\), then let \(B=E\setminus\mathcal{D}_{F}(P(\underline{t})\). As we have seen in the proof of Statement 5, \(F(P(\underline{t}))=P(\underline{t})\cap(E\setminus\mathcal{D}_{F}(P( \underline{t}))=G(E\setminus\mathcal{D}_{F}(P(\underline{t})))=G(F(P( \underline{t}))\cup J)\); so, \(S=G(B)\). This gives \(\mathcal{D}_{G}(B)\cap B=\overline{G}(B)=J\). From the contracts outside \(B\), the set, \(B\), must dominate contracts under score limit \(\underline{t}\), since if colleges do not accept contracts from \(J\), then they will not accept other contracts with the same or lower scores. (It cannot happen that for some college, \(C_{j}\), all contracts in \(J\) have a score of \(t_{j}-2\) or less and some \(e\
otin B\) has a score of \(t_{j}-1\), because in that case, \(P_{G_{j}}\) would have chosen \(t_{j}-1\) and \(\underline{t}\) would not be stable.) Therefore, \(\mathcal{D}_{G}(B)\supseteq E\setminus P(\underline{t})\). Therefore, \(A=E\setminus\mathcal{D}_{G}(B)\subseteq P(\underline{t})\). Since \(F\) is path independent and \(S=F(P(\underline{t}))\subseteq A\subseteq P(\underline{t})\), we get that \(F(A)=S\). From Lemma 2, \(D_{F}(A)=D_{F}(P(t))=E\setminus B\); so, \(S\) is indeed four-stable. (i)\(\Leftarrow\) (ii)  
If \(S\) is four-stable, then there exists \(A,B\), such that \(F(A)=S,G(B)=S\). Let the score limit be \(\underline{t}=P_{G}(B)\). We want to know what \(P(\underline{t})\) is. It is sure that \(P(\underline{t})\cap B=S\), because \(P(P_{G}(B))\cap B=G(B)\), and since \(\mathcal{D}_{G}(B)=E\setminus A\) and \(\mathcal{D}_{G}(B)\supseteq E\setminus P(t)\), so \(A=E\setminus\mathcal{D}_{G}(B)\subseteq P(\underline{t})\). Since \(\mathcal{D}_{F}(A)=E\setminus B\), substitutability implies that dominated contracts will not be chosen from \(P(\underline{t})\), since \(A\subseteq P(\underline{t})\subseteq A\cup(E\setminus B)\). Therefore, \(\overline{F}(P(\underline{t}))\supseteq P(\underline{t})\setminus A\).