Envy-Free Classification
Maria-Florina F Balcan, Travis Dick, Ritesh Noothigattu, Ariel D Procaccia
Abstract
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, especially when individuals have heterogeneous preferences. 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.
BibTeX
@inproceedings{NEURIPS2019_e94550c9,
author = {Balcan, Maria-Florina F and Dick, Travis and Noothigattu, Ritesh and Procaccia, Ariel D},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Envy-Free Classification},
url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/e94550c93cd70fe748e6982b3439ad3b-Paper.pdf},
volume = {32},
year = {2019}
}