# Envy-Free Classification

arXiv: https://arxiv.org/abs/1809.08700 · HTML: https://mlsanity.com/paper/1809.08700/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2018.

## Built on by (most cited first, 11 of 11)

- [Understanding Instance-Level Impact of Fairness Constraints](https://mlsanity.com/paper/2206.15437/) (2022)
- [Online certification of preference-based fairness for personalized recommender systems](https://mlsanity.com/paper/2104.14527/) (2021)
- [A New Notion of Individually Fair Clustering: α-Equitable k-Center](https://mlsanity.com/paper/2106.05423/) (2021)
- [Algorithmic Fairness in Business Analytics: Directions for Research and Practice](https://mlsanity.com/paper/2207.10991/) (2022)
- [Beyond Adult and COMPAS: Fairness in Multi-Class Prediction](https://mlsanity.com/paper/2206.07801/) (2022)
- [Fair Ranking as Fair Division: Impact-Based Individual Fairness in Ranking](https://mlsanity.com/paper/2206.07247/) (2022)
- [Individual Preference Stability for Clustering](https://mlsanity.com/paper/2207.03600/) (2022)
- [Toward Operationalizing Pipeline-aware ML Fairness: A Research Agenda for Developing Practical Guidelines and Tools](https://mlsanity.com/paper/2309.17337/) (2023)
- [When Personalization Harms: Reconsidering the Use of Group Attributes in Prediction](https://mlsanity.com/paper/2206.02058/) (2022)
- [Algorithmic Challenges in Ensuring Fairness at the Time of Decision](https://mlsanity.com/paper/2103.09287/) (2021)
- [Scalable Algorithms for Individual Preference Stable Clustering](https://mlsanity.com/paper/2403.10365/) (2024)

## Abstract (arXiv)

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.