Envy-Free Classification
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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationFairnessGeneral ClassificationSimilar Papers 제목 키워드 기반
Reforming an Envy-Free Matching
We consider the problem of reforming an envy-free matching when each agent is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of an agent with an unassigned item preferr…
Envy-Free but Still Unfair: Envy-Freeness Up To One Item (EF-1) in Personalized Recommendation
Envy-freeness and the relaxation to Envy-freeness up to one item (EF-1) have been used as fairness concepts in the economics, game theory, and social choice literatures since the 1960s, and have recently gained popularit…
Recommendation SystemsThe lattice of envy-free many-to-many matchings with contracts
We study envy-free allocations in a many-to-many matching model with contracts in which agents on one side of the market (doctors) are endowed with substitutable choice functions and agents on the other side of the marke…
BlockingPositionA Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents
We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from $n$ agents. The problem has received attention in computer science, mathematics, and economics.…
Fair Division via Social Comparison
In the classical cake cutting problem, a resource must be divided among agents with different utilities so that each agent believes they have received a fair share of the resource relative to the other agents. We introdu…