Abstract
This paper considers the capacity expansion problem in two-sided matchings, where the policymaker is allowed to allocate some extra seats as well as the standard seats. In medical residency match, each hospital accepts a limited number of doctors. Such capacity constraints are typically given in advance. However, such exogenous constraints can compromise the welfare of the doctors; some popular hospitals inevitably dismiss some of their favorite doctors. Meanwhile, it is often the case that the hospitals are also benefited to accept a few extra doctors. To tackle the problem, we propose an anytime method that the upper confidence tree searches the space of capacity expansions, each of which has a resident-optimal stable assignment that the deferred acceptance method finds. Constructing a good search tree representation significantly boosts the performance of the proposed method. Our simulation shows that the proposed method identifies an almost optimal capacity expansion with a significantly smaller computational budget than exact methods based on mixed-integer programming.
Introduction
In two-sided matching markets like the medical residency match, hospitals have a fixed number of "seats" or quotas. The classic Deferred Acceptance (DA) algorithm ensures a stable matching, but fixed capacities often force popular hospitals to reject highly qualified doctors, reducing overall social welfare. In practice, capacities can be flexible—hospitals might find extra funding or space for a few more residents.
The challenge is the Capacity Expansion Problem: given a budget of $B$ extra seats, how should they be distributed across hospitals to maximize the welfare of the residents? Previous research showed that finding the absolute optimal allocation is NP-complete. Existing solutions either rely on computationally expensive Mixed-Integer Programming (MIP) or fast but suboptimal greedy heuristics. This paper proposes an "anytime" algorithm that bridges this gap, providing high-quality solutions faster than MIP and more accurately than simple heuristics.
MCTS and Tree Representations
The authors propose using Upper Confidence Tree (UCT), a popular Monte Carlo Tree Search (MCTS) variant. The core idea is to treat the allocation of extra seats as a sequence of decisions in a search tree. Once a capacity vector is chosen at a leaf node, the standard DA algorithm is used to evaluate the "reward" (the total resident ranking).
The key innovation lies in the Tree Representation of the expansion space:
- Iterative Priority Tree (IPT): To avoid redundant paths (e.g., giving a seat to Hospital A then B is the same as B then A), a strict ordering based on hospital priority is enforced.
- Batch Tree (BT): Instead of adding seats one by one, each branch represents the total number of extra seats allocated to a specific hospital. This significantly reduces the depth of the tree.
- Hospital Ordering: Search efficiency is boosted by branching "important" hospitals earlier. Metrics used include Popularity (Borda count) and Potential Envy (how many residents would have preferred that hospital over their current match).
Experimental Evaluation
The researchers evaluated their approach on synthetic datasets (1,000 residents, 5-15 hospitals) and real-world data from the Japan Residency Matching Program (JRMP) 2007 (1,287 residents, 50 clustered hospitals).
Key Results
- Speed vs. Accuracy: The proposed UCT method (specifically the Batch Tree variant) found solutions nearly identical to the exact MIP solver (Agg-Lin) but was 2 to 20 times faster.
- Anytime Property: Unlike MIP solvers that might take hours to find a feasible solution for large instances, UCT provides a valid, improving solution almost immediately and refines it over time.
- Scalability: On large synthetic instances where the exact MIP solver failed to finish within an hour, UCT identified expansions that were significantly better than the best-known temporal values from the MIP solver.
Conclusion
By framing capacity expansion as a tree search and applying MCTS, the authors achieve near-optimal results with significantly reduced computational costs. The "Batch Tree" representation combined with "Envy-based" ordering allows the algorithm to focus on hospitals where residents are most likely to feel "envy," finding high-welfare expansions rapidly. Future work could explore "nearly stable" matchings or other distributional constraints, as well as alternative tree search algorithms like Nested Monte-Carlo Search.
Summary updated