# Maximum stable matching/allocation

I checked some papers on two-side stable allocation/matching (marriage, worker/company, doctor/hospital), but has not found any literature on the following problem. Can someone point out if I missed some paper or help analyze the problem?

Consider two sets of nodes, $U$ and $V$. $f_u(v)$ is the non-negative (integer) preference function of $u\in U$ towards $v\in V$. Similarly, $f_v(u)$ is for $v\in V$ towards $u\in U$. Let $E\subseteq U\times V$ be a set of pairs. Each pair $(u,v)\in E$ indicates that we can never allocate one to the other.

$\pi$ is an allocation where $\pi(u)\in V$ is the node allocated to $u$ and $\pi(v)\in U$ is the node allocated to $v$. $\pi$ is weak-stable if there does not exist a pair ($u,v$) such that $f_u(v)>f_u(\pi(u))$ and $f_v(u)>f_v(\pi(v))$, which means that $u$ prefers $v$ to $\pi(u)$ and $v$ prefers $u$ to $\pi(v)$ simultaneously.

I want to compute a stable matching with maximum size, i.e. $maximize_{\pi}|\pi|$. Notice that, ties are allowed in any preference function.

• It seems to me that your problem is equivalent to MAX SMTI (Stable Marriage with Ties and Incomplete lists). Am I missing something? Oct 5 '16 at 16:02
• @HirokiYanagisawa Many thanks! I find the MAX SMTI problem in Hard Variants of Stable Marriage. They show that this problem is NP-hard and give a 2-approximation algorithm. Oct 5 '16 at 18:35
• @HirokiYanagisawa I see more than 200 papers citing it, I am wondering if you know any paper solves the weighted version, i.e. instead of simply maximizing $|\pi|$, I wish to $maximize_{\pi}\sum_{(u,v)\in \pi}f_u(v)$. I guess there will also be a 2-approximation on the weighted version. Oct 5 '16 at 18:36
• I notice that there is a paper Stable Marriage with Incomplete Lists and Ties. This paper works on minimizing a particular cost (or called preference index), but not the weight I wish to maximize -- the mathmatical things are different. Oct 5 '16 at 18:41
• I posted my comment in the answer section. Oct 6 '16 at 14:44