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. This paper initiates the study of finding a stable many-to-one matching, under cardinal valuations, while satisfying fairness among the agents on either side. Specifically, motivated by several real-world settings, we focus on leximin optimal fairness and seek leximin optimality over many-to-one stable matchings. We first consider the special case of ranked valuations where all agents on each side have the same preference orders or rankings over the agents on the other side (but not necessarily the same valuations). For this special case, we provide a complete characterisation of the space of stable matchings. This leads to FaSt, a novel and efficient algorithm to compute a leximin optimal stable matching under ranked isometric valuations (where, for each pair of agents, the valuation of one agent for the other is the same). The running time of FaSt is linear in the number of edges. Building upon FaSt, we present an efficient algorithm, FaSt-Gen, that finds the leximin optimal stable matching for ranked but otherwise unconstrained valuations. The running time of FaSt-Gen is quadratic in the number of edges. We next establish that, in the absence of rankings, finding a leximin optimal stable matching is NP-Hard, even under isometric valuations. In fact, when additivity and non-negativity are the only assumptions on the valuations, we show that, unless P=NP, no efficient polynomial factor approximation is possible. When additivity is relaxed to submodularity, we find that not even an exponential approximation is possible.