Envy-Free Classification

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. 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.

References in corpus (8)

• Equality of Opportunity in Supervised Learning
• Learning Non-Discriminatory Predictors
• From Parity to Preference-based Notions of Fairness in Classification
• Calibration for the (Computationally-Identifiable) Masses
• Probably Approximately Metric-Fair Learning
• Asymptotic Existence of Fair Divisions for Groups
• A Voting-Based System for Ethical Decision Making
• Multiclass Learning Approaches: A Theoretical Comparison with Implications

Cited by in corpus (6)

• Fair Ranking as Fair Division: Impact-Based Individual Fairness in Ranking
• Toward Operationalizing Pipeline-aware ML Fairness: A Research Agenda for Developing Practical Guidelines and Tools
• Sample Complexity of Uniform Convergence for Multicalibration
• Avoiding Resentment Via Monotonic Fairness
• A Learning Framework for Distribution-Based Game-Theoretic Solution Concepts
• A New Notion of Individually Fair Clustering: $\alpha$-Equitable $k$-Center