Accuracy vs. Accuracy: Computational Tradeoffs Between Classification Rates and Utility

We revisit the foundations of fairness and its interplay with utility and efficiency in supervised learning settings where training labels are richer than binary outcomes, such as risk estimates (probabilities), individual types, or rankings. We introduce new notions of accurate classification rates for subgroups in the population, defined by comparing the induced positive-classification rates to those under the Bayes-optimal rich predictor. Our main contributions are computational impossibility results: we show that simultaneously achieving these rate-accuracy guarantees and natural desiderata such as calibration or loss minimization is, in some cases, computationally infeasible, even when training examples are labeled by the Bayes-optimal rich predictor. Unlike prior impossibility results in this area, these desiderata are simultaneously satisfied by the Bayes-optimal predictor, and each can be achieved efficiently in isolation.