Near Feasible Stable Matchings with Complementarities

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 matching problem has a ’nearby’ instance with a table matching. The nearby instance is obtained by perturbing the capacities of the hospitals. Specifically, given a reported capacity for each hospital h, we find a redistribution of the slot capacities k¹h satisfying [kh –k¹h] ≤ 4 for all hospital 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 side constraints and contracts.