  Fairness is increasingly recognized as a critical component of machine
learning systems. However, it is the underlying data on which these systems are
trained that often reflect discrimination, suggesting a database repair
problem. Existing treatments of fairness rely on statistical correlations that
can be fooled by statistical anomalies, such as Simpson's paradox. Proposals
for causality-based definitions of fairness can correctly model some of these
situations, but they require specification of the underlying causal models. In
this paper, we formalize the situation as a database repair problem, proving
sufficient conditions for fair classifiers in terms of admissible variables as
opposed to a complete causal model. We show that these conditions correctly
capture subtle fairness violations. We then use these conditions as the basis
for database repair algorithms that provide provable fairness guarantees about
classifiers trained on their training labels. We evaluate our algorithms on
real data, demonstrating improvement over the state of the art on multiple
fairness metrics proposed in the literature while retaining high utility.
