# Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making

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

## Key facts

- Cited by 75 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Mar 2019.

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

- [Trustworthy AI: From Principles to Practices](https://mlsanity.com/paper/2110.01167/) (2021)
- [Bias Mitigation for Machine Learning Classifiers: A Comprehensive Survey](https://mlsanity.com/paper/2207.07068/) (2022)
- [Trustworthy AI: A Computational Perspective](https://mlsanity.com/paper/2107.06641/) (2021)
- [CrossWalk: Fairness-enhanced Node Representation Learning](https://mlsanity.com/paper/2105.02725/) (2021)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [Aligning Eyes between Humans and Deep Neural Network through Interactive Attention Alignment](https://mlsanity.com/paper/2202.02838/) (2022)
- [A Stochastic Optimization Framework for Fair Risk Minimization](https://mlsanity.com/paper/2102.12586/) (2021)
- [Fairness without Imputation: A Decision Tree Approach for Fair Prediction with Missing Values](https://mlsanity.com/paper/2109.10431/) (2021)
- [FARE: Provably Fair Representation Learning with Practical Certificates](https://mlsanity.com/paper/2210.07213/) (2022)
- [Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features](https://mlsanity.com/paper/2206.11844/) (2022)
- [Improving Recommendation Fairness via Data Augmentation](https://mlsanity.com/paper/2302.06333/) (2023)
- [Modeling Techniques for Machine Learning Fairness: A Survey](https://mlsanity.com/paper/2111.03015/) (2021)
- [Beyond Adult and COMPAS: Fairness in Multi-Class Prediction](https://mlsanity.com/paper/2206.07801/) (2022)
- [Scalable Spectral Clustering with Group Fairness Constraints](https://mlsanity.com/paper/2210.16435/) (2022)
- [A Critical Survey on Fairness Benefits of Explainable AI](https://mlsanity.com/paper/2310.13007/) (2023)
- [Learning Optimal Fair Classification Trees: Trade-offs Between Interpretability, Fairness, and Accuracy](https://mlsanity.com/paper/2201.09932/) (2022)
- [Input-agnostic Certified Group Fairness via Gaussian Parameter Smoothing](https://mlsanity.com/paper/2206.11423/) (2022)
- [Learning Optimal Prescriptive Trees from Observational Data](https://mlsanity.com/paper/2108.13628/) (2021)
- [Interpretable and Fair Boolean Rule Sets via Column Generation](https://mlsanity.com/paper/2111.08466/) (2021)
- [Optimal Decision Diagrams for Classification](https://mlsanity.com/paper/2205.14500/) (2022)
- [Scalable Optimal Multiway-Split Decision Trees with Constraints](https://mlsanity.com/paper/2302.06812/) (2023)
- [Unmasking Bias in AI: A Systematic Review of Bias Detection and Mitigation Strategies in Electronic Health Record-based Models](https://mlsanity.com/paper/2310.19917/) (2023)
- [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://mlsanity.com/paper/2409.12788/) (2024)
- [An Empirical Comparison of Bias Reduction Methods on Real-World Problems in High-Stakes Policy Settings](https://mlsanity.com/paper/2105.06442/) (2021)
- [Optimal Decision Tree Policies for Markov Decision Processes](https://mlsanity.com/paper/2301.13185/) (2023)
- [Margin Optimal Classification Trees](https://mlsanity.com/paper/2210.10567/) (2022)
- [Generalized Disparate Impact for Configurable Fairness Solutions in ML](https://mlsanity.com/paper/2305.18504/) (2023)
- [Constrained Prescriptive Trees via Column Generation](https://mlsanity.com/paper/2207.10163/) (2022)
- [When Fair Classification Meets Noisy Protected Attributes](https://mlsanity.com/paper/2307.03306/) (2023)
- [Explainable Global Fairness Verification of Tree-Based Classifiers](https://mlsanity.com/paper/2209.13179/) (2022)

## Abstract (arXiv)

In recent years, automated data-driven decision-making systems have enjoyed a tremendous success in a variety of fields (e.g., to make product recommendations, or to guide the production of entertainment). More recently, these algorithms are increasingly being used to assist socially sensitive decision-making (e.g., to decide who to admit into a degree program or to prioritize individuals for public housing). Yet, these automated tools may result in discriminative decision-making in the sense that they may treat individuals unfairly or unequally based on membership to a category or a minority, resulting in disparate treatment or disparate impact and violating both moral and ethical standards. This may happen when the training dataset is itself biased (e.g., if individuals belonging to a particular group have historically been discriminated upon). However, it may also happen when the training dataset is unbiased, if the errors made by the system affect individuals belonging to a category or minority differently (e.g., if misclassification rates for Blacks are higher than for Whites). In this paper, we unify the definitions of unfairness across classification and regression. We propose a versatile mixed-integer optimization framework for learning optimal and fair decision trees and variants thereof to prevent disparate treatment and/or disparate impact as appropriate. This translates to a flexible schema for designing fair and interpretable policies suitable for socially sensitive decision-making. We conduct extensive computational studies that show that our framework improves the state-of-the-art in the field (which typically relies on heuristics) to yield non-discriminative decisions at lower cost to overall accuracy.