TL;DR
This paper tackles the complex problem of matching medical interns to hospital positions in Israel, a system previously relying on a "Random Serial Dictatorship" lottery. The authors introduce a new, more efficient mechanism that aims to improve overall intern satisfaction while respecting a "Do No Harm" principle. A key contribution is a novel algorithm for handling "couples" (pairs of interns who must be matched together), which is crucial for real-world assignment problems with constraints.
What Problem Does This Paper Address?
The Israeli medical internship is a mandatory year-long program that all medical graduates must complete. Historically, this placement was determined by a lottery system known as "Random Serial Dictatorship" (RSD). While seemingly fair, RSD can be inefficient and doesn't always account for complex real-world constraints. The authors identified two main issues with the existing system:
- Inefficiency and Lack of "Do No Harm": The old system wasn't necessarily the most efficient, and there was no guarantee that the new system wouldn't make some participants worse off. The "Do No Harm" principle, a core requirement, means that everyone should be at least as well off (in expectation) with the new system as with the old one.
- Two-Body Problems (Couples): A significant portion of interns apply as "couples" (friends or partners who wish to be placed in the same hospital). The old system had specific rules for couples, and ensuring they are matched together in a new, efficient system presents a significant algorithmic challenge, often referred to as a "two-body problem" in assignment contexts.
The paper aims to redesign this matching system to be more efficient, fair (adhering to "Do No Harm"), and capable of handling the complexities of couples.
Methods
The authors developed a new assignment mechanism that moves away from a strict lottery to a more sophisticated probabilistic approach. Key methodological contributions include:
- Probabilistic Assignment Mechanism: Instead of a fixed assignment, the new mechanism generates a probability matrix where each intern has a certain probability of being assigned to each hospital. This matrix is then decomposed into a convex combination of deterministic assignments.
- "Do No Harm" Constraint Integration: The mechanism is designed to ensure that every intern is at least as well off (in terms of expected happiness, defined by a specific utility function) under the new system as they would be under RSD. This is achieved by incorporating this constraint directly into the optimization process.
- Handling Couples (Two-Body Problems): This is a central algorithmic innovation. The problem of decomposing a stochastic assignment matrix into deterministic assignments becomes NP-hard when couples must be matched together. The authors propose a polynomial-time approximation algorithm that finds a "good enough" decomposition, ensuring couples are matched together while minimizing deviation from the target probabilities. This algorithm involves a two-stage process: first, allocating couples, and then adjusting singles' allocations to fill remaining capacities.
- Empirical Evaluation: The algorithm's performance was evaluated using real-world data from the Israeli Medical Internship Match, as well as simulated data.
Datasets
- Israeli Medical Internship Match Data: The authors utilized anonymized preference data from the Israeli Ministry of Health, specifically focusing on data from the years 2010-2014. This dataset includes intern preferences for 23 hospitals. Preferences for foreign-trained doctors were also available up to 2012.
Key Insights and Ideas
- The "Do No Harm" Principle is Achievable: The paper demonstrates that it's possible to design a more efficient matching system while ensuring no participant is worse off. This is a crucial finding for designing fair and acceptable market mechanisms.
- Couples are a Major Algorithmic Hurdle: The presence of couples (or any form of complementarity constraints) significantly complicates standard assignment algorithms, turning what would be a tractable problem into an NP-hard one. This highlights the need for specialized algorithms for such scenarios.
- Approximation is Necessary and Effective: For the couples problem, an exact solution is computationally infeasible. The authors show that a polynomial-time approximation algorithm can provide a solution that is "tight" and performs well in practice, even if it doesn't achieve the absolute optimal outcome.
- Geographic Preferences Drive Intern Behavior: The analysis of intern preferences revealed a strong tendency for interns to rank hospitals geographically, suggesting that location is a significant factor in their decision-making.
- Foreign-Trained Doctors Have More Heterogeneous Preferences: Compared to Israeli-trained doctors, foreign-trained doctors exhibited more diverse preferences, which impacted their performance in the old RSD system.
Key Results
- Successful Redesign and Implementation: The proposed new mechanism was implemented for the Israeli Medical Internship Match in 2014 and has been used since, including for foreign-trained doctors.
- Improved Intern Rankings: The new mechanism led to improved average rankings for both Israeli and foreign-trained interns compared to the old RSD system.
- NP-Hardness of Couples Problem: The paper proves that determining whether a stochastic assignment matrix with couples can be decomposed into deterministic assignments is NP-hard.
- Approximation Algorithm Performance: The proposed approximation algorithm for the couples problem achieves an approximation ratio of $2/q$, where $q$ is the capacity of the smallest hospital. Empirical results on real and simulated data show that the algorithm performs significantly better than this theoretical bound, with deviations being much smaller in practice.
- Efficiency Gains: The new mechanism is more efficient than the previous lottery system.
Limitations and Future Work
- Trade-off Between Truthfulness and Efficiency: The authors acknowledge that their mechanism sacrifices some degree of truthfulness for efficiency. While they argue this is a necessary trade-off and manageable, it's an ongoing area of research.
- "Small" Probabilities: The analysis of the approximation algorithm's lower bound was primarily focused on the domain $P^{\ge C}$ (where singles outweigh couples in hospitals). Extending this to cases where probabilities are "small" remains an open problem.
- Generalizing to Larger Groups: The current algorithm handles couples. Extending it to handle larger groups (e.g., triplets) is a natural next step.
- Strategy-Proofness vs. Efficiency: The paper raises the question of a more principled way to balance strategy-proofness with efficiency, noting that their current approach doesn't explicitly pay an extra price for strategy-proofness beyond the DNH principle.
- Handling Parents: The paper discusses how parental benefits were voted out by students. Investigating how the algorithm would behave with a population that includes parents, and finding a principled way to handle them, is suggested.
- Couples in Different Hospitals within the Same City: The current algorithm assumes couples must be in the same hospital. Exploring approximation for couples in different hospitals within the same city is posed as an open question.
Summary updated