Stable Marriage Problem with Ties and Incomplete bounded length\n preference list under social stability

2016/01/14 by Ashish Shrivastava, Shrivastava, Ashish, C. Pandu Rangan +1
Economics, Econometrics and Finance · Social Sciences · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems #Gender, Labor, and Family Dynamics

paper · pdf · doi:10.48550/arxiv.1601.03523

openalex publication_date 2016/01/14 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28

Abstract

We consider a variant of socially stable marriage problem where preference\nlists may be incomplete, may contain ties and may have bounded length. In real\nworld application like NRMP and Scottish medical matching scheme such\nrestrictions arise very frequently where set of agents (man/woman) is very\nlarge and providing a complete and strict order preference list is practically\nin-feasible. In presence of ties in preference lists, the most common solution\nis weakly socially stable matching. It is a fact that in an instance, weakly\nstable matching can have different sizes. This motivates the problem of finding\na maximum cardinality weakly socially stable matching.\n

Related

• The stable marriage problem with ties and restricted edges
• Stable Marriage Problems with Ties and Incomplete Preferences: An Empirical Comparison of ASP, SAT, ILP, CP, and Local Search Methods
• Local search for stable marriage problems with ties and incomplete lists
• On the (Parameterized) Complexity of Almost Stable Marriage
• On the approximability of the stable marriage problem with one-sided ties