## 1 Introduction
We will later break up some ties, dividing the men in a tie into two groups, and we will say, that \(w\) prefers one group to the other. So there will be a case that \(w\)_prefers_\(m_{1}\) to \(m_{2}\), but she does not strictly prefer \(m_{1}\) to \(m_{2}\), and in this situation we mean that \(\mathrm{pri}(w,m_{1})=\mathrm{pri}(w,m_{2})\), but \(m_{1}\) is in the preferred group and \(m_{2}\) is not. If both of them are in the same group then we say \(m_{1}\) and \(m_{2}\) are _alike_ for \(w\). We define \(\mathrm{pri}(m,w)\) similarly. Of course, \(\mathrm{pri}(m,w)\) is not related to \(\mathrm{pri}(w,m)\). We represent these priorities in the figures by writing \(\mathrm{pri}(m,w)\) and \(\mathrm{pri}(w,m)\) close to the corresponding endvertex of edge \(mw\). For a man \(m\) we will modify his list in either of two ways. Sometimes we delete a woman from the list. Sometimes (at a given point, when his list is empty) we will restore the original list of \(m\). We mean by \"_favorite woman_\" of \(m\), the most preferred woman still on \(m\)'s list; if there are more alike women on the top of the list, we choose one of them arbitrarily. _Remark. The author apologizes that the text of this paper is not politically correct. Just like the one of [PERSON] and [PERSON] [3], or the phrases used in many other papers on this topic. It would indeed be possible to change the terminology, but we find this approach pretty well-mannered._  
Let \(M\) be a matching. If \(m\) is _matched_ in \(M\), or in other words, if \(m\) is _engaged_ then we denote \(m\)'s fiancee by \(M(m)\). Similarly we use \(M(w)\) for the fiance of an engaged woman \(w\). **Definition 1**: _A pair \(mw\) is blocking \(M\), if \(mw\in E\setminus M\) (they are an acceptable pair and they are not matched) and_  
* \(w\) _is either not engaged or_ \(w\) _strictly prefers_ \(m\) _to her fiance,_ **and**__
* \(m\) _is either not engaged or_ \(m\) _strictly prefers_ \(w\) _to his fiancee._  
**Definition 2**: _A matching is called stable if there is no blocking pair._  
While there may be objections to the connotations of these words, for simplicity we use the term \"**lad**\" to represent a man who still has some women on his list, whom he did not propose to so far, and we use the term \"**old bachelor**\" to represent a man who was rejected by all acceptable women and decides to become inactive forever. Moreover we use the term \"**maiden**\" to represent a woman who did not get any proposal so far. Later we need to use some other similar terms, defined there. It is well-known that every instance of the stable marriage problem has a stable matching, and it can be found in linear time. The celebrated algorithm of [PERSON] [3] is the following. (We give a precise definition of the algorithms, however in a rather informal format. We think that none the less this style can be somewhat annoying for people studying algorithms regularly, for the other part of the readers it helps understanding the essence of these simple algorithms). A man can be either a _lad_ or an _old bachelor_. A lad can be either _active_ or _engaged_. A woman can be either _maiden_ or _engaged_. At the beginning every man is an active lad and every woman is a maiden. _Algorithm GS_  
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. 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 a man \(m\) was engaged to a woman \(w\), and later \(w\) rejects him, then \(m\) becomes active again, and deletes \(w\) from his list. If the list of \(m\) becomes empty, he will turn into an old bachelor and will remain inactive forever.