  With the growing adoption of machine learning (ML) systems in areas like law
enforcement, criminal justice, finance, hiring, and admissions, it is
increasingly critical to guarantee the fairness of decisions assisted by ML. In
this paper, we study the tradeoff between fairness and accuracy under the
statistical notion of equalized odds. We present a new upper bound on the
accuracy (that holds for any classifier), as a function of the fairness budget.
In addition, our bounds also exhibit dependence on the underlying statistics of
the data, labels and the sensitive group attributes. We validate our
theoretical upper bounds through empirical analysis on three real-world
datasets: COMPAS, Adult, and Law School. Specifically, we compare our upper
bound to the tradeoffs that are achieved by various existing fair classifiers
in the literature. Our results show that achieving high accuracy subject to a
low-bias could be fundamentally limited based on the statistical disparity
across the groups.
