Near Feasible Stable Matchings with Complementarities Thành Nguyen ∗ and Rakesh Vohra†

The National Resident Matching program strives for a stable matching of medical students to teaching hospitals. With the presence of couples, stable matchings need not exist. For any student preferences, we show that each instance of a stable match-ing problem has a ‘nearby ’ instance with a stable matching. The nearby instance is obtained by perturbing the capacities of the hospitals. Specifically, given a reported capacity kh for each hospital h, we find a redistribution of the slot capacities k h sat-isfying |kh − k′h | ≤ 4 for all hospitals h and h kh ≤ k′h ≤ h kh + 9, such that a stable matching exists with respect to k′. Our approach is general and applies to other type of complementarities, as well as matchings with contracts