On Achieving Fairness and Stability in Many-to-One Matchings

The past few years have seen a surge of work on fairness in social choice literature. A major portion of this work has focused on allocation settings where items must be allocated fairly to agents with diverse preferences. In comparison, fairness in two-sided settings where agents have to be matched to other agents, with preferences on both sides, has received much less attention. In this paper, we explore the problem of finding a stable many-to-one matching while satisfying fairness among the agents, having cardinal utilities. In particular, we focus on leximin optimal fairness and seek leximin optimal many-to-one stable matchings. In the special case of ranked utilities where all agents on each side have the same rankings over the agents on the other side (but not necessarily the same utilities), we provide a characterisation for the space of stable matchings. This leads to a novel algorithm, called FaSt, that finds the leximin optimal stable matching under ranked isometric utilities (where the utilities from matching are the same across an edge). The running time of FaSt is linear in the number of edges. Additionally, we provide an efficient algorithm, called FaSt-Gen, that finds the leximin optimal stable matching for ranked but otherwise unconstrained utilities. The running time of FaSt-Gen is quadratic in the number of edges. We then establish that, in the absence of rankings, finding a leximin optimal stable matching is NP-Hard, even under isometric utilities. In fact, when additivity is the only assumption on the utilities, we show that, unless P=NP, no polynomial time approximation is possible.