On Achieving Fairness and Stability in Many-to-One Matchings
share
Matching algorithms have been classically studied with the goal of finding stable solutions. However, in many important societal problems, the degree of fairness in the matching assumes crucial importance, for instance when we have to match COVID-19 patients to care units. We study the problem of finding a stable many-to-one matching while satisfying fairness among all the agents with cardinal utilities. We consider various fairness definitions from fair allocation literature, such as envy-freeness (EF) and leximin optimal fairness. We find that EF and its weaker versions are incompatible with stability, even under a restricted setting with isometric utilities. We focus on leximin optimal fairness and show that finding such a matching is NP-Hard, even under isometric utilities. Next, we narrow our focus onto ranked isometric utilities and provide a characterisation for the space of stable matchings. We present a novel and efficient algorithm that finds the leximin optimal stable matching under ranked isometric utilities. To the best of our knowledge, we are the first to address the problem of finding a leximin optimally fair and stable matching.
READ FULL TEXT