Envy-Free Classification
This work addresses fairness in classification for machine learning applications, proposing a novel theoretical framework but is incremental as it adapts concepts from fair division to classification.
The paper tackles the problem of ensuring envy-freeness as a fairness notion in classification tasks, showing that a small sample is sufficient to guarantee that a classifier, which is envy-free on a sample, remains almost envy-free with respect to the underlying distribution with high probability, particularly when the classifier is a mixture of deterministic classifiers from a family of low Natarajan dimension.
In classic fair division problems such as cake cutting and rent division, envy-freeness requires that each individual (weakly) prefer his allocation to anyone else's. On a conceptual level, we argue that envy-freeness also provides a compelling notion of fairness for classification tasks. Our technical focus is the generalizability of envy-free classification, i.e., understanding whether a classifier that is envy free on a sample would be almost envy free with respect to the underlying distribution with high probability. Our main result establishes that a small sample is sufficient to achieve such guarantees, when the classifier in question is a mixture of deterministic classifiers that belong to a family of low Natarajan dimension.