Abstract

We analyze the Gale-Shapley matching problem within the context of Rawlsian justice. Defining a fair matching algorithm by a set of 4 axioms (Gender Indifference, Peer Indifference, Maximin Optimality, and Stability), we show that not all preference profiles admit a fair matching algorithm, the reason being that even this set of minimal axioms is too strong in a sense. Because of conflict between Stability and Maximin Optimality, even the algorithm which generates the mutual agreement match, paradoxically, has no chance to be fair.We then relax the definition of fairness (by giving preference to Stability over Maximin Optimality) and again find that some preference profiles admit a fair matching algorithm, while others still do not, but the mutual agreement algorithm now is fair under this definition.The paper then develops a test, which determines, for a given preference profile, whether a fair algorithm exists or not.