Near Feasible Stable Matchings with Complementarities

Abstract:The National Resident Matching program strives for a stable matchingof medical students to teaching hospitals. With the presence ofcouples, 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 stable matching. The nearby instance is obtained byperturbing the capacities of the hospitals. Our approach is generaland applies to other type of complementarities, as well as matchingswith side constraints and contracts.Joint work with Rakesh Vohra.