Timezone: »

 
Poster
Envy-Free Classification
Maria-Florina Balcan · Travis Dick · Ritesh Noothigattu · Ariel Procaccia

Thu Dec 12 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #77
in Applications -- Fairness, Accountability, and Transparency »

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.

Keywords: Fairness, Accountability, and Transparency · Game Theory and Computational Economics · Applications · Theory
[ Paper]  [ Poster] 

Author Information

Maria-Florina Balcan (Carnegie Mellon University)
Travis Dick (TTIC)
Ritesh Noothigattu (Carnegie Mellon University)
Ariel Procaccia (Harvard University)

More from the Same Authors