## 1 Introduction  
An instance of the _stable marriage problem_[1] consists of the same number \(n\) of men and women, and each person's preference list. In a preference list, each person ranks all the members of the opposite sex in a strict order. A _matching_ is a set of \(n\) disjoint man-woman pairs in which each person appears exactly once. A _blocking pair_ for a matching \(M\) is a man-woman pair each of whom prefers the other to his/her partner in \(M\). A matching is _stable_ if it contains no blocking pair.  
It is known that there exists at least one stable matching in any instance, and one can be found by the Gale-Shapley algorithm (GS) in \(O(n^{2})\) time [1,2]. The stable matching found by GS is called the _man-optimal stable matching_ that has an extreme property that every man is assigned the best possible partner among all the stable matchings. In applications for asymmetric settings, such as assigning residents to hospitals or students to schools, it is common to formulate the problem by setting residents or students to the men's side, so that those people can receive benefit. Nevertheless, there are instances for which all (or almost all) men are assigned low-ranked partners even in the man-optimal stable matching, (e.g., a worst case instance for GS given in Figure 1, which originates from [2]). For such instances, the merit of using the man-optimal mechanism cannot be sufficiently exploited.  
To overcome this drawback, we consider the problem of improving the man-optimal stable matching by allowing small changes in preference lists. In this paper we first allow only one man's preference list to be changed, and consider optimization and decision variants. In the optimization variant, we are asked to find a man and a way of changing his list that cause the maximum improvement. In the decision variant, we ask if we can obtain a positive improvement. For both problems, we impose a restriction that no man should be assigned a worse partner than the man-optimal partner in the original instance. We show that these problems can be solved in time \(O(n^{3})\) and \(O(n^{2})\), respectively. We then extend the problem so that we are allowed to change \(k\) men's preference lists. We show that the optimization variant is W[1]-hard with respect to the parameter \(k\). We also give \(O(n^{2k+1})\)-time and \(O(n^{k+1})\)-time exact  
Figure 1: Worst case example for the Gale–Shapley algorithm for \(n=5\). Partners in the man-optimal stable matching are underlined. Each preference list is ordered from left to right in increasing order of the rank, _i.e._, the leftmost person is the most preferable and the rightmost person is the least preferable.  
algorithms for the optimization and decision variants, respectively. Finally, we show that the problems become easy when \(k=n\), _i.e._, we are allowed to change the preference lists of any number of men. We give \(O(n^{2.5}\log n)\)-time and \(O(n^{2})\)-time algorithms for the optimization and decision variants, respectively.  
Our problem can also be viewed as an issue of coalition strategy by men. Knowing all the preference lists, men are trying to maximize their total profit by submitting falsified preference lists, while bounding the number of such _liars_ and guaranteeing that no one becomes worse off. Results of this paper show the computational complexities of obtaining an optimal strategy depending on the number \(k\) of liars. Strategic issue in the stable marriage problem is an extensively studied topic (see [3] for example).