  Algorithmic fairness is of utmost societal importance, yet state-of-the-art
large-scale machine learning models require training with massive datasets that
are frequently biased. In this context, pre-processing methods that focus on
modeling and correcting bias in the data emerge as valuable approaches. In this
paper, we propose FairShap, a novel instance-level data re-weighting method for
fair algorithmic decision-making through data valuation by means of Shapley
Values. FairShap is model-agnostic and easily interpretable. It measures the
contribution of each training data point to a predefined fairness metric. We
empirically validate FairShap on several state-of-the-art datasets of different
nature, with a variety of training scenarios and machine learning models and
show how it yields fairer models with similar levels of accuracy than the
baselines. We illustrate FairShap's interpretability by means of histograms and
latent space visualizations. Moreover, we perform a utility-fairness study and
analyze FairShap's computational cost depending on the size of the dataset and
the number of features. We believe that FairShap represents a novel
contribution in interpretable and model-agnostic approaches to algorithmic
fairness that yields competitive accuracy even when only biased training
datasets are available.
