Maximal Combinations of Fairness Definitions

The so-called ‘Impossibility Theorem’ for fairness definitions is one of the more striking research results with both theoretical and practical consequences, as it states that satisfying certain combinations of fairness definitions is impossible. To date, this negative result has not yet been complemented with a positive one: a characterization of which combinations of fairness notions are possible. This work aims to fill this gap by identifying maximal sets of commonly used fairness definitions for binary classification that can be simultaneously satisfied. The fairness definitions used are demographic parity, equal opportunity, predictive equality, predictive parity, false omission rate parity, overall accuracy equality and treatment equality. We conclude that in total 12 maximal sets of these fairness definitions are possible, among which are seven combinations of two definitions, and five combinations of three definitions. Our findings also shed light on the practical relevance and utility of each of these 12 maximal fairness definitions in various scenarios, regarding the accuracy of the classifier and ratios of false positives and false negatives, considering the base rates.