  We propose a novel reduction-to-binary (R2B) approach that enforces
demographic parity for multiclass classification with non-binary sensitive
attributes via a reduction to a sequence of binary debiasing tasks. We prove
that R2B satisfies optimality and bias guarantees and demonstrate empirically
that it can lead to an improvement over two baselines: (1) treating multiclass
problems as multi-label by debiasing labels independently and (2) transforming
the features instead of the labels. Surprisingly, we also demonstrate that
independent label debiasing yields competitive results in most (but not all)
settings. We validate these conclusions on synthetic and real-world datasets
from social science, computer vision, and healthcare.
