Pairwise Stability for Assignment Problem with Budget Constraints


    We study assignment problem with fixed budget constraints. Examples include assigning students to graduate schools when colleges have fixed budget, a faculty member with a fixed research fund hiring research assistants, a manager assigning workers to different projects where each project has fixed total benefit, assigning post-doctoral candidates to universities with fixed budgets etc. In graduate college admissions, each college has a fixed amount of money to distribute as stipends. Each college has strict preferences overs individual students that can be extended to the group of students. On the other hand, each student is matched with at most one college and receives a stipend from it. Each student has quasi-linear preferences over college-stipend bundles.
    Differently from earlier literature, in this paper, we specify a fixed budget for each college. One other different feature of our model is that colleges value money only to the extent that it allows them to enroll better students. We show that introducing budget constraint results in loosing some of the previous results in the literature. We define pairwise stability and show that a pairwise stable allocation always exists. We construct an algorithm. The rule defined through this algorithm always selects a pairwise stable allocation. This rule is also strategy-proof for students: no student can ever benefit from misrepresenting his preferences. Finally, we show that starting from an arbitrary allocation, there exist a sequence of allocations, each allocation being obtained from the previous one by "satisfying" a blocking pair, such that the final allocation is pairwise stable.