The Price of Local Fairness in Multistage Selection
  The rise of algorithmic decision making led to active researches on how to
define and guarantee fairness, mostly focusing on one-shot decision making. In
several important applications such as hiring, however, decisions are made in
multiple stage with additional information at each stage. In such cases,
fairness issues remain poorly understood.
  In this paper we study fairness in $k$-stage selection problems where
additional features are observed at every stage. We first introduce two
fairness notions, local (per stage) and global (final stage) fairness, that
extend the classical fairness notions to the $k$-stage setting. We propose a
simple model based on a probabilistic formulation and show that the locally and
globally fair selections that maximize precision can be computed via a linear
program. We then define the price of local fairness to measure the loss of
precision induced by local constraints; and investigate theoretically and
empirically this quantity. In particular, our experiments show that the price
of local fairness is generally smaller when the sensitive attribute is observed
at the first stage; but globally fair selections are more locally fair when the
sensitive attribute is observed at the second stage---hence in both cases it is
often possible to have a selection that has a small price of local fairness and
is close to locally fair.
