Abstract
This paper deals with two-sided matching with
budget constraints where one side (firm or hospital) can make monetary transfers (offer wages) to
the other (worker or doctor). In a standard model,
while multiple doctors can be matched to a single
hospital, a hospital has a maximum quota: the number of doctors assigned to a hospital cannot exceed
a certain limit. In our model, a hospital instead
has a fixed budget: the total amount of wages allocated by each hospital to 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 Hat-
field and Milgrom, so that it handles near-feasible
matchings that exceed each budget of the hospitals
by a certain amount. We then propose two novel
mechanisms that efficiently return such a nearfeasible matching that is stable with respect to the
actual amount of wages allocated by each hospital. In particular, by sacrificing strategy-proofness,
our second mechanism achieves the best possible
bound