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.
