Near-Feasible Stable Matchings with Budget Constraints

Abstract

This paper examines two-sided matching with budget constraints where one side (a firm or hospital) can make monetary transfers (offer wages) to the other (a worker or doctor). In a standard model, while multiple doctors can be matched to a single hospital, a hospital has a {\em maximum quota}, thus, the number of doctors assigned to that hospital cannot exceed a certain limit. In our model, in contrast, a hospital instead has a {\em fixed budget}, that is, the total amount of wages allocated by each hospital to the doctors is constrained. With budget constraints, stable matchings may fail to exist and checking for the existence is hard. To deal with the nonexistence of stable matchings, we extend the "matching with contracts" model of Hatfield and Milgrom, so that it deals with \textit{near-feasible} matchings that exceed each hospital budget by a certain amount. We then propose two novel mechanisms that efficiently return such a near-feasible matching that is stable with respect to the actual amount of wages allocated by each hospital. Specifically, by sacrificing strategy-proofness, our second mechanism achieves the best possible bound of budget excess.