The Study of Stable Marriage Problem with Ties and Incomplete Bounded Length Preference List under Social Stability

We consider a variant of the Stable Marriage Problem where preference lists of man/woman may be incomplete, may contain ties and may have bounded length in presence of a notion of social stability. In real world matching applications like NRMP and Scottish medical matching scheme such restrictions can arise very frequently where set of agents (man/woman) is very large and providing a complete and strict order preference list is practically in-feasible. In presence of ties in preference lists, there exist three different notion of stability, weak stability, strong stability and super stability. The most common solution is to produce a weakly stable matching. It is a fact that in an instance of Stable Marriage problem with Ties and Incomplete list (SMTI), weakly stable matching can have different sizes. This motivates the problem of finding a maximum cardinality weakly socially stable matching.

In this paper, we find maximum size weakly socially stable matching for a special instance of Stable Marriage problem with Ties and Incomplete bounded length preference list under Social Stability. The motivation to consider this instance is the known fact, finding maximum size weakly socially stable matching in any larger instance of this problem is NP-hard.