# Anytime Capacity Expansion in Medical Residency Match by Monte Carlo Tree Search

arXiv: https://arxiv.org/abs/2202.06570 · HTML: https://mlsanity.com/paper/2202.06570/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 37 references that are in the map.
- First posted on arXiv 14 Feb 2022.

## Builds on (most cited first, 1 of 1)

- [Anytime Discovery of a Diverse Set of Patterns with Monte Carlo Tree Search](https://mlsanity.com/paper/1609.08827/) (2016)

## Built on by (most cited first, 1 of 1)

- [An Efficient Algorithm for Thresholding Monte Carlo Tree Search](https://mlsanity.com/paper/2601.22600/) (2026)

## Abstract (arXiv)

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.