## 4 Algorithms
### Generalized Gale-Shapley Algorithm for Three-Stable and Four-Stable Sets  
For three-stable sets, we can generalize the Gale-Shapley algorithm to the case where both choice functions are substitutable, but they do not have to be path independent. It is a special case of the monotone function iteration that finds a fixed point of a monotone function. The following algorithm is the same as in [6]:  
Let \(F\) be the choice function of men/students, and \(G\) is the choice function of women/colleges. In the male-proposing version, let \(X_{1}=E\); men choose from all contracts and propose to\(E\setminus\ \overline{F}(E)\). Women choose \(G(F(E))\) and reject \(\overline{G}(F(E))\). In the second step, men choose from all contracts, except for the rejected ones: \(X_{2}=E\setminus\overline{G}(Y_{1})=E\setminus\overline{G}(F(X_{1}))\). They choose \(F(X_{2})\). The women take these contracts and the previously rejected contracts and choose from \(Y_{2}=F(X_{2})\cup\overline{G}(F(X_{1})=E\setminus\overline{F}(X_{2})\). Since \(G\) is substitutable, if a contract was rejected earlier, it will be rejected in this step, as well.  
Here, this algorithm differs from the original Gale-Shapley, since there, women choose only from their current proposals. However, if \(G\) is path independent, then \(G(Y_{2})\subseteq F(X_{2})\subseteq Y_{2}\) implies \(G(Y_{2})=G(F(X_{2}))\); so, putting back already refused proposals to the choice set does not change the outcome.  
A general step of the algorithm: for a given \(X_{i}\), let \(Y_{i}=E\setminus\overline{F}(X_{i})\), and let \(X_{i+1}=E\setminus\overline{G}(Y_{i})\).  
Define the following function, \(f\):  
\[f(X_{i},Y_{i})=(E\setminus\overline{G}(Y_{i}),E\setminus\overline{F}(E\setminus \overline{G}(Y_{i})))\]  
We can define a partial order on pairs \((A^{\prime},B^{\prime})\leq(A,B)\), if \(A^{\prime}\subseteq A\) and \(B^{\prime}\supseteq B\).  
Observe that \(f\) is monotone for this ordering. The iteration of this monotone function gives us a fixed pair \((X_{i},Y_{i})\), which corresponds to a three-stable pair \((A,B)\). If we start our iteration from pair \((X_{1},Y_{1})=(E,F(E))\), we get the male-optimal matching; if we start from \((X_{1},Y_{1})=(\emptyset,\emptyset)\), we get the female-optimal one.  
There is an alternative algorithm similar to the previous one:  
Define function \(f^{\prime}:2^{E}\times 2^{E}\to 2^{E}\times 2^{E}\) by:  
\[f^{\prime}(A,B):=(E\setminus(\overline{G}(B)),E\setminus(\overline{F}(A))\]  
If \(F\) and \(G\) are substitutable, then \(f^{\prime}\) is monotone for order \(\leq\), since, if \(B\) decreases, then \(\overline{G}(B)\) decreases; so \(E\setminus\overline{G}(B)\) increases. Similarly, if \(A\) increases, then \(E\setminus\overline{F}(A)\) decreases.  
As before, three-stable pairs are exactly the fixed points of \(f^{\prime}\). We start the iteration from \((A_{1},B_{1})=(E,\emptyset)\) for the men-optimal or with \((A_{1},B_{1})=(\emptyset,E)\) for the women-optimal solution.  
For four-stability, we define monotone function \(f^{\prime\prime}\) as follows:  
\[f^{\prime\prime}(A,B):=(E\setminus(\mathcal{D}_{G}(B)),E\setminus(\mathcal{D }_{F}(A)))\]  
If \(F,G\) are substitutable, then \(\mathcal{D}_{F},\mathcal{D}_{G}\) are monotone; therefore, \(f^{\prime\prime}\) is monotone for order \(\leq\). Fixed points of \(f^{\prime\prime}\) are four-stable pairs \((A,B)\), since \(A=E\setminus(\mathcal{D}_{G}(B))\), \(B=E\setminus(\mathcal{D}_{F}(A)))\).  
If we start the iteration of \(f^{\prime\prime}\) from \((A_{1},B_{1})=(E,\emptyset)\), we get a four-stable pair with the largest possible \(A\) and smallest possible \(B\); so, it is men-optimal. Starting pair \((A_{1},B_{1})=(\emptyset,E)\) leads to the women-optimal solution.