Capacity Modification in the Stable Matching Problem

We study the problem of capacity modification in the many-to-one stable matching of workers and firms. Our goal is to systematically study how the set of stable matchings changes when some seats are added to or removed from the firms. We make three main contributions: First, we examine whether firms and workers can improve or worsen upon changing the capacities under worker-proposing and firm-proposing deferred acceptance algorithms. Second, we study the computational problem of adding or removing seats to either match a fixed worker-firm pair in some stable matching or make a fixed matching stable with respect to the modified problem. We develop polynomial-time algorithms for these problems when only the overall change in the firms’ capacities is restricted, and show NP-hardness when there are additional constraints for individual firms. Lastly, we compare capacity modification with the classical model of preference manipulation by firms and identify scenarios under which one mode of manipulation outperforms the other. We find that a threshold on a given firm’s capacity, which we call its peak, crucially determines the effectiveness of different manipulation actions.

Authors

• Salil Gokhale IIT Delhi
• Samarth Singla Indian Institute of Technology Delhi
• Shivika Narang University of New South Wales
• Rohit Vaish Indian Institute of Technology Delhi

Keywords

• Stable matching
• Capacity modification
• Preference manipulation