Summer Internship Matching with Funding Constraints

We present a novel model that captures matching markets for summer internships at universities and other organizations that involve funding constraints. For these markets, we show that standard results from the literature such as the existence of stable matchings do not extend and in fact checking whether a stable matching exists is NP-complete which answers an open problem. Because of these challenges, we investigate how far stability requirements can be satisfied. One of our contributions is presenting a polynomial-time algorithm that satisfies a weaker notion of stability and allocates the budget in a fair manner.