The Possibility of Fairness: Revisiting the Impossibility Theorem in Practice
Open accessThe DOI matches its Crossref record; 39 of the 39 references it cites were found in a registry or an index.
Abstract
The “impossibility theorem” — which is considered foundational in algorithmic fairness literature — asserts that there must be trade-offs between common notions of fairness and performance when fitting statistical models, except in two special cases: when the prevalence of the outcome being predicted is equal across groups, or when a perfectly accurate predictor is used. However, theory does not always translate to practice. In this work, we challenge the implications of the impossibility theorem in practical settings. First, we show analytically that, by slightly relaxing the impossibility theorem (to accommodate a practitioner’s perspective of fairness), it becomes possible to identify abundant sets of models that satisfy seemingly incompatible fairness constraints. Second, we demonstrate the existence of these models through extensive experiments on five real-world datasets. We conclude by offering tools and guidance for practitioners to understand when — and to what degree — fairness along multiple criteria can be achieved. This work has an important implication for the community: achieving fairness along multiple metrics for multiple groups (and their intersections) is much more possible than was previously believed.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“Moreover, the reviewed literature has documented extensively the limitations of a technical-only perspective in algorithmic bias and discrimination [36,81], the importance of sociotechnical views of bias [4], the interdependence between technical and sociotechnical views in auditing of algorithmic systems [31], and the limitations of operationalizing technical measures in non-AI contexts [7,19].”
From A Framework for Assurance Audits of Algorithmic Systems (2024) · cites this paper as [4]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Mapping the Margins: Intersectionality, Identity Politics, and Violence against Women of Color
Crenshaw, K. (1991) · Stanford Law Review · doi:10.2307/1229039 · Cited by 32,792
A Survey on Bias and Fairness in Machine Learning
Mehrabi, N., Morstatter, F., Saxena, N., Lerman, K., & Galstyan, A. (2022) · ACM Computing Surveys · doi:10.1145/3457607 · Cited by 5,812 · cited 1×
“In response to the complex and nuanced nature of fairness, researchers have defined dozens of fairness metrics, or mathematical assessments of an algorithm’s prejudice, that address different aspects of fairness [7, 9, 11, 16, 25, 38, 44, 54, 59, 64].”
BackgroundA Survey on Bias and Fairness in Machine Learning
Mehrabi, N., Morstatter, F., Saxena, N., Lerman, K., & Galstyan, A. (2019) · arXiv · doi:10.48550/arxiv.1908.09635 · Cited by 5,812
Programming with linear fractional functionals
Charnes, A., & Cooper, W. W. (1962) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800090303 · Cited by 2,936
Fair prediction with disparate impact: a study of bias in recidivism prediction instruments
Chouldechova, A. (2017) · Big Data · doi:10.1089/big.2016.0047 · Cited by 2,159
Bellamy, R. K. E., Dey, K., Hind, M., Hoffman, S. C., Houde, S., Kannan, K., Lohia, P., Martino, J., Mehta, S., Mojsilovic, A., et al. (2018) · arXiv · doi:10.48550/arxiv.1810.01943 · Cited by 1,581 · cited 1×
“In response to the complex and nuanced nature of fairness, researchers have defined dozens of fairness metrics, or mathematical assessments of an algorithm’s prejudice, that address different aspects of fairness [7, 9, 11, 16, 25, 38, 44, 54, 59, 64].”
BackgroundInherent trade-offs in the fair determination of risk scores
Kleinberg, J., Mullainathan, S., & Raghavan, M. (2017) · Schloss Dagstuhl – Leibniz-Zentrum für Informatik · doi:10.4230/lipics.itcs.2017.43 · Cited by 943 · cited 8×
“1 (Impossibility Result Variation [15] [37]).”
BackgroundInfluentialInherent Trade-Offs in the Fair Determination of Risk Scores
Kleinberg, J., Mullainathan, S., & Raghavan, M. (2016) · arXiv · doi:10.48550/arxiv.1609.05807 · Cited by 941 · cited 8×
“1 (Impossibility Result Variation [15] [37]).”
BackgroundInfluentialYeh, I.-C., & Lien, C.-H. (2009) · Expert Systems with Applications · doi:10.1016/j.eswa.2007.12.020 · Cited by 885
Research works printed but not linked: 22
- Toon Calders and Sicco Verwer . 2010. Three naive Bayes approaches for discrimination-free classification. Data mining and knowledge discovery 21, 2 ( 2010 ), 277–292. Toon Calders and Sicco Verwer. 2010. Three naive Bayes approaches for discrimination-free classification. Data mining and knowledge discovery 21, 2 (2010), 277–292.
- A. Charnes and W.W. Cooper. 1962. Programming with linear fractional functionals. Naval Research Logistics Quarterly 9(3-4) (1962) 181-186. https://doi.org/10.1002/nav.3800090303 · DOI · Paper page
- Catherine D’Ignazio and Lauren F Klein . 2020. Data feminism . MIT Press . Catherine D’Ignazio and Lauren F Klein. 2020. Data feminism. MIT Press.
- Sorelle A Friedler , Carlos Scheidegger , Suresh Venkatasubramanian , Sonam Choudhary , Evan P Hamilton , and Derek Roth . 2019 . A comparative study of fairness-enhancing interventions in machine learning . In Proceedings of the conference on fairness, accountability, and transparency. 329–338 . Sorelle A Friedler, Carlos Scheidegger, Suresh Venkatasubramanian, Sonam Choudhary, Evan P Hamilton, and Derek Roth. 2019. A comparative study of fairness-enhancing interventions in machine learning. In Proceedings of the conference on fairness, accountability, and transparency. 329–338.
- Andreas Fuster , Paul Goldsmith-Pinkham , Tarun Ramadorai , and Ansgar Walther . 2020. Predictably unequal? the effects of machine learning on credit markets. The Effects of Machine Learning on Credit Markets (October 1 , 2020 ) (2020). Andreas Fuster, Paul Goldsmith-Pinkham, Tarun Ramadorai, and Ansgar Walther. 2020. Predictably unequal? the effects of machine learning on credit markets. The Effects of Machine Learning on Credit Markets (October 1, 2020) (2020).
- Moritz Hardt , Eric Price , and Nati Srebro . 2016. Equality of opportunity in supervised learning. Advances in neural information processing systems 29 ( 2016 ). Moritz Hardt, Eric Price, and Nati Srebro. 2016. Equality of opportunity in supervised learning. Advances in neural information processing systems 29 (2016).
- Faisal Kamiran and Toon Calders . 2009 . Classifying without discriminating . In 2009 2nd international conference on computer, control and communication. IEEE, 1–6. Faisal Kamiran and Toon Calders. 2009. Classifying without discriminating. In 2009 2nd international conference on computer, control and communication. IEEE, 1–6.
- Faisal Kamiran and Toon Calders . 2010 . Classification with no discrimination by preferential sampling . In Proc. 19th Machine Learning Conf. Belgium and The Netherlands , Vol. 1 . Citeseer. Faisal Kamiran and Toon Calders. 2010. Classification with no discrimination by preferential sampling. In Proc. 19th Machine Learning Conf. Belgium and The Netherlands, Vol. 1. Citeseer.
- Faisal Kamiran and Toon Calders . 2012. Data preprocessing techniques for classification without discrimination. Knowledge and information systems 33, 1 ( 2012 ), 1–33. Faisal Kamiran and Toon Calders. 2012. Data preprocessing techniques for classification without discrimination. Knowledge and information systems 33, 1 (2012), 1–33.
- Danijel Kučak , Vedran Juričić , and Goran Đambić . 2018 . MACHINE LEARNING IN EDUCATION-A SURVEY OF CURRENT RESEARCH TRENDS.Annals of DAAAM & Proceedings 29 (2018). Danijel Kučak, Vedran Juričić, and Goran Đambić. 2018. MACHINE LEARNING IN EDUCATION-A SURVEY OF CURRENT RESEARCH TRENDS.Annals of DAAAM & Proceedings 29 (2018).
- Barbara A Langham . 2009. The achievement gap: What early childhood educators need to know. Texas Child Care Quarterly ( 2009 ), 14–16. Barbara A Langham. 2009. The achievement gap: What early childhood educators need to know. Texas Child Care Quarterly (2009), 14–16.
- Nicol Turner Lee . 2018. Detecting racial bias in algorithms and machine learning. Journal of Information, Communication and Ethics in Society ( 2018 ). Nicol Turner Lee. 2018. Detecting racial bias in algorithms and machine learning. Journal of Information, Communication and Ethics in Society (2018).
- Timo Makkonen . 2002. Multiple , compound and intersectional discrimination: Bringing the experiences of the most marginalized to the fore . Institute for Human Rights, Åbo Akademi University ( 2002 ). Timo Makkonen. 2002. Multiple, compound and intersectional discrimination: Bringing the experiences of the most marginalized to the fore. Institute for Human Rights, Åbo Akademi University (2002).
- Preetam Nandy , Cyrus Diciccio , Divya Venugopalan , Heloise Logan , Kinjal Basu , and Noureddine El Karoui . 2022 . Achieving Fairness via Post-Processing in Web-Scale Recommender Systems . In 2022 ACM Conference on Fairness, Accountability, and Transparency. 715–725 . Preetam Nandy, Cyrus Diciccio, Divya Venugopalan, Heloise Logan, Kinjal Basu, and Noureddine El Karoui. 2022. Achieving Fairness via Post-Processing in Web-Scale Recommender Systems. In 2022 ACM Conference on Fairness, Accountability, and Transparency. 715–725.
- Safiya Umoja Noble. 2018. Algorithms of oppression: How search engines reinforce racism. nyu Press. Safiya Umoja Noble. 2018. Algorithms of oppression: How search engines reinforce racism. nyu Press.
- Ziad Obermeyer , Brian Powers , Christine Vogeli , and Sendhil Mullainathan . 2019. Dissecting racial bias in an algorithm used to manage the health of populations. Science 366, 6464 ( 2019 ), 447–453. Ziad Obermeyer, Brian Powers, Christine Vogeli, and Sendhil Mullainathan. 2019. Dissecting racial bias in an algorithm used to manage the health of populations. Science 366, 6464 (2019), 447–453.
- Geoff Pleiss , Manish Raghavan , Felix Wu , Jon Kleinberg , and Kilian Q Weinberger . 2017. On fairness and calibration. Advances in neural information processing systems 30 ( 2017 ). Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. 2017. On fairness and calibration. Advances in neural information processing systems 30 (2017).
- Pedro Saleiro , Kit T Rodolfa , and Rayid Ghani . 2020 . Dealing with bias and fairness in data science systems: A practical hands-on tutorial . In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. 3513–3514 . Pedro Saleiro, Kit T Rodolfa, and Rayid Ghani. 2020. Dealing with bias and fairness in data science systems: A practical hands-on tutorial. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. 3513–3514.
- Stephanie A Shields . 2008 . Gender: An intersectionality perspective. Sex roles 59, 5-6 (2008), 301–311. Stephanie A Shields. 2008. Gender: An intersectionality perspective. Sex roles 59, 5-6 (2008), 301–311.
- Sahil Verma and Julia Rubin . 2018. Fairness definitions explained. In 2018 ieee/acm international workshop on software fairness (fairware) . IEEE , 1–7. Sahil Verma and Julia Rubin. 2018. Fairness definitions explained. In 2018 ieee/acm international workshop on software fairness (fairware). IEEE, 1–7.
- Michael L. Wick , Swetasudha Panda , and Jean-Baptiste Tristan . 2019 . Unlocking Fairness: a Trade-off Revisited . In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 , NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett (Eds.). 8780–8789. https://proceedings.neurips.cc/paper/2019/hash/373e4c5d8edfa8b74fd4b6791d0cf6dc-Abstract.html Michael L. Wick, Swetasudha Panda, and Jean-Baptiste Tristan. 2019. Unlocking Fairness: a Trade-off Revisited. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett (Eds.). 8780–8789. https://proceedings.neurips.cc/paper/2019/hash/373e4c5d8edfa8b74fd4b6791d0cf6dc-Abstract.html
- Leid Zejnilovic , Susana Lavado , Carlos Soares , Íñigo Martínez De Rituerto De Troya , Andrew Bell , and Rayid Ghani . 2021 . Machine Learning Informed Decision-Making with Interpreted Model’s Outputs: A Field Intervention. In Academy of Management Proceedings, Vol. 2021. Academy of Management Briarcliff Manor , NY 10510 , 15424 . Leid Zejnilovic, Susana Lavado, Carlos Soares, Íñigo Martínez De Rituerto De Troya, Andrew Bell, and Rayid Ghani. 2021. Machine Learning Informed Decision-Making with Interpreted Model’s Outputs: A Field Intervention. In Academy of Management Proceedings, Vol. 2021. Academy of Management Briarcliff Manor, NY 10510, 15424.
Cited by
The life cycle of large language models in education: A framework for understanding sources of bias
Lee, J., Hicke, Y., Yu, R., Brooks, C., & Kizilcec, R. F. (2024) · British Journal of Educational Technology · doi:10.1111/bjet.13505 · Cited by 119
“However, the complexity of social identities makes achieving absolute fairness an impractical goal and compromises are often needed to benefit from generally useful LLM applications at the cost of minor biases (Bell et al., 2023).”
BackgroundA Framework for Assurance Audits of Algorithmic Systems
Lam, K., Lange, B., Blili-Hamelin, B., Davidovic, J., Brown, S., & Hasan, A. (2024) · The 2024 ACM Conference on Fairness, Accountability, and Transparency · doi:10.1145/3630106.3658957 · Cited by 75
“…in cases where substantive differences of opinion exist between experts— such as in the discourse on computational definitions of fairness [6, 8, 37]—designers of audit standards must navigate these nuances while also balancing to achieve a set of criteria that provides compliance and is…”
BackgroundImplementing equitable and intersectionality‐aware ML in education: A practical guide
Mangal, M., & Pardos, Z. A. (2024) · British Journal of Educational Technology · doi:10.1111/bjet.13484 · Cited by 57
Operationalizing the Search for Less Discriminatory Alternatives in Fair Lending
Gillis, T. B., Meursault, V., & Ustun, B. (2024) · ACM Conference on Fairness, Accountability, and Transparency (FAccT) · doi:10.1145/3630106.3658912 · Cited by 50
Navigating fairness aspects of clinical prediction models
Chakradeo, K., Huynh, I., Balaganeshan, S. B., Dollerup, O. L., Gade-Jørgensen, H., Laupstad, S. K., Malham, M., Nguyen, T., Hulmán, Á., & Varga, T. V. (2025) · BMC Medicine · doi:10.1186/s12916-025-04340-3 · Cited by 41
“While recent research explored ways to overcome this trade-off [44], there is still an ethical dilemma: Is it justifiable to reduce performance for previously advantaged groups, potentially causing harm, to improve fairness and outcomes for marginalized or disadvantaged groups?”
Metadata
- Authors
- Bell, A., Bynum, L., Drushchak, N., Zakharchenko, T., Rosenblatt, L., & Stoyanovich, J.
- Affiliations
- New York University (US)
- Ukrainian Catholic University (UA)
- ORCID
- Venue
- 2023 ACM Conference on Fairness, Accountability, and Transparency
- Publisher
- ACM
- Published
- 2023-06-12
- Pages
- 400-422
- OpenAlex
- W4380366644
- Cited by
- 21
- References
- 21
- Citations by year
- 2026: 2 · 2025: 11 · 2024: 6 · 2023: 2
- FWCI
- 5.25
- Type
- conference paper
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- ACM Conference on Fairness, Accountability, and Transparency (FAccT) (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion, public-domain)
- arXiv (Cornell University) (public-domain)
- Funders
- National Science Foundation (1839302, 1922658, 1916505)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Ethics and Social Impacts of AI
- Physical Sciences › Computer Science › Artificial Intelligence › Explainable Artificial Intelligence (XAI)
- Social Sciences › Law › Discrimination and Equality Law
- Keywords
- algorithmic fairness, impossibility theorem, fairness-utility trade-off, intersectional fairness, fairness constraints, statistical model fitting
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: The Possibility of Fairness: Revisiting the Impossibility Theorem in Practice. https://app.cochat.ai/papers/10.1145/3593013.3594007
- The paper
- Bell, A., Bynum, L., Drushchak, N., Zakharchenko, T., Rosenblatt, L., & Stoyanovich, J. (2023). The Possibility of Fairness: Revisiting the Impossibility Theorem in Practice. 2023 ACM Conference on Fairness, Accountability, and Transparency. https://doi.org/10.1145/3593013.3594007
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.