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

Eyal Haïm Cohen, Christophe Denis, Mohamed Hebiri
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:3367-3375, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-cohen26b, title = { Set to Be Fair: Demographic Parity Constraints for Set-Valued Classification }, author = {Cohen, Eyal Ha\"{i}m and Denis, Christophe and Hebiri, Mohamed}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {3367--3375}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/cohen26b/cohen26b.pdf}, url = {https://proceedings.mlr.press/v300/cohen26b.html}, abstract = { 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. } }
Endnote
%0 Conference Paper %T Set to Be Fair: Demographic Parity Constraints for Set-Valued Classification %A Eyal Haïm Cohen %A Christophe Denis %A Mohamed Hebiri %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-cohen26b %I PMLR %P 3367--3375 %U https://proceedings.mlr.press/v300/cohen26b.html %V 300 %X 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.
APA
Cohen, E.H., Denis, C. & Hebiri, M.. (2026). Set to Be Fair: Demographic Parity Constraints for Set-Valued Classification . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:3367-3375 Available from https://proceedings.mlr.press/v300/cohen26b.html.

Related Material