Pipeline Interventions
  We introduce the \emph{pipeline intervention} problem, defined by a layered
directed acyclic graph and a set of stochastic matrices governing transitions
between successive layers. The graph is a stylized model for how people from
different populations are presented opportunities, eventually leading to some
reward. In our model, individuals are born into an initial position (i.e. some
node in the first layer of the graph) according to a fixed probability
distribution, and then stochastically progress through the graph according to
the transition matrices, until they reach a node in the final layer of the
graph; each node in the final layer has a \emph{reward} associated with it. The
pipeline intervention problem asks how to best make costly changes to the
transition matrices governing people's stochastic transitions through the
graph, subject to a budget constraint. We consider two objectives: social
welfare maximization, and a fairness-motivated maximin objective that seeks to
maximize the value to the population (starting node) with the \emph{least}
expected value. We consider two variants of the maximin objective that turn out
to be distinct, depending on whether we demand a deterministic solution or
allow randomization. For each objective, we give an efficient approximation
algorithm (an additive FPTAS) for constant width networks. We also tightly
characterize the "price of fairness" in our setting: the ratio between the
highest achievable social welfare and the highest social welfare consistent
with a maximin optimal solution. Finally we show that for polynomial width
networks, even approximating the maximin objective to any constant factor is NP
hard, even for networks with constant depth. This shows that the restriction on
the width in our positive results is essential.
