Achieving Fairness as well as Stability in Matchings
Matching problems are ubiquitous, be it matching students to colleges, tasks to workers, offices to employees, or peoples to objects. is a fundamental property of any matching problem. Matching problems become complex due to personal preferences agents will have. Stability is a fundamental property of any solution to a matching problem. Stability guarantees that no two agents will be simultaneously happier if their allocations are changed. Fairness is another crucial property that guarantees that the solution satisfies an appropriate notion of fairness of allocation. We consider the important problem of achieving fairness in stable many-to-one matchings where students need to be matched to colleges. We observe that envy-freeness, which is a popular notion of stability, and its natural extensions are not compatible with stability. We show that the notion of leximin optimality, which is another popular measure of fairness, is able to ensure fairness to agents on either side. This study provides a comprehensive exploration of when the problem of finding the leximin optimal stable matching is computationally tractable.
Shivika Narang, Arpita Biswas, Y Narahari. On Achieving Leximin Fairness and Stability in Many-to-One Matchings. Proceedings of the 21st International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2022).