## 1 Introduction  
In 1962, [PERSON] and [PERSON] [3] gave their famous simple deferred acceptance algorithm, which always finds stable matching in a two-sided market. If incomplete lists and ties are allowed in the preference lists, their algorithm still works, and gives some stable matching. However, in this case, we are usually interested in not only finding some stable matching, but one with maximum size. This problem (usually called MAX-SMTI) is APX-hard, and probably cannot be approximated within a factor of \(4/3\). [PERSON] [1] gave the first \(3/2\)-approximation using our previous \(3/2\)-approximation for the case, when ties are only on one side of the market [4]. In this paper, we give a much simpler algorithm than the one he gave, which is only a slight modification of the historical algorithm of [PERSON] and [PERSON]. It also gives \(3/2\)-approximation, but in **linear** time. The proof of the approximation ratio is uncomplicated, thus it serves as a good example for teaching purposes. We call a mechanism _natural_ if participants need not make any difficult computation and are not required to make illogical decisions. For several practice motivated models in Economics, natural mechanisms are more efficient than \"artificial\" ones. In this paper, we make difference between _global_ and _local_ algorithms. When we speak about a global algorithm, we assume that there is a centralized decision mechanism, having all possible information (here: the preference lists of all participants). A global algorithm is called linear time if the number of steps it takes is some constant times the size of the input (usually the total length of the preference lists). A local algorithm is quite restricted compared to a global algorithm. Here, every participant must have his/her own decision mechanism without having any global information. Besides his/her own information, a participant can only ask data from his/her acceptable partners. In real life, we have many circumstances when this is true for the participants. Therefore, designing a local information mechanism is an important goal. In this model, we assume everyone has his/her own list sorted at the beginning, and a local algorithm is called linear time if the number of steps any participant needs is some constant times the size of the input (length of the preference list) of that particular participant. We will give both linear time global and linear time local algorithms for approximating the maximum size stable marriage problem, moreover in our local algorithm every participant of the two-sided market will make only very natural and rational decisions. An instance of the stable marriage problem consists of a set \(U\) of men, a set \(W\) of women, and a preference list for each person; that is, a weak linear order (ties are allowed) of some participants (thus, in this paper, we are dealing with only the practical situation of incomplete lists) of the opposite gender. If \(m\in U\) and \(w\in W\), then a pair \(mw\) is called _acceptable_ if \(m\) is on the list of \(w\) and \(w\) is on the list of \(m\). We model acceptable pairs with a bipartite graph \(G=(U,W,E)\), (where \(E\) is the set of acceptable pairs; we may assume that if \(w\) is not on the list of \(m\) then \(m\) is also missing from the list of \(w\)). Note, that total length of the lists is proportional to \(|E|\). A _matching_ in this graph consists of mutually disjoint acceptable pairs. We store the weak order of the lists as priorities. For an acceptable pair \(mw\), let \(\mathrm{pri}(w,m)\) be an integer from \(1\) up to \(|U|\) representing the priority of \(m\) for \(w\). We say that \(w\in W\)_strictly prefers_\(m_{1}\in U\) to \(m_{2}\in U\) if both \(m_{1}\) and \(m_{2}\) are acceptable for \(w\), and \(\mathrm{pri}(w,m_{1})>\mathrm{pri}(w,m_{2})\). Ties are represented by equal priorities, e.g., if \(m_{1}\) and \(m_{2}\) are tied in \(w\)'s list, then \(\mathrm{pri}(w,m_{1})=\mathrm{pri}(w,m_{2})\).