Optimal Capacity Modification for Stable Matchings with Ties

A team of computer scientists from the Indian Institute of Technology has published a significant theoretical advance in matching algorithms, addressing the 40-year-old Hospitals/Residents (HR) problem with ties. The paper, 'Optimal Capacity Modification for Stable Matchings with Ties,' focuses on strong stability—a desirable property where no resident-hospital pair would mutually prefer each other over their current match. The researchers prove that by optimally increasing hospital quotas (capacity), they can guarantee the existence of a strongly stable matching, solving a long-standing theoretical challenge.

They explore two optimization criteria: MINSUM (minimizing total capacity increase) and MINMAX (minimizing maximum increase per hospital). Their key breakthrough shows MINSUM admits a polynomial-time algorithm and establishes an analog of the famous rural hospitals theorem for this augmented setting. However, the cost version of MINSUM is NP-hard and inapproximable, while MINMAX itself is NP-hard. For practical cases where hospital preference lists have ties of length at most ℓ+1, they provide an efficient algorithm that increases quotas by at most ℓ and outputs the best matching from residents' perspective.

This theoretical work has immediate practical implications for modern AI systems. As AI agents become more prevalent in job markets, ride-sharing platforms, and resource allocation, they often operate with 'tied' preferences or equal rankings. The algorithms provide a mathematically sound way to adjust system capacities to ensure stable, envy-free matches exist. This prevents the common problem where no perfect matching satisfies all constraints, forcing platforms to make suboptimal or unfair assignments.