A Comparative Study of Stability Representations for Solving Many-to-One Matching Problems with Utility-Weighted Objectives, Ties, and Incomplete Lists via Integer Optimization

We consider integer optimization models for finding stable solutions to many-to-one, utility-weighted matching problems with incomplete preference lists and ties. While traditional algorithmic approaches for the stable many-to-one matching problem, such as the Deferred Acceptance algorithm, offer efficient performance for the strict problem setting, adaptation to alternative settings often requires careful customization. Optimization-based approaches are free of the need to create customized algorithms for each unique context, and can readily accommodate such extensions as (incomplete) preference lists with ties; alternative and non-traditional objective functions; and side constraints including those that ensure stable matching outcomes free of waste. We explore the flexibility of optimization-based approaches in several ways. First, we introduce four new constraint sets that prevent justified envy, and a new system of constraints that prevents waste; taken together, they jointly ensure stable matching outcomes. Second, we create two algorithms to accelerate the generation of our proposed constraints. Third, we construct aggregate objective functions to reflect multiple hierarchical emphases by imposing a strict lexicographical order on the individual components. Fourth, we conduct comprehensive experiments to study the computational performance of our proposed optimization models and compare them with models from the extant literature under a variety of problem attributes. Our experiments reveal the circumstances under which each stability representation excels in terms of optimality criteria and computational efficiency on a variety of real and synthetic datasets. One such setting where our proposed stability representations excel includes the important context of when sufficient seats exist for applicants, such as school choice problems and hospital-residency matching.

Article

Download

View A Comparative Study of Stability Representations for Solving Many-to-One Matching Problems with Utility-Weighted Objectives, Ties, and Incomplete Lists via Integer Optimization