## Appendix
From \(F(A^{\prime}\cup\{b\})=S\), we get \(F(A\cup\{b\})\subseteq F(A\cup\{b\})\cup F(A^{\prime}\cup\{b\})\subseteq A\cup\{b\}\); so,  
Figure 7: Score-increasing algorithm. \(F(A\cup\{b\})=F(F(A\cup\{b\})\cup F(A^{\prime}\cup\{b\}))\). Using that \(F\) is path independent, from Theorem 3, \(b\in F(A\cup\{b\})=F(F(A\cup\{b\})\cup F(A^{\prime}\cup\{b\}))=F(A\cup\{b\})\cup(A^ {\prime}\cup\{b\}))=F(A^{\prime}\cup A\cup\{b\})\subseteq S\). Therefore, \(b\in S\); a contradiction. Let \(S\) and \(S^{\prime}\) be two different stable sets. Let four-stable pairs \((A,B)\) and \((A^{\prime},B^{\prime})\) correspond to stable sets \(S\) and \(S^{\prime}\), respectively. _(ii)_\((A,B)\leq(A^{\prime},B^{\prime})\Rightarrow S\leq_{F}S^{\prime}\). From the ordering of the four-stable pairs, \(S\subseteq A\subseteq A^{\prime}\) and \(S^{\prime}\subseteq A^{\prime}\); so, \(S\cup S^{\prime}\subseteq A^{\prime}\). Since \(F\) is path independent, from \(S^{\prime}=F(A^{\prime})\subseteq S\cup S^{\prime}\subseteq A^{\prime}\), we get that \(F(S\cup S^{\prime})=S^{\prime}\). _(iii)_\(S\leq_{F}S^{\prime}\), \(\Rightarrow(A,B)\leq(A^{\prime},B^{\prime})\). Suppose that \(B^{\prime}\
subseteq B\). Consequently, \(\exists\)\(b\), such that \(b\
otin B\), but \(b\in B^{\prime}\). From Lemma 2, \(\mathcal{D}_{F}(A)=\mathcal{D}_{F}(S)\); so:  
\(b\
otin B\Rightarrow b\in\mathcal{D}_{F}(A)=\mathcal{D}_{F}(S)\Rightarrow b \
otin F(S\cup\{b\})\)  
\(b\in B^{\prime}\Rightarrow b\
otin\mathcal{D}_{F}(A^{\prime})=\mathcal{D}_{F}( S^{\prime})\Rightarrow b\in F(S^{\prime}\cup\{b\})\)  
We know that \(F(S\cup S^{\prime})=S^{\prime}\); therefore, \(F(S\cup S^{\prime}\cup\{b\})\subseteq S^{\prime}\cup\{b\}\subseteq S\cup S^{ \prime}\cup\{b\}\). Since \(F\) is path independent, \(F(S\cup S^{\prime}\cup\{b\})=F(S^{\prime}\cup\{b\})\
i b\); hence \(b\in F(S\cup\{b\})\); a contradiction. Similarly, from \(B^{\prime}\subseteq B\), we get \(\mathcal{D}_{F}(B^{\prime})\subseteq\mathcal{D}_{F}(B)\) by the monotonicity of \(\mathcal{D}_{F}\) and \(E\setminus A^{\prime}\subseteq E\setminus A\); hence \(A^{\prime}\supseteq A\). _(iv) The stable sets form a lattice_. We have seen that there is an order preserving bijection between the stable sets and stable pairs. As stable pairs form a lattice, stable sets do, as well. Proof of Statement 5.: Let \(J=\{e\
otin P(\underline{t}):e\in F(\{e\}\cup P(\underline{t}))\}\) be the set of contracts that \(F\) prefers to \(F(P(\underline{t}))\). In other words, \(J=(E\setminus\mathcal{D}_{F}(P(\underline{t})))\setminus P(\underline{t})\); therefore, \(E\setminus\mathcal{D}_{F}(P(\underline{t}))=F(P(\underline{t}))\cup J\). (See Figure 8.)  
Suppose \(\underline{t}\) is a fixed point. Let \(B=E\setminus\mathcal{D}_{F}(P(\underline{t}))\), and we use that: \(P(P_{G}(B))\cap B=G(B)\). From this, \(P(\underline{t})\cap(E\setminus\mathcal{D}_{F}(P(\underline{t})))=P(P_{G}(E \setminus\mathcal{D}_{F}(P(\underline{t}))))\cap(E\setminus\mathcal{D}_{F}(P( \underline{t})))=G(E\setminus\mathcal{D}_{F}(P(\underline{t})))\). Since \(P(\underline{t})\cap(E\setminus\mathcal{D}_{F}(P(\underline{t})))=F(P(t))\), we get that \(G(F(P(\underline{t}))\cup J)=F(P(\underline{t}))\), and since \(G\) is substitutable, \(\overline{G}(F(P(\underline{t})))\subseteq\overline{G}(F(P(\underline{t})) \cup J)=J\). Therefore, \(G(F(P(\underline{t})))=F(P(\underline{t}))\); so, \(\underline{t}\) is valid. To prove that \(\underline{t}\) is critical, assume that college \(C_{j}\) lowers its score limit by one. Let  
\(\underline{t}^{\prime}=(t_{1},t_{2},\ldots,t_{j-1},t_{j}-1,t_{j+1},\ldots,t_{m})\). Then, at college \(C_{j}\), the accepted \(P(\underline{t})\) increases with some contracts. Now, we use that the graph is simple. If \(A_{i}C_{j}\in P(\underline{t})\), then applicant \(A_{i}\) will also be accepted under \(\underline{t}^{\prime}\).