Introduction

Applicants (residents) need to be placed into positions in an organization (hospital). Each applicant ranks all positions and each organization ranks all applicants. How can we place applicants in the positions such that 1) the final placement is stable and 2) the placement is optimal for applicants.

Properties

Our solution guarantees the following properties:

1. Stability: No resident remain unmatched if there is a hospital that ranks him better than all its’ already matched residents.
2. Efficiency:The solution is always the best (among stable solutions) for the residents.
3. Truthfulness: It is always better for the residents to be honest about their ranking of hospitals.

Algorithm Overview

We assume all agents have strict rankings. Residents apply to hospitals and are tentatively matched. A hospital rejects a proposal from a resident if their capacity is full and the proposing resident is ranked below all previously matched residents. If not, the hospital rejects a lowest ranked resident from the tentatively matched list, and accepts the proposing resident.

Not every resident is guaranteed to be matched to a hospital. The current algorithm does not handle couples or other special cases.

The redesign of the matching market for American physicians: Some engineering aspects of economic design
By: Alvin E. Roth and Elliott Peranson