Placement With Assignment Guarantees and Semi-Flexible Capacities

We analyze an extension of the many-to-one placement problem, where some doctors are exogenously guaranteed a seat at a program, which defines a lower bound on their assignment. Respecting assignment guarantees, combined with the limited capacities of programs often violates fairness and leaves more preferred doctors unemployed. In pursuance of restoring fairness, a designer often has to deviate from the target capacities of programs, and imposing the traditional notion of fairness results in excessive deviations from the target capacities. In order to prevent excessive deviations, we introduce two notions that are tailored to the environment: q-fairness and avoiding unnecessary slots. Furthermore, we introduce the Assignment-Guarantees-Adjusted Mechanism (AGAM) and show that it is the unique strategy-proof mechanism that satisfies q-fairness and avoids unnecessary slots whilst respecting assignment guarantees. Furthermore, among the mechanisms that satisfy q-fairness and respect guarantees, AGAM minimizes the deviation from the target capacities.