# Set to Be Fair: Demographic Parity Constraints for Set-Valued Classification

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 39 references that are in the map.
- First posted on arXiv 6 Oct 2025.

## Builds on (most cited first, 18 of 18)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment](https://mlsanity.com/paper/1610.08452/) (2016)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Conformal Prediction With Conditional Guarantees](https://mlsanity.com/paper/2305.12616/) (2023)
- [Leveraging Labeled and Unlabeled Data for Consistent Fair Binary Classification](https://mlsanity.com/paper/1906.05082/) (2019)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Loss Functions for Top-k Error: Analysis and Insights](https://mlsanity.com/paper/1512.00486/) (2015)
- [A statistical framework for fair predictive algorithms](https://mlsanity.com/paper/1610.08077/) (2016)
- [Set-valued classification -- overview via a unified framework](https://mlsanity.com/paper/2102.12318/) (2021)
- [Fair learning with Wasserstein barycenters for non-decomposable performance measures](https://mlsanity.com/paper/2209.00427/) (2022)
- [Conformalized Fairness via Quantile Regression](https://mlsanity.com/paper/2210.02015/) (2022)
- [Survey on Fairness Notions and Related Tensions](https://mlsanity.com/paper/2209.13012/) (2022)
- [Conformal Classification with Equalized Coverage for Adaptively Selected Groups](https://mlsanity.com/paper/2405.15106/) (2024)
- [Multimodal Gender Fairness in Depression Prediction: Insights on Data from the USA & China](https://mlsanity.com/paper/2408.04026/) (2024)
- [Can everyday AI be ethical. Fairness of Machine Learning Algorithms](https://mlsanity.com/paper/1810.01729/) (2018)

## Abstract (arXiv)

Set-valued classification is used in multiclass settings where confusion between classes can occur and lead to misleading predictions. However, its application may amplify discriminatory bias motivating the development of set-valued approaches under fairness constraints. In this paper, we address the problem of set-valued classification under demographic parity and expected size constraints. We propose two complementary strategies: an oracle-based method that minimizes classification risk while satisfying both constraints, and a computationally efficient proxy that prioritizes constraint satisfaction. For both strategies, we derive closed-form expressions for the (optimal) fair set-valued classifiers and use these to build plug-in, data-driven procedures for empirical predictions. We establish distribution-free convergence rates for violations of the size and fairness constraints for both methods, and under mild assumptions we also provide excess-risk bounds for the oracle-based approach. Empirical results demonstrate the effectiveness of both strategies and highlight the efficiency of our proxy method.