  Fair classification has been a topic of intense study in machine learning,
and several algorithms have been proposed towards this important task. However,
in a recent study, Friedler et al. observed that fair classification algorithms
may not be stable with respect to variations in the training dataset -- a
crucial consideration in several real-world applications. Motivated by their
work, we study the problem of designing classification algorithms that are both
fair and stable. We propose an extended framework based on fair classification
algorithms that are formulated as optimization problems, by introducing a
stability-focused regularization term. Theoretically, we prove a stability
guarantee, that was lacking in fair classification algorithms, and also provide
an accuracy guarantee for our extended framework. Our accuracy guarantee can be
used to inform the selection of the regularization parameter in our framework.
To the best of our knowledge, this is the first work that combines stability
and fairness in automated decision-making tasks. We assess the benefits of our
approach empirically by extending several fair classification algorithms that
are shown to achieve the best balance between fairness and accuracy over the
Adult dataset. Our empirical results show that our framework indeed improves
the stability at only a slight sacrifice in accuracy.
