# Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness

arXiv: https://arxiv.org/abs/1711.05144 · HTML: https://mlsanity.com/paper/1711.05144/

## Key facts

- Cited by 384 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Nov 2017.

## Built on by (most cited first, 30 of 384)

- [Bias and Fairness in Large Language Models: A Survey](https://mlsanity.com/paper/2309.00770/) (2023)
- [Towards Out-Of-Distribution Generalization: A Survey](https://mlsanity.com/paper/2108.13624/) (2021)
- [A survey on datasets for fairness-aware machine learning](https://mlsanity.com/paper/2110.00530/) (2021)
- [Auditing large language models: a three-layered approach](https://mlsanity.com/paper/2302.08500/) (2023)
- [Bias Mitigation for Machine Learning Classifiers: A Comprehensive Survey](https://mlsanity.com/paper/2207.07068/) (2022)
- [A Clarification of the Nuances in the Fairness Metrics Landscape](https://mlsanity.com/paper/2106.00467/) (2021)
- [Picking on the Same Person: Does Algorithmic Monoculture lead to Outcome Homogenization?](https://mlsanity.com/paper/2211.13972/) (2022)
- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Fast Model Debias with Machine Unlearning](https://mlsanity.com/paper/2310.12560/) (2023)
- [Batch Multivalid Conformal Prediction](https://mlsanity.com/paper/2209.15145/) (2022)
- [Practical Adversarial Multivalid Conformal Prediction](https://mlsanity.com/paper/2206.01067/) (2022)
- [Towards Intersectionality in Machine Learning: Including More Identities, Handling Underrepresentation, and Performing Evaluation](https://mlsanity.com/paper/2205.04610/) (2022)
- [A Unifying Theory of Distance from Calibration](https://mlsanity.com/paper/2211.16886/) (2022)
- [SocialCounterfactuals: Probing and Mitigating Intersectional Social Biases in Vision-Language Models with Counterfactual Examples](https://mlsanity.com/paper/2312.00825/) (2023)
- [Improving the Fairness of Chest X-ray Classifiers](https://mlsanity.com/paper/2203.12609/) (2022)
- [Fair and Optimal Classification via Post-Processing](https://mlsanity.com/paper/2211.01528/) (2022)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [Characterizing Intersectional Group Fairness with Worst-Case Comparisons](https://mlsanity.com/paper/2101.01673/) (2021)
- [Constrained Learning with Non-Convex Losses](https://mlsanity.com/paper/2103.05134/) (2021)
- [A Survey on Intersectional Fairness in Machine Learning: Notions, Mitigation, and Challenges](https://mlsanity.com/paper/2305.06969/) (2023)
- [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (2023)
- [Fairness for Unobserved Characteristics: Insights from Technological Impacts on Queer Communities](https://mlsanity.com/paper/2102.04257/) (2021)
- [Improving Fairness via Federated Learning](https://mlsanity.com/paper/2110.15545/) (2021)
- [Achieving Fairness at No Utility Cost via Data Reweighing with Influence](https://mlsanity.com/paper/2202.00787/) (2022)
- [When Does Optimizing a Proper Loss Yield Calibration?](https://mlsanity.com/paper/2305.18764/) (2023)
- [Exploring How Machine Learning Practitioners (Try To) Use Fairness Toolkits](https://mlsanity.com/paper/2205.06922/) (2022)
- [Making Decisions under Outcome Performativity](https://mlsanity.com/paper/2210.01745/) (2022)
- [On the Robustness of Sparse Counterfactual Explanations to Adverse Perturbations](https://mlsanity.com/paper/2201.09051/) (2022)

## Abstract (arXiv)

The most prevalent notions of fairness in machine learning are statistical definitions: they fix a small collection of pre-defined groups, and then ask for parity of some statistic of the classifier across these groups. Constraints of this form are susceptible to intentional or inadvertent "fairness gerrymandering", in which a classifier appears to be fair on each individual group, but badly violates the fairness constraint on one or more structured subgroups defined over the protected attributes. We propose instead to demand statistical notions of fairness across exponentially (or infinitely) many subgroups, defined by a structured class of functions over the protected attributes. This interpolates between statistical definitions of fairness and recently proposed individual notions of fairness, but raises several computational challenges. It is no longer clear how to audit a fixed classifier to see if it satisfies such a strong definition of fairness. We prove that the computational problem of auditing subgroup fairness for both equality of false positive rates and statistical parity is equivalent to the problem of weak agnostic learning, which means it is computationally hard in the worst case, even for simple structured subclasses. We then derive two algorithms that provably converge to the best fair classifier, given access to oracles which can solve the agnostic learning problem. The algorithms are based on a formulation of subgroup fairness as a two-player zero-sum game between a Learner and an Auditor. Our first algorithm provably converges in a polynomial number of steps. Our second algorithm enjoys only provably asymptotic convergence, but has the merit of simplicity and faster per-step computation. We implement the simpler algorithm using linear regression as a heuristic oracle, and show that we can effectively both audit and learn fair classifiers on real datasets.