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

Code for reproducing results in the paper "Anytime Capacity Expansion in Medical Residency Match by Monte Carlo Tree Search". Note that Gurobi license is required to solve linear programming problems and mixed integer programming problems.

About

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.

Installation

This code is written in Python 3. To install the required dependencies, execute the following command:

$ pip install -r requirements.txt

For Docker User

Build the container:

$ docker build -t mcts-capacity-expansion .

After build finished, run the container:

$ docker run -it mcts-capacity-expansion

Run Experiments

In order to compare the proposed algorithm to the existing algorithms via synthetic data experiments (w/o hospital-wise limits), execute the following command:

$ python run_synthetic_experiment_wo_college_wise_budgets.py --num_students=1000 --num_colleges=15 --budget=30 --correlation=0.4 --num_trials=10

In this experiment, the following options can be specified:

• --num_students: Number of residents.
• --num_colleges: Number of hospitals.
• --budget: Number of expansion slots.
• --correlation: Correlation level of student preferences. The default value is 0.0.
• --num_trial: Number of trials to run experiments. The default value is 10.

To evaluate the algorithms via synthetic data experiments with hospital-wise limits, execute the following command:

$ python run_synthetic_experiment_with_college_wise_budgets.py --num_students=1000 --num_colleges=15 --budget=30 --correlation=0.4 --num_trials=10

To evaluate the algorithms via real-data experiments, execute the following command:

$ python run_real_data_experiment.py --budget=30 --num_trials=10

Citation

If you use our code in your work, please cite our paper:

@inproceedings{abe2022mctsce,
  title     = {Anytime Capacity Expansion in Medical Residency Match by Monte Carlo Tree Search},
  author    = {Abe, Kenshi and Komiyama, Junpei and Iwasaki, Atsushi},
  booktitle = {Proceedings of the Thirty-First International Joint Conference on
               Artificial Intelligence, {IJCAI-22}},
  pages     = {3--9},
  year      = {2022}
}