Discrimination in Algorithmic Decision Making: From Principles to Measures and Mechanisms

Incorporating nondiscrimination goals into the design of algorithmic decision making systems (or, classifiers) has proven to be quite challenging. These challenges arise mainly due to (i) the computational complexities involved in incorporating nondiscrimination goals, and (ii) inadequacy of existing measures to computationally capture discrimination in certain situations. The goal of this thesis is to tackle these two problems.

First, we aim to design mechanisms to incorporate two existing measures of discrimination, disparate treatment and disparate impact, into the design of well-known classifiers. To this end, we introduce a novel and intuitive mechanism of decision boundary covariance. This mechanism can be included into the formulation of any convex boundary-based classifier in the form of convex constraints without increasing the classifier’s complexity. It also allows for fine-grained control over the degree of (non)discrimination, often at a small cost in terms of accuracy.

Second, we propose alternative measures of discrimination that can avoid shortcomings of existing measures in certain situations. Our first proposed measure, disparate mistreatment, is useful in situations when the validity of historical decisions in the training data can be ascertained. The remaining two measures, preferred treatment and preferred impact, are useful in situations when feature and class distributions of different groups subject to the decision making are significantly different, and can additionally help reduce the cost of nondiscrimination. We extend our decision boundary covariance mechanism and incorporate the newly proposed nondiscrimination measures into the formulations of convex boundary-based classifiers, this time as convex-concave constraints. The resulting formulations can be solved efficiently using recent advances in convex-concave programming.