Gradual (In)Compatibility of Fairness Criteria
  Impossibility results show that important fairness measures (independence,
separation, sufficiency) cannot be satisfied at the same time under reasonable
assumptions. This paper explores whether we can satisfy and/or improve these
fairness measures simultaneously to a certain degree. We introduce
information-theoretic formulations of the fairness measures and define degrees
of fairness based on these formulations. The information-theoretic formulations
suggest unexplored theoretical relations between the three fairness measures.
In the experimental part, we use the information-theoretic expressions as
regularizers to obtain fairness-regularized predictors for three standard
datasets. Our experiments show that a) fairness regularization directly
increases fairness measures, in line with existing work, and b) some fairness
regularizations indirectly increase other fairness measures, as suggested by
our theoretical findings. This establishes that it is possible to increase the
degree to which some fairness measures are satisfied at the same time -- some
fairness measures are gradually compatible.
