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—most famously the medical residency match—residents rank hospitals, and hospitals rank residents. The standard Deferred Acceptance (DA) algorithm is used to find a "stable" matching where no pair of a resident and a hospital would both prefer to be matched with each other over their current assignments. However, hospital capacities (quotas) are usually fixed in advance, leading to a "welfare loss": popular hospitals must reject highly qualified residents simply because they lack seats.
If a policymaker has a small budget of extra seats (e.g., 10–30 seats to distribute across dozens of hospitals), determining the optimal allocation to maximize overall resident happiness is an NP-complete problem. Existing exact solvers are often too slow for large-scale real-world use, and simple greedy approaches frequently miss the best configurations.
Methods: Tree-Based Search Space Representation
The authors propose using Upper Confidence Tree (UCT), a variant of Monte Carlo Tree Search, to navigate the massive search space of potential capacity expansions. The key technical contribution lies in the representation of the "expansion space" as a tree to avoid redundancy and improve search efficiency.
As illustrated in Figure 3, three main structures were evaluated:
- Iterative Priority Tree (IPT): Enforces a specific ordering to prevent searching the same configuration multiple times.
- Batch Tree (BT): Allows allocating multiple seats to a single hospital in one step, drastically reducing the search tree's depth.
- Ordering Heuristics: The search is guided by ranking hospitals based on Popularity (Borda count) or Potential Envy (the number of residents who preferred a hospital but were rejected).
For every node explored, the algorithm runs the standard DA algorithm to evaluate the "cost" (total resident ranking) of that specific capacity setup. This "anytime" property allows the algorithm to provide the best configuration found so far if stopped at any moment.
Experimental Results
The researchers evaluated their approach using synthetic datasets (1,000 residents, 5–15 hospitals) and real-world data from the Japan Residency Matching Program (JRMP) for the Tokyo district (1,287 residents, 51 hospitals).
As shown in Figure 6, the Batch Tree (BT) variants consistently outperformed other methods:
- Near-Optimality: In almost all tests, BT variants found solutions with a negligible 0.02% to 0.1% gap from the true mathematical optimum.
- Speedup: The proposed MCTS method was 2 to 20 times faster than the state-of-the-art exact method (
Agg-Lin). - Scalability: On large synthetic instances where exact solvers timed out at the 1-hour mark, the MCTS method consistently found high-quality solutions within minutes.
Conclusion
By intelligently structuring the search space as a Batch Tree and utilizing UCT, this method provides a scalable solution for the capacity expansion problem in matching markets. While the current model assumes a standard matching framework, future work could extend this to handle complex distributional constraints or explore alternative search variants like Nested Monte-Carlo Search to further enhance performance.
Summary updated