Set to Be Fair: Demographic Parity Constraints for Set-Valued Classification
This work addresses fairness in set-valued classification, which is important for applications where confusion between classes can lead to misleading predictions, though it is incremental as it applies existing fairness constraints to a specific classification setting.
The paper tackles the problem of set-valued classification under demographic parity and expected size constraints, proposing two strategies: an oracle-based method that minimizes classification risk while satisfying constraints, and a computationally efficient proxy method. Empirical results demonstrate the effectiveness of both strategies, with the proxy method showing efficiency.
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.