  We extend the notion of minimax fairness in supervised learning problems to
its natural conclusion: lexicographic minimax fairness (or lexifairness for
short). Informally, given a collection of demographic groups of interest,
minimax fairness asks that the error of the group with the highest error be
minimized. Lexifairness goes further and asks that amongst all minimax fair
solutions, the error of the group with the second highest error should be
minimized, and amongst all of those solutions, the error of the group with the
third highest error should be minimized, and so on. Despite its naturalness,
correctly defining lexifairness is considerably more subtle than minimax
fairness, because of inherent sensitivity to approximation error. We give a
notion of approximate lexifairness that avoids this issue, and then derive
oracle-efficient algorithms for finding approximately lexifair solutions in a
very general setting. When the underlying empirical risk minimization problem
absent fairness constraints is convex (as it is, for example, with linear and
logistic regression), our algorithms are provably efficient even in the worst
case. Finally, we show generalization bounds -- approximate lexifairness on the
training sample implies approximate lexifairness on the true distribution with
high probability. Our ability to prove generalization bounds depends on our
choosing definitions that avoid the instability of naive definitions.
