## 3 The New Algorithm for General Stable Marriage  
For the new algorithm we use the following terms, most of which are familiar to the reader. A man can be either a _lad_, or a _bachelor_, or an _old bachelor_. A lad or a bachelor can be either _active_ or _engaged_. If women \(w_{1}\) and \(w_{2}\) have the same priority on \(m\)'s list, and \(w_{1}\) is maiden but \(w_{2}\) is engaged, then \(m\)**prefers maiden**\(w_{1}\) to **engaged**\(w_{2}\). An engaged lad is **uncertain**, if his list contains a woman he prefers to his actual fiancee (this can happen, if there were two maidens with the same highest priority on \(m\)'s list, and \(m\) became engaged to one of them). A woman can be either _maiden_ or _engaged_. An engaged woman is **flighty**, if her fiance is _uncertain_. If there are two men, \(m_{1}\) and \(m_{2}\) with the same priority on a woman \(w\)'s list, and \(m_{1}\) is a lad, but \(m_{2}\) is a bachelor, then \(w\)**prefers bachelor**\(m_{2}\) to **lad**\(m_{1}\). At the beginning every man is a lad and every woman is a maiden. In the description of the algorithm, differences from GSA1 are set in boldface. _New Algorithm_  
While there exists an active man \(m\), he proposes to his favorite woman \(w\). If \(w\) accepts his proposal, they become engaged. If \(w\) rejects him, \(m\) deletes \(w\) from his list. When a woman \(w\) gets a new proposal from man \(m\), she always accepts this proposal, if she is a maiden **or a flighty woman**. She also accepts this proposal, if she prefers \(m\) to her current fiance. Otherwise she rejects \(m\). If \(w\) accepted \(m\), then she rejects her previous fiance, if there was one (breaks off her engagement), and becomes engaged to \(m\). If \(m\) was engaged to a woman \(w\) and later \(w\) rejects him, then \(m\) becomes active again, and deletes \(w\) from his list, **except if \(m\) is uncertain, in this case \(m\) keeps \(w\) on the list**. If the list of \(m\) becomes empty for the first time, he turns into a bachelor, his original list is recovered, and he reactivates himself. If the list of \(m\) becomes empty for the second time, he will turn into an old bachelor and will remain inactive forever. After the algorithm finishes, the engaged pairs get married and form matching \(M\). **Lemma 1**: _When a woman receives the first proposal, she becomes engaged, and will never become a maiden again. A woman can become flighty only after the first proposal she receives. After the second proposal a woman can never be flighty. If a woman changes her fiance, then she always prefers the new fiance to the previous one, except if she was flighty, when she may reject a preferred man, but in this case she remains on the rejected man's list._  
**Proof. ** The only statement that needs a proof is that after getting the second proposal a woman \(w\) cannot be flighty. However starting with the second proposal she gets every proposal as an engaged woman, so either she keeps her previous fiance, consequently she is not flighty, or her new fiance \(m\) cannot be uncertain. (If there is a maiden \(w^{\prime}\) on the list of \(m\) with the same priority as \(w\), then \(m\) would prefer \(w^{\prime}\) to \(w\), so he would propose to \(w^{\prime}\) first.) \(\Box\)  
**Lemma 2**: _The matching \(M\) given by the new algorithm is stable._  
**Proof. ** Suppose \(mw\) is a blocking pair. If \(w\) is maiden then she did not get any proposals, so \(m\) did not reach her when he processed his list, consequently he is engaged to a preferred woman \(w^{\prime}\) (though it can be the case that \(w^{\prime}\) is flighty and now \(m\) would prefer \(w\) to \(w^{\prime}\), but he does not strictly prefer her, so pair \(mw\) cannot be blocking). If \(m\) is not married then he is an old bachelor, consequently he proposed to \(w\) at least twice. By the previous lemma the priority of the fiance of woman \(w\) is monotonically increasing after the second proposal she got. So the husband of \(w\) cannot be strictly less preferred than \(m\).