## 2 Algorithm
### Description of Algorithm GS Modified  
Algorithm GS Modified given further on is to some extent modeled on the Gale-Shapley algorithm in which men propose to women on their lists and women dispose. In the course of running the algorithm, preference lists \(L_{m}\) will diminish and some additional lists \(L_{m}^{\prime}\) will be built. If at some point a free man \(m\) has a nonempty list \(L_{m}\), it means that he has not yet proposed to all women on his list \(L_{m}\) and potentially belongs to a blocking pair or a masculine dangerous path. If a free man \(m\) has a nonempty list \(L_{m}^{\prime}\), it means that he potentially belongs to a feminine dangerous path. Whenever it is man \(m\)'s turn to propose and \(L_{m}\
eq\emptyset\), he would like to get matched to the best possible woman on his list \(L_{m}\) without creating a blocking pair (as in GS algorithm) but also ensure that he does not belong to any masculine dangerous path. To this end, \(m\) proposes to the woman \(w\) to whom he has not yet proposed and who is as high on \(L_{m}\) as possible. If \(w\) is free or matched to someone worse for her than \(m\), she accepts \(m\) and rejects her current partner if she had one. If \(w\) is co-satellitic, which means that she is matched to some man \(m^{\prime}\) such that there is a free woman \(w^{\prime}\) who is equally good for \(m^{\prime}\) as \(w\), then it means that \(m\) currently belongs to a masculine dangerous path \((m,w,m^{\prime},w^{\prime})\). In this case \(w\) does not care whether \(m\) is better for her than \(m^{\prime}\) and accepts him while rejecting \(m^{\prime}\), and immediately afterwards \(m^{\prime}\) proposes to \(w^{\prime}\), who accepts him. This operation can be very well viewed as though \(m^{\prime}\) proposed to \(w^{\prime}\) without having proposed to \(w\) first, and some time later \(m\) proposed to \(w\). (Here edge \((m^{\prime},w)\) was special at the moment \(m^{\prime}\) proposed to \(w\) for the first time and that's why if \(m^{\prime}\) gets rejected by \(w^{\prime}\), he will propose to \(w\) again, because in this case \(w\) was not removed from \(L_{m^{\prime}}\). Let us notice that if \(m^{\prime}\) were allowed to remove \(w\) from his list \(L_{m^{\prime}}\) at the moment he proposed to \(w\) for the first time and the edge \((m^{\prime},w)\) was special, then after being rejected by \(w^{\prime}\) later on, he would not propose to \(w\) for the second time, and as a result a blocking pair involving \(m^{\prime}\) and \(w\) might arise.) To avoid multiple operations of this kind concerning one woman, we will assume that given a tie, a man proposes to unmatched women  
Figure 1: The description of a dangerous path and its two types: a feminine dangerous path and a masculine dangerous path. before proposing to matched ones. This ensures that in the above scenario, \(m\) cannot become satellite after being matched with \(w\). If a woman \(w\) to whom \(m\) proposes is matched to man \(m^{\prime}\) equally good for her as \(m\), and \(w\) is co-subsatellitic w.r.t. \(m\), meaning that \(m^{\prime}\) has some free women on his list, then at the current moment \(m\) belongs to a feminine dangerous path. What happens now is that \(w\) rejects \(m\) but \(m\) adds \(w\) to his list \(L^{\prime}_{m}\). (Woman \(w\) does not accept \(m\) because \(m\) may be subsatellitic as well.) In every other case \(w\) rejects \(m\). If man \(m\) has proposed to all women on his list \(L_{m}\) and remained free, but his list \(L^{\prime}_{m}\) is nonempty, he will propose to women on \(L^{\prime}_{m}\) starting from the top. If he proposes to \(w\), and \(w\) is matched to some man \(m^{\prime}\) who is equally good for her as \(m\), and additionally, \(m^{\prime}\) is subsatellitic, then \(w\) accepts \(m\) and rejects \(m^{\prime}\). Otherwise \(w\) rejects him. Let us notice that it cannot happen that \(w\) prefers \(m\) to \(m^{\prime}\), because man \(m\) had proposed to all women on his list \(L_{m}\) before proceeding to list \(L^{\prime}_{m}\subseteq L_{m}\).