  The adoption of automated, data-driven decision making in an ever expanding
range of applications has raised concerns about its potential unfairness
towards certain social groups. In this context, a number of recent studies have
focused on defining, detecting, and removing unfairness from data-driven
decision systems. However, the existing notions of fairness, based on parity
(equality) in treatment or outcomes for different social groups, tend to be
quite stringent, limiting the overall decision making accuracy. In this paper,
we draw inspiration from the fair-division and envy-freeness literature in
economics and game theory and propose preference-based notions of fairness --
given the choice between various sets of decision treatments or outcomes, any
group of users would collectively prefer its treatment or outcomes, regardless
of the (dis)parity as compared to the other groups. Then, we introduce
tractable proxies to design margin-based classifiers that satisfy these
preference-based notions of fairness. Finally, we experiment with a variety of
synthetic and real-world datasets and show that preference-based fairness
allows for greater decision accuracy than parity-based fairness.
