Reserve Systems with Match-Specific Beneficiaries

Abstract

We study two-sided matching problems in which the designer regards certain participant--institution matches as socially desirable ('beneficiary matches') and seeks to promote such matches. This objective can conflict with maximizing the total number of matches. We introduce minimal cycles to characterize the complete non-domination frontier, where each point represents an allocation that cannot increase beneficary matches without sacrificing total matches. Our main results are (i) the frontier is concave, so each additional match costs weakly more beneficiary matches than the last, (ii) traversing from maximum total matches to maximum beneficiary matches on the frontier reduces total matches by at most half of the maximum total, (iii) the Repeated Hungarian Algorithm computes the entire frontier in polynomial time, and (iv) mechanisms that approximately satisfy a percentage requirement of beneficiary matches on the frontier can respect priority orderings and elicit eligibility in a strategy-proof manner, but no such mechanism is path-independent. These results enable rigorous evaluation of policies that promote beneficiary matches across diverse allocation contexts.