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 (wherethe 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.
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.
R
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
This paper initiates the study
A
, under cardinal valuations,
R
, having cardinal utilities. In particular,
on either side. Specifically, motivated by several real-world settings,
R
optimal
optimality over
R
In
We first consider
R
utilities
valuations
A
preference orders or
R
utilities)
valuations). For this special case
R
characterisation for
complete characterisation of
R
a novel algorithm, called FaSt, that finds the
FaSt, a novel and efficient algorithm to compute a
R
utilities (wherethe utilities from matching are the same across an edge
valuations (where, for each pair of agents, the valuation of one agent for the other is the same
R
Additionally, we provide
Building upon FaSt, we present
D
called
R
utilities
valuations
R
then
next
R
utilities
valuations
R
is the only assumption on the utilities
and non-negativity are the only assumptions on the valuations
R
polynomial time
efficient polynomial factor approximation is possible. When additivity is relaxed to submodularity, we find that not even an exponential