<p>Your problem is equivalent to MAX SMTI (Stable Marriage with Ties and Incomplete lists).  You can find the current best approximation algorithm for MAX SMTI in the following paper:
<a href="http://www.mdpi.com/1999-4893/6/3/471/htm" rel="nofollow">Z. Kiraly, Linear Time Local Approximation Algorithm for Maximum
Stable Marriage, Algorithms 2013, 6, 471-484.</a></p>

<p>There are many papers on MAX SMTI, but unfortunately I am not aware of any paper that handles the weighted version of MAX SMTI.</p>

CC BY-SA 3.0
2016-10-06T14:44:11.650Z
2016-10-06T14:44:11.650Z
Hiroki Yanagisawa
<p>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?</p>

<p>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.</p>

<p>$\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)&gt;f_u(\pi(u))$ and $f_v(u)&gt;f_v(\pi(v))$, which means that $u$ prefers $v$ to $\pi(u)$ and $v$ prefers $u$ to $\pi(v)$ simultaneously.</p>

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

CC BY-SA 3.0
2016-10-05T16:02:32.723Z
It seems to me that your problem is equivalent to MAX SMTI (Stable Marriage with Ties and Incomplete lists).  Am I missing something?
Hiroki Yanagisawa
CC BY-SA 3.0
2016-10-05T18:35:27.363Z
@HirokiYanagisawa Many thanks! I find the MAX SMTI problem in [Hard Variants of Stable Marriage](http://www.dcs.gla.ac.uk/publications/PAPERS/5831/hvsm.pdf). They show that this problem is NP-hard and give a 2-approximation algorithm.
user2789928
CC BY-SA 3.0
2016-10-05T18:36:57.443Z
@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.
user2789928
CC BY-SA 3.0
2016-10-05T18:41:22.723Z
I notice that there is a paper [Stable Marriage with Incomplete Lists and Ties](https://pdfs.semanticscholar.org/348d/bc5f2243bfaa9ac6d155b5f67c01e1be3ac2.pdf). 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.
user2789928
CC BY-SA 3.0
2016-10-06T14:44:27.900Z
I posted my comment in the answer section.
Hiroki Yanagisawa
<np-hardness><gt.game-theory><matching><bipartite-graphs><stable>
Maximum stable matching/allocation
user2789928
# Maximum stable matching/allocation

(Asked by: username_0 on 2016-10-05)

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.

**Tags:** np-hardness, gt.game-theory, matching, bipartite-graphs, stable
> **Comments:**
> **username_1**: It seems to me that your problem is equivalent to MAX SMTI (Stable Marriage with Ties and Incomplete lists).  Am I missing something?  
> **username_0**: @HirokiYanagisawa Many thanks! I find the MAX SMTI problem in [Hard Variants of Stable Marriage](http://www.dcs.gla.ac.uk/publications/PAPERS/5831/hvsm.pdf). They show that this problem is NP-hard and give a 2-approximation algorithm.  
> **username_0**: @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.  
> **username_0**: I notice that there is a paper [Stable Marriage with Incomplete Lists and Ties](https://pdfs.semanticscholar.org/348d/bc5f2243bfaa9ac6d155b5f67c01e1be3ac2.pdf). 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.  
> **username_1**: I posted my comment in the answer section.  

---

## 1 answers

### Answer by username_1 on 2016-10-06. Score: 2 | Accepted answer

Your problem is equivalent to MAX SMTI (Stable Marriage with Ties and Incomplete lists). You can find the current best approximation algorithm for MAX SMTI in the following paper:
[Z. Kiraly, Linear Time Local Approximation Algorithm for Maximum
Stable Marriage, Algorithms 2013, 6, 471-484.](http://www.mdpi.com/1999-4893/6/3/471/htm)

There are many papers on MAX SMTI, but unfortunately I am not aware of any paper that handles the weighted version of MAX SMTI.


---

