  The many-to-one stable matching problem provides the fundamental abstraction
of several real-world matching markets such as school choice and
hospital-resident allocation. The agents on both sides are often referred to as
residents and hospitals. The classical setup assumes that the agents rank the
opposite side and that the capacities of the hospitals are fixed. It is known
that increasing the capacity of a single hospital improves the residents' final
allocation. On the other hand, reducing the capacity of a single hospital
deteriorates the residents' allocation. In this work, we study the
computational complexity of finding the optimal variation of hospitals'
capacities that leads to the best outcome for the residents, subject to
stability and a capacity variation constraint. First, we show that the decision
problem of finding the optimal capacity expansion is NP-complete and the
corresponding optimization problem is inapproximable within a certain factor.
This result holds under strict and complete preferences, and even if we
allocate extra capacities to disjoint sets of hospitals. Second, we obtain
analogous computational complexity results for the problem of capacity
reduction. Finally, we study the variants of these problems when the goal is to
maximize the size of the final matching under incomplete preference lists.

Computational Complexity;Computer Science and Game Theory