# Special case of stable marriage

I have an instance of the stable marriage problem in which the first side $$S_1$$ has $$n_1$$ agents and the second side $$S_2$$ has $$n_2$$ agents with $$n_2$$ is very big in comparison to $$n_1$$. In addition, the agents of $$S_2$$ have the same preference list. The stability constraints can be modelled as follows:

$$1 \leq \sum\limits_{j'\in F^{\leq}_{j}(i)}x_{ij'} + \sum\limits_{i'\in C^{\leq}_{i}}x_{i'j};$$ $$i \in S_1$$, $$j \in S_2$$

where $$F^{\leq}_{j}(i)$$ is the set of agents of $$S_2$$ that $$i$$ ranks at the same level or better than $$j$$ and $$C^{\leq}_{i}$$ is the set of $$S_1$$ that are at the same level or better than $$i$$.

My question is: is there a way to model the stability constraints with a number of constraints in the order $$O(n_1)$$ rather than $$O(n_1 n_2)$$? because $$n_2$$ is very big and we already have a number of columns in order of $$O(n_1 n_2)$$.

• Are you interested specifically in this approach for solving this problem, or will you be happy with any algorithm? Apr 19, 2020 at 10:33
• any algorithm for this special case can be helpful for me Apr 19, 2020 at 10:51
• You are trying to find an algorithm to solve an "asymatic stable assignment"! Jan 20, 2021 at 12:24