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.


Introduction
Inequality can be difficult to correct by the time it manifests itself in consequential domains. For example, faculty in computer science departments are disproportionately male [Way et al., 2016], and although the reasons for this are varied and complex, it seems difficult to correct only by intervening in the process of faculty hiring (although the solution likely involves some intervention at this stage). The problem is that interventions at the final stage of a long pipeline may not be enough (or the best way) to address iniquities that compound starting from earlier stages in the pipeline such as graduate school, college, high school, enrichment programs, all the way back to birth circumstances. Because each stage of, for example, employment pipelines feeds into the next, interventions that are isolated to any one stage can have difficulty controlling effects on final outcomes -and although in practice it is difficult to fully understand such a system, we would ideally like to design proposed interventions at a system-wide level, rather than myopically.
Thus motivated, we study an optimization problem within a stylized (and highly simplified) model of such a pipeline. Our model is a layered directed acyclic graph. The vertices in the first layer represent a coarse partitioning of possible birth circumstances into a small number of typeseach vertex representing one of these types. There is a probability vector over these vertices and individuals are "born" into some vertex with these probabilities. The graph represents a Markov process that determines how individuals progress through the pipeline. From every vertex there is a stochastic transition matrix specifying the probability that an individual will progress to each vertex in the next layer of the pipeline. We might imagine, for example, that the proportion of children that enroll in each of several elementary schools (the second layer of such a pipeline) varies according to the neighborhood that they are raised in (the first layer). The proportion of children that then go on to enroll in each of several high schools may then vary according to the elementary school they attend, and so on. Finally, vertices at the last layer of the pipeline are associated with payoffs. One may then calculate the expected payoff of an individual as a function of their initial position. These payoffs may vary widely depending on this position.
We are concerned with the problem of how best to invest limited resources so as to modify the transition matrices governing different layers of this pipeline to achieve some goal. In this paper we consider two goals: the first is simply maximizing social welfare -the expected payoff for an individual chosen according to the given probability vector for the first layer. Although this is a natural objective, it can easily lead to solutions that are "unfair" in the sense that they will prioritize investments that lead to improvements for majority populations over minority populations, simply because majority populations, by their sheer numbers, contribute more to social welfare. The second goal we study is therefore to maximize the minimum expected payoff of individuals, where the minimum is taken over all of the initial positions, i.e., layer 1 vertices. This "maximin" objective is a standard fairness-motivated objective in allocation problems [see, e.g., Barman and Krishnamurthy, 2017, Procaccia and Wang, 2014, Budish, 2011. In fact, we study two different variants of this objective, that can be distinguished by the timing with which one wants to evaluate fairness. The ex-ante maximin objective asks for a distribution over budget-feasible modifications of the transition matrices, that maximize the minimum expected payoff over all initial positions. The ex-post maximin objective asks for a single (i.e. deterministic) budget-feasible modification to the transition matrices. Because the problem we study is non-convex, these two goals are distinctwhich is preferred depends on when one wants to evaluate the fairness of a solution: before or after the randomization.

Overview of Our Results
Briefly, our main contributions are the following: 1. We define and formalize the pipeline intervention problem with the social welfare, ex-ante maximin, and ex-post maximin objectives. We also prove a separation between the ex-post and ex-ante maximin solutions.
2. We give an additive fully polynomial-time approximation scheme (FPTAS) for both the social welfare and ex-post maximin objectives for networks of constant width (but arbitrarily long depth).
3. We give an efficient reduction from the ex-ante maximin objective problem to the ex-post maximin objective problem via equilibrium computation in two-player zero-sum games. Combined with our results from 2, this yields an additive FPTAS for the ex-ante maximin objective problem for constant width networks as well.
4. We define and prove tight bounds on the "price of fairness", which compares the optimal social welfare that can be achieved with a given budget to the social welfare of ex-post maximin optimal solutions.
5. Finally, we show that the pipeline intervention problem is NP hard even to approximate in the general case when the width w is not bounded -and hence that our efficient approximation algorithms cannot be extended to the general case (or even the case of constant depth, polynomial width networks).

Related Work
There is an enormous literature in "algorithmic fairness" that has emerged over the last several years, that we cannot exhaustively summarize here -but see Chouldechova and Roth [2018] for a recent survey. Most of this literature is focused on the myopic effects of a single intervention, but what is more conceptually related to our paper is work focusing on the longer-term effects of algorithmic interventions. Dwork and Ilvento [2018] and Bower et al. [2017] study the effects of imposing fairness constraints on machine learning algorithms that might be composed together in various ways to reach an eventual outcome. They show that generally fairness constraints imposed on constituent algorithms in a pipeline or other composition do not guarantee that the same fairness constraints will hold on the entire mechanism as a whole. (They also study conditions under which fairness guarantees are well behaved under composition). Two recent papers [Liu et al., 2019a, Mouzannar et al., 2019 study parametric models by which classification interventions in an earlier stage can have effects on the data distribution at later stages, and show that for many commonly studied fairness constraints, their effects can either be positive or negative in the long term, depending on the functional form of the relationship between classification decisions and changes in the agent type distribution.
There is also a substantial body of work studying game theoretic models for how interventions affect "fairness" goals. This work dates back to Coate andLoury [1993], Foster andVohra [1992] in the economics literature, who propose game theoretic models to rationalize how unequal outcomes might emerge despite two populations being symmetrically situated. More recently, in the computer science literature, several papers consider more complicated models that are similar in spirit to Coate and Loury [1993], Foster and Vohra [1992]. Hu and Chen [2018] propose a two-stage model of a labor market with a "temporary" (i.e. internship) and "permanent" stage, and study the equilibrium effects of imposing a fairness constraint on the temporary stage. Liu et al. [2019b] consider a model of the labor market with higher dimensional signals, and study equilibrium effects of subsidy interventions which can lessen the cost of exerting effort. Kannan et al. [2019] study the effects of admissions policies on a two-stage model of education and employment, in which a downstream employer makes rational decisions. Jung et al.
[2020] study a model of criminal justice in which crime rates are responsive to the classifiers used to determine criminal guilt, and study which fairness constraints are consistent with the goal of minimizing crime.

Model
The pipeline intervention problem is defined by a layered directed acyclic graph G = (V, E), where V is the set of vertices (or nodes), and E is the set of edges. The vertices are partitioned into k layers L 1 , L 2 , · · · L k , each consisting of w vertices. We say that w is the width of the graph. For every t ∈ [k − 1], there is a directed edge from every u ∈ L t to every v ∈ L t+1 ; the graph contains no other edge. In turn, every path from layer L 1 to layer L k must go through exactly one vertex in each layer L 2 , . . . , L k−1 in this order. Intuitively, such a layered graph represents a pipeline, in which individuals start at initial positions in layer 1, and transition through the graph to final positions in layer k, stochastically according to transition matrices which we define next.
Let M be the set of left stochastic matrices in R w×w : i.e., M ∈ M if and only if for all j ∈ [w], w k=1 x(k) = 1} be the set of probability distributions over [w]. An instance of the pipeline intervention problem is defined by three things: denotes the probability of transitioning from node u to node v 1 .
2. An input distribution D 1 over the vertices in layer 1, where D 1 (u) denotes the fraction of the population that starts at u in L 1 as their initial position. Without loss of generality we assume D 1 (u) > 0 for all initial positions u ∈ L 1 .
3. Finally, a reward R(v) ≥ 0 corresponding to each vertex v ∈ L k in the final layer. We let R = (v) v∈L k denote the vector of all rewards on layer k. We assume without loss of generality that the rewards on any two vertices in the final layer are distinct: for all v, v ∈ L k , R(v) = R(v ). We can also assume without loss of generality (up to renaming) that R(1) > . . . > R(w).
In our model, each vertex u in the starting layer L 1 represents the initial position of some population; abusing notation, we refer to this population also as u. An individual in population u transitions to a node in layer L 2 , then a node in layer L 3 , up until they reach a node v in destination layer L k , and obtains a reward of R(v), with probability given by the transition matrices M 0 1 to M 0 k−1 . The expected reward of an individual from population u is therefore given by R M k−1 · . . . · M 1 e u , where e u represents the w-dimensional standard basis vector corresponding to index u. The aim of the pipeline intervention problem is to modify the transition matrices between pairs of adjacent layers so as to improve these expected rewards in some way (we study several objectives) given a finite resource constraint.
We will take the point of view of a centralized designer, who can invest money into modifying the transition matrices between layers. We assume that modifying these transitions matrices is costly, and that on a given layer t, transforming M 0 t to some alternative M t ∈ M has cost: We remark that although for simplicity we assume that costs are uniform in the sense that changing the probability of transitions is the same between any pair of vertices, our results naturally extend to non-uniform transition costs.
The designer has a total budget of B, and can select target transition matrices (M 1 , . . . , M k−1 ) so long as the cost of modifying the initial transition matrices to his targets does not exceed his budget. That is, he must select target transition matrices subject to the constraint: We let be the set of feasible sets of transition matrices, given initial matrices M 0 1 , . . . , M 0 k−1 and budget B. We will consider several objectives that we may wish to optimize. The first is simply to maximize the overall social welfare (i.e. the expected reward of an individual chosen according to D 1 ), which is given by The second objective aims to compute a "fair" outcome in the sense that it evaluates a solution according to the expected payoff of the worst-off members of society (here interpreted as individuals starting at the pessimal initial position), rather than according to the average. This is the classic maximin objective. It turns out that there are two distinct variants of this problem, depending on whether one wishes to allow randomized solutions (i.e. distributions over matrices) or not. We will elaborate on this distinction in the next section, but in the deterministic variant we wish to optimize where e j ∈ R w is the unit vector with e j (j) = 1, and e j (i) = 0 for all i = j.
Remark 1. In defining the model above, we have made two simplifications that make our notation simpler, but are not necessary. These are: 1. We have assumed that each layer has exactly w vertices. In fact, all of our results generalize to the case in which each layer has ≤ w vertices.
2. We have assumed that all edges are able to be modified. In fact, all of our algorithms generalize to the case in which only a subset of the edges between adjacent layers are "malleable" and the remaining are fixed (and probability mass can only be moved between malleable edges).

Optimization Problems of Interest
In this paper, we will provide algorithms to solve the following three optimization problems. We note at the outset that these optimization problems are non-convex, due to the fact that the set F of feasible matrices (M 1 , . . . , M k−1 ) is not convex for k > 2. Hence we should not expect efficient algorithms in the fully general setting; we will give efficient algorithms for networks of constant width w (i.e. algorithms whose running time is polynomial in the depth of the network k), and show that outside of this class, the problem is NP hard even to approximate.
Social welfare maximization The first optimization problem we aim to solve is that of maximizing the social welfare of our network, under our budget constraint: Ex-post maximin problem The second optimization problem aims to maximize the minimum expected reward that a population can obtain, where the minimum is taken over all initial positions: Ex-ante maximin problem The third optimization problem has the same objective as Program 2, but allows randomization over sets of transition matrices that satisfy the budget constraint 2 . To define this optimization problem, we let ∆F B, M 0 1 , . . . , M 0 k−1 the set of probability distributions with support F B, M 0 1 , . . . , M 0 k−1 . The optimization program is given by: where the expectation is taken over the randomness of distribution ∆M . Note that where Program 3 can be viewed as optimizing an ex-ante notion of fairness, in which we are evaluated on the minimum expected value of individuals starting at any initial position, before the coins of ∆M are flipped. In contrast, Program 2 evaluates the minimum expected value of individuals starting at any initial position for an already established set of transition matrices.  (1), the existence of a maximum is an immediate consequence of the fact that the objective function is continuous in (M 1 , . . . , M k−1 ) and F and M are compact sets. For Program (2), note that no solution can have R M k−1 . . . M 1 e j ≥ R ∞ for any j, as M k−1 . . . M 1 e j is a probability distribution. Hence, we can rewrite the program as This is an optimization problem with a continuous objective function over a compact set, so it admits a solution. A similar argument follows for Program (3).

Algorithmic Preliminaries
Our paper uses a dynamic programming approach for solving programs (1) and (2). (Our solution to program (3) is a game-theoretic reduction to our solution to program (2)). Our algorithms will search over possible input distributions in D starting from layer L t for all t ∈ {2, . . . , k − 2}, and over possible ways of splitting the total budget B and allocating budget B t to the transition from layer L t to layer L t+1 , for all t ∈ [k − 1]. To do so, we will need to discretize both the budget space [0, B] and the probability space D.
Cost of Discretizing the Budget To discretize the budget space, we define B(ε) = {kε, ∀k ∈ N } to be the set of numbers on the real line that are multiples of ε. We consider the following discretized version of Programs 1 and 2 (We do not need to explicitly consider Program (3), since our solution for this one will be a reduction to our solution to Program (2)): and We show that this discretization does not affect the optimal value of our optimization problems by much: Claim 1. There exists a feasible solution M ε 1 , . . . , M ε k−1 to Program (4) (resp. Program (5)) with objective value at least OP T We provide a brief proof sketch below, and defer the full proof to Appendix A.1.
Proof sketch. We prove this result by constructing transition matrices M ε t that use roughly ε budget less than M * t . We show that we can do so so as to only lose welfare of the order of in each of the k − 1 layer transitions we consider, and that this loss composes additively. Definition 1. Let K ⊆ R w . We call a subset S of K an ε-net for K with respect to the 1 -norm if and only if for every D ∈ K, there exists D ∈ S such that Claim 2 (ε-nets in 1 -distance for D). Take ε > 0. There exists an ε-net D(ε) of D with respect to the 1 -norm that has size 1 ε w . This is a standard proof, included in Appendix A.2 for completeness.

Social Welfare Maximization
We want to solve the following optimization problem:

A Dynamic Programming Algorithm for Social Welfare Maximization
In this section, we describe a dynamic programming algorithm for approximately solving the problem above on long skinny networks. The algorithm will run in polynomial time when the width w of the network is small; its running time is polynomial in the depth k of the network, but exponential in the width w. The formal description is given in Algorithm 1. Our algorithm works backwards, starting from the final transition matrix from layer L k−1 to L k . It builds up the solutions to sub-problems parameterized by three parameters -a layer t, a starting distribution over the vertices in layer t, and a budget B ≥t that can be used at layers ≥ t. For each sub-problem, it computes an approximately welfare-optimal solution. Once all of these sub-problems have been solved, the optimal solution to the original problem can be read off from the "sub-problem" in which t = 1, the starting distribution is the distribution on initial positions, and B ≥1 = B. Here is the informal description of the algorithm: 1. For t going backwards from k − 1 to 1, the algorithm does the following exploration over budget splits and probability distributions D t , D t+1 ∈ D(ε) (an ε-net for the w-dimensional simplex in 1 norm) on L t : (a) The algorithm explores all discretized splits of a budget B ≥t to be used for layers t to k − 1 into a budget B t to expend on layer t and a budget B ≥t+1 to expend on the remaining layers t+1 to k−1, as well as all choices of target output probability distribution D t+1 ∈ D(ε) on layer L t+1 and the starting probability distribution D t ∈ D(ε). Informally, we can think of these "target" and "initial" probability distributions as guesses for what the distribution on vertices in layer t + 1 and layer t look like in the optimal solution. Recall that for each D t+1 and B ≥t+1 , our algorithm has already computed a near-optimal solution for a smaller sub-problem, which we will utilize in the next step.
(b) The algorithm then finds a transition matrix from L t to L k that maximizes welfare when the starting distribution on layer t is D t and the remaining transition matrices are fixed as in the solution to the corresponding sub-problem. Although the overall welfare-maximization problem is non-convex, this sub-problem can be solved as a linear program (Program 7) because all transition matrices except for one have been fixed as the solution to our sub-problem.
(c) Finally, the algorithm picks and stores the recovered transition matrices from layer L t to L k that yield the highest reward, among all the transition matrices recovered from step 1b.
We remark that while (for notational simplicity) our algorithm is written as if all layers have size exactly w, it can easily be extended to the case in which all layers have size at most w.
end Pick B ≥t+1 , D t+1 leading to the highest objective value in Program 7, and set We briefly note why Program (7) is a linear program. The objective is linear because only the matrix M t represents variables. Thus we simply need to verify that the constraint on the cost is linear.
Definition 2. We say that a transition matrix M t is feasible with respect to a budget split B ≥t , B ≥t+1 if and only if Note that saying that M t feasible with respect to B ≥t , B ≥t+1 is equivalent to saying that M t is a feasible solution to Program (7) with parameters B ≥t , B ≥t+1 , D t , D t+1 for any D t , D t+1 ∈ D(ε). The constraint c M t , M 0 t ≤ B ≥t+1 − B ≥t can be equivalently replaced by 2w 2 + 1 linear constraints. To do so, we introduce w 2 variables -a 1 , a 2 , · · · a w 2 . The constraint can then be rewritten in the , where each f i is a linear combination of the variables. We can thus express the budget constraint of Program 7 by the following set of linear constraints: Thus, Program 7 can be written as a linear program with the number of constraints and variables being polynomial in w.

Running Time and Social Welfare Guarantees
We provide the running time and social welfare guarantees of Algorithm 1 below.
Theorem 1. Algorithm 1 instantiated with discretization parameter ε yields a solution achieving social welfare at least OP T − 3(k − 1)ε R ∞ , and has running time is any upper-bound on the running time for solving linear Program 7, which is always polynomial in w.
This immediately yields the following corollary: is any upper-bound on the running time for solving linear Program 7, which is always polynomial in w.
We observe that this running time is polynomial in k (the depth of the network) and 1/ε (the inverse additive error tolerance), but exponential in w (the width of the network). Hence our algorithm runs in polynomial time for the class of constant width networks.
Remark 3. We note that our additive near-optimality guarantee can be translated into a multiplicative guarantee. This follows from noting that given budget B, OP T ≥ B 2w R ∞ : this can be reached by investing the totality of the budget into having every node in the second-to-last layer transition to the highest reward node in the last layer with probability B 2w . Taking ε = δ · B 6(k−1)w for some constant δ < 1 gives a multiplicative approximation to the optimal social welfare with approximation factor 1 − δ.
The proof of Theorem 1 relies on the following lemma, and its corollary: Lemma 1. Let M ∈ R w×w be a left stochastic matrix, and let D, D ∈ D be probability distributions.
where the inequality follows from the triangle inequality, and the second-to-last equality from the fact that as M is a left stochastic matrix.
Corollary 2. Let R ∈ R w be a real vector and D, D ∈ D be probability distributions such that D − D 1 ≤ ε, and M ∈ R w×w a left stochastic matrix. Then Proof.
where the first step follows from Holder's inequality.
We are now ready to prove Theorem 1: Note that such matrices exist by Claim 1. Let D ε t the probability distribution on layer t defined by these transition matrices, i.e.
To prove the result, we will show by induction that for all B ≥t ≥ B ε ≥t , and for D t ∈ D(ε) such that This will directly imply that as B ε is one of the possible values of B ≥1 , Combined with Claim 1 that states OP T ε ≥ OP T − (k − 1)ε R ∞ , we will obtain the result.
Let us now provide our inductive proof. First, consider the transition from layer L k−1 to layer Now, suppose the induction hypothesis holds at layer t + 1. I.e., for all Using the induction hypothesis, we obtain that In particular, which concludes the proof of the social welfare guarantee. For the running time, we note that at each time step t, we solve one instance of Program 7 for each of the (at most) B ε possible budget splits of B ≥t and for each of the . This is repeated for k − 1 values of t.

(Ex-post) Maximin Value Maximization
Although social welfare maximization is a natural objective, it is well-known that it can be "unfair" in the sense that it explicitly prioritizes the welfare of larger populations (here represented as initial positions that have larger probability mass) over smaller populations. We can alternately evaluate a solution according to the welfare of the least-well-off population (here represented by the initial position with the smallest expected value) and ask to optimize that objective. We show how to optimize this objective in this section, when one demands a deterministic solution.

A Dynamic Programming Algorithm for Computing an Ex-post Maximin Allocation
Algorithm and proof: In this subsection, we adapt the dynamic programming approach in Section 4.1 to give an approximation algorithm for the problem of maximizing the minimum expected reward over all initial positions. Recall that D, the probability simplex, denotes the set of all possible probability distributions on a layer. Intuitively, our algorithm for maximizing social welfare kept track of a single probability distribution in each subproblem: the overall probability of arriving at each vertex in the layer over both the randomness of an individual's initial position, and the randomness of the transition matrix. In order to optimize the minimum expected value over all initial positions, we will need to keep track of more state. At every layer L t , we will keep track of the probability of reaching each vertex in that layer from each initial position in the starting layer. So, we will now keep track of collections of w probability distributions in D w , one for each starting position. We call the elements of D w population-wise distributions.
We introduce a discretization A(ε) of D w , as follows: . Given a population-wise probability distribution A t ∈ A(ε) at layer t, we write A j t for the probability distribution corresponding to population j. The algorithm works as follows, just as before, running backwards from the final layer to the first layer: 1. For t going backwards from k − 1 to 1, the algorithm does the following, for every populationwise distribution A t ∈ A(ε) on L t : (a) The algorithm explores all splits of the budget B ≥t for layers t to k into a budget B t for the transition from L t to L t+1 and a budget B ≥t+1 for L t+1 to L k , as well as all choices of output population-wise probability distributions A t+1 ∈ A(ε) on layer L t+1 .
(b) The algorithm then finds a near-optimal transition matrix from L t to L k for every budget decomposition, by using the previously computed near-optimal solution for layers L t+1 to L k , and solving Program 8. The program maximizes the minimum reward obtained from any initial position, assuming the population-wise distribution of individuals at layer L t is given by A t .
(c) Finally, the algorithm picks and stores the best recovered transition matrices from layer L t to L k that yield the highest reward, among all the transition matrices recovered from step 1b.
The input population-wise probability distribution A 1 ∈ D w on the first layer is defined in the following manner, A j 1 := e j (the j-th basis vector in the usual orthonormal basis of R w ) for all j ∈ [w].
Note that Program (8) can be written as a linear program of size polynomial in w, using the same method that was employed to write Program (7) as a linear program.

Running Time and Ex-Post Maximin Value Guarantees
Remember that we let OP T M M denote the maximin value value of the given network. The running time and accuracy guarantees of Algorithm 2 are provided below: Theorem 2. Algorithm 2 with discretization parameter ε yields maximin value at least OP T M M − 3(k − 1)ε R ∞ , and has running time O k B ε 1 ε w 4 g(w) , where g(w) is any upper-bound on the running time for solving linear Program 8, which is always polynomial in w.
This immediately induces the following corollary: The proof of Theorem 2 is almost identical to that of Theorem 1. We provide the full proof in Appendix C.1. Input: Reward vector R on layer L k , initial transition matrices M 0 1 , . . . , M 0 k−1 , budget B, discretization parameter ε.
end Pick B ≥t+1 , A t+1 with the best objective value in Program 8, and let

(Ex-ante) Maximin Value Maximization
In this section, we consider the problem of optimizing the ex-ante minimum expected value over all initial positions: in other words, we allow ourselves to find a distribution over solutions, and take expectations over the randomness of this distribution, solving: We show in Appendix B that this can yield strictly higher utility than optimizing the ex-post minimum value. We then give an algorithm for solving the ex-ante problem by exhibiting a game theoretic reduction to the ex-post problem.

Solving the Ex-ante Maximization Problem Using Algorithm 1
Because Program 3 is a max min problem over a polytope, we can view it as a zero-sum game, and the solution that we want corresponds to a maxmin equilibrium strategy of this game. As first shown by Freund and Schapire [1996], it is possible to compute an approximate equilibrium of a zero-sum game if we can implement a no-regret learning algorithm for one of the players, and an approximate best-response algorithm for the other player: if we simply simulate repeated play of the game between a no-regret player and a best-response player, then the empirical average of player actions in this simulation converges to the Nash equilibrium of the game.
This forms the basis of our algorithm. One player plays the "multiplicative weights" algorithm over the initial positions in layer 1 of the graph. This induces at every round a distribution over initial positions. The best response problem, which must be solved by the other player, corresponds to solving a welfare-maximization problem given the distribution over initial positions represented by the multiplicative weights distribution. Fortunately, this is exactly the problem that we have already given a dynamic programming solution for. The solution in the end corresponds to the uniform distribution over the solutions computed by the best-response player over the course of the dynamics. The algorithm is formally described below: The no-regret player plays distribution D t ∈ D.
The best-response player chooses M t ∈ F B, M 0 1 , . . . , M 0 k−1 such that using Algorithm 1. The no-regret player observes u t i = R M t k−1 . . . M t 1 e i for all i ∈ [w], and picks D t+1 via multiplicative weight update, as follows: The proof of Lemma 2 follows from interpreting Program 3 as zero-sum game, noting that the best response problem for the maximization player corresponds to the welfare-maximization problem for which we have an efficient algorithm, and then applying the no-regret dynamic analysis from Freund and Schapire [1996]. The details are provided in Appendix C.2.

Price of Fairness
In this section, we compute tight bounds on a "price of fairness". Specifically, we compare the optimal welfare achievable with the welfare that is achievable if we instead use our budget to maximize the minimum value over initial positions -i.e. if we solve the maximin problem. We focus on the ex-post maximin problem -i.e. we prove our bounds with respect to deterministic solutions. We note that there may be many different maximin optimal solutions that differ in their overall welfare, and so we consider two variants of the price of fairness in our setting -comparing with both the maximum welfare consistent with a maximin optimal solution, and the minimum welfare consistent with a maximin optimal solution.
Let OP T SW the optimal value of Program (1) (the optimal social welfare). Let S f be the set of solutions to Program (2)  to be the maximum and minimum social welfare respectively that are consistent with maximin optimal solutions. We define two variants of "the price of fairness" in our setting as: Note that P + f ≤ P − f always, as P + f compares the optimal social welfare with the solution of Program 2 with highest social welfare , while P − f considers the solution that has the lowest social welfare. We provide matching lower bounds on P + f and upper bounds on P − f . This, in turn, provides tight bounds on the price of fairness with respect to any choice of maximin solution.
7.1 Lower Bounds on P + f Our lower bounds are based on the following construction: Example 1. Consider a network with only two layers, L 1 and L 2 , such that L 1 has w nodes and L 2 has 2 nodes. Suppose the starting distribution is given by D 0 1 = (1 − (w − 1)ε, ε, . . . , ε) for ε > 0 small enough, the reward vector is given by R = (1, 0) , and the initial transition matrix M 0 1 is given by I.e., in the initial transition matrix, every starting node transitions to the destination node that has reward 0, and the welfare of the initial network is 0.
Theorem 3. For all w ∈ N, for any δ > 0, there exists a network with k = 2 with price of fairness The proof follows from solving the social welfare maximization problem and the maximin value problem on Example 1. The full proof is provided in Appendix C.3.1.

Upper Bounds on P − f
Our upper bounds will make use of the following claim, which bounds the maximum social welfare that can be achieved under budget B.
is the initial welfare. The proof of this lemma is straightforward and is deferred to Appendix C.3.2. We will also need lower bounds on the social welfare achieved by any optimal solution to the maximin program. The first lower bound is a function of B and w, but is independent of W 0 .

Lemma 4. For any
The proof of Lemma 4 is deferred to Appendix C.3.3. We provide a brief proof sketch below: Proof Sketch. The budget B can be fully invested in improving edges from the second-to-last layer L k−1 to the last layer L k . The idea is to increase the transition from any node u ∈ L k−1 to the best node v ∈ L k with reward R ∞ , by an amount of B/2w each. Doing so guarantees the result, noting that every starting node in the first layer transitions to a node in L k−1 with probability 1, then to reward R ∞ on the last layer L k with probability at least B/2w.
The second lower bound we need shows that the social welfare achieved by a solution to Program (2) is lower-bounded by the initial social welfare W 0 = R M 0 k−1 . . . M 0 1 D 0 1 .

Lemma 5. For any
We defer the full proof of Lemma 5 to Appendix C.3.4 and provide a proof sketch below: Proof Sketch. The proof follows from the fact that increasing the expected reward of any given node u in any layer L t in the network can be done by taking some of the transition probability from u to a low-reward node and re-allocating it to the transition between u and a higher reward node. Doing so does not decrease the expected reward of any other vertex in the network. In turn, it is always sub-optimal to invest budget into decreasing the expected reward of any node in the network.
We can now use Lemmas 3, 4 and 5 to derive nearly tight upper bounds on the price of fairness with respect to the worst maximin solution: Proof. We divide the proof in three cases: 1. B ≥ 2w. By Lemma 4, it must be the case that any optimal solution to Program (2) has welfare at least min 1, B 2w R ∞ = R ∞ . It is then immediately the case that OP T SW = R ∞ by Lemma 3 and P f = 1.
2. 2 < B ≤ 2w. By Lemma 3, we have OP T SW ≤ R ∞ . Further, by Lemma 4, we have that any solution to Program (2) has welfare at least B 2w R ∞ . This immediately yields the result.
3. 0 < B ≤ 2. By Lemma 3, we have OP T SW ≤ W 0 + B 2 R ∞ . By Lemmas 4 and 5, we have that the social welfare of any maximin solution is at least W 0 and at least B 2w R ∞ . Therefore, the price of fairness is upper-bounded on the one hand by and on the other hand by When W 0 ≥ B 2w R ∞ , the first bound gives and when W 0 ≤ B 2w R ∞ , the second bound yields which concludes the proof.

Hardness of Approximation
In this section, we show that the problem of finding the ex-post maximin value of a pipeline intervention problem instance within an approximation factor of 2 is NP-hard in the general case, where the width w of the network is not bounded. More specifically, we show that no algorithm that has a time bound polynomial in w, k and B can give a 2-approximation to the maximin value unless P = N P . This hardness result holds for k as small as 17. We remark that our result and proof can be immediately extended to show hardness of C-approximation, for any constant C, for an appropriate choice of constant depth k.
The problem that we show to be hard to approximate is a slight generalization of our original problem. We have assumed up to now that we are allowed to modify the probabilities on all the edges, whereas, in our generalization, only a subset of the edges between adjacent layers are "malleable" and the remaining are fixed; probability mass can now only be moved between malleable edges. We remind the reader that our algorithmic results generalize to this setting, as per Remark 1.
We show this hardness result via a reduction from a gap version of the vertex cover problem. The result of Dinur and Safra [2005] shows that it is NP-hard to approximate the minimum vertex cover by a factor smaller than 1.306. In particular, their result shows that the following gap version of vertex cover is NP-hard: given (G, κ), we wish to either know if the graph G has a vertex cover of size κ, or has no vertex cover smaller than size 1.306κ.

The Reduction
Our reduction works as follows: we construct a pipeline intervention instance of constant width (17 layers) from the given graph. The first layer has a node corresponding to each edge (u, v) of the original graph, and is connected by edges to nodes corresponding to vertices u and v on the second layer. We set up the instance so that positive probability mass is only ever added to a set of edge disjoint paths, where each path corresponds to a vertex in the original graph. These paths are shown by the dark, solid lines in Figure 1. The main idea behind the reduction is the following -by observing how allocations finding the maximin value split the budget over these edge disjoint paths, we can find out which vertices would form a small vertex cover of the original graph. Formally, let the given graph G = (V, E) we reduce from have n vertices (|V| = n) and m edges (|E| = m). We construct of a pipeline intervention problem instance I with k + 2 layers and width w, where k = 15 and w is polynomial in n. The instance I has an associated budget B(κ, ε) = 2kκε where ε < 1 2 . For the sake of clarity, we refer to the set of vertices V in the vertex cover instance as "vertices" and the vertices in the instance I as "nodes". A complete description of instance I is as follows: 1. The first layer, L 1 , has exactly m nodes, with each edge (u, v) in graph G having a unique corresponding node of the same label in layer L 1 .
2. The second layer has exactly n nodes, with each vertex v in graph G, having a unique corresponding node in layer L 2 with label v 2 .
3. The next k − 1 layers are of the following form -layer L i , for i = 3 to k + 1, has n + 1 nodes. The first n nodes have labels from the set {v i } v∈V , i..e, each vertex v in the original graph G has a corresponding node v i in layer L i . The last node is indexed by x i and exists to capture the "leftover" outward probability from the nodes {v i−1 } v∈V in layer L i−1 .
4. The final layer L k+2 has two reward nodes -y, of reward 1 and z, of reward 0.
We now describe the initial transition matrices.
1. From layer L 1 to layer L 2 : for every node (u, v) in layer L 1 , the outgoing probability is equally split between edges to nodes u 1 and v 1 in layer L 2 , i.e., edges ((u, v), u 1 ) and ((u, v), v 1 ) each have probability 1 2 .
2. From layer L i to layer L i+1 for i = 2 to k: For all vertices v ∈ V (i.e., the original graph), the corresponding edge (v i , v i+1 ) (in our construction) has probability ε. The remaining outgoing probability out of node v i goes to the leakage node x i+1 . We call edges of the form (v i , x i+1 ) "leakage" edges. For i ≥ 3, the edge (x i , x i+1 ) has all the outward probability, i.e., 1, from node x i .
3. From layer L k+1 to layer L k+2 : each node in layer L k+1 is connected to z, the zero reward node, with probability 1.
We let P v be the path going through nodes v 2 , v 3 · · · v k+1 , y in our construction. We will refer to {P v } v∈V as vertex paths. Let E be the set of edges found on paths {P v } v∈V . Let E contain of all the "leakage" edges in the instance I ,i.e., edges of the form (v i , x i+1 ) as well as all edges of the form (v k+1 , z). We stipulate, as part of the description of the instance, that E ∪ E is the set of malleable edges in I and that the probability mass on any other edge cannot be changed. This completes the description of instance I .

Proof of Hardness of Approximation
In this setup, we argue that any algorithm computing a maximin value of our instance will only use budget to improve the probability mass on the vertex paths. To begin, we observe that the only nodes with more than one outgoing malleable edge are the nodes on the vertex paths, exempting the reward node y. Hence, these are the only nodes whose associated outgoing transition matrices can be modified. Furthermore, these nodes have exactly one edge from E , the edges on the vertex paths, and one leakage edge, implying that probability mass can only be transferred between these two edges. Note that the reward associated with starting at any leakage node is always 0, since all outgoing edges from leakage nodes lead to the zero sink with probability 1, and are not malleable. In contrast, nodes on the vertex paths start with expected positive welfare initially. Therefore, it would be a (strictly) sub-optimal strategy to route any more probability mass towards a leakage node , i.e., increase the probability mass on any edge in E leading to reward 0, since it would come at the cost of decreasing probability mass on an edge towards a node on a vertex path with strictly positive reward. Consequently, any algorithm that optimizes the maximin value would only increase the probability on the other malleable edges, i.e., edges in E , by removing probability mass from edges E . To give a more local picture, budget is spent on the following operation -increasing the probability mass on an edge of the form (v i , v i+1 ) and balancing the outgoing probability mass from vertex v i by correspondingly decreasing the probability mass on edge (v i , x i+1 ). Note that there are no malleable edges in the transition between layer L 1 and layer L 2 , and hence the corresponding transition matrix remains unchanged.
We fix a threshold T (2ε) k 4 . The following lemma shows the desired reduction: Lemma 6. If graph G has a vertex cover of size κ, then the maximin value of the constructed instance is at least 2T . Complementarily, if graph G has no vertex cover smaller than 1.3605κ, then the maximin value of the constructed instance is less than T .
Observe that the above lemma shows achieving a 2-approximation to the maximin value is NP-hard, since such an algorithm would be able to solve the gap version of vertex cover in polynomial time. Note that this also rules out an additive PTAS for the pipeline interventions problem, even for networks of constant depth , since our hard instance I has constant depth.
Proof of Lemma 6. The forward direction of the proof is straightforward. Given that the original graph has a vertex cover V * ⊆ V of size κ, we show a candidate solution that guarantees a minimum reward of 2T . Consider the subset E * ⊆ E which consists only of edges on the vertex paths indexed by vertices in the vertex cover V * , i.e., {P v } v∈V * . Since each such path has k edges and there are κ number of paths, |E * | = kκ. We spend a budget 2ε to increase the probability mass one each edge of E * by ε and decrease the probability mass of the corresponding leakage edge by ε. Note that this is always possible, since ε + ε ≤ 1 (i.e., we never try to increase the probability mass on an edge beyond 1). This exactly utilizes our budget B(κ, ε) = 2kκε. The new probability on every edge of E * is now 2ε. Consider any population starting on a node (u, v) of the first layer. Since V * is a vertex cover, at least one of u or v is present in the set V * . Without loss of generality, let us assume v ∈ V * . The reward at node v 2 is now exactly (2ε) k . Since the transition matrices for layer L 1 to L 2 are unchanged, a population starting at node (u, v) arrives at node v 2 with probability 1 2 ; thus, an agent starting at (u, v) has expected reward at least (2ε) k 2 = 2T . Now, consider the case where the graph has no vertex cover of size 1.305κ. To prove a contradiction, let us assume that the maximin value is greater than or equal to T . We will show that we can recover a vertex cover of size less than size 1.305κ from the maximin value solution, thus proving a contradiction. Let W (l) represent the reward associated with starting at node l. We know that all the budget is spent on the paths {P v } v∈V . Let use write 2kεa v be the budget spent on improving path P v ; note that the net increase in probability mass across all edges of P v is kεa v . By the AM-GM inequality, we know that W (v 2 ) ≤ (ε + a v ε) k , with equality when ka v ε is split equally across edges on path P v . A population starting at node (u, v) on layer L 1 reaches node u 2 and node v 2 each with probability 1 2 each. Thus, we have W ((u, v)) ≤ (ε+auε) k +(ε+avε) k 2 . Since this solution guarantees a reward of at least T for every vertex within a total budget B(κ, ε) = 2kκε, we have the following inequalities: Dividing the first inequality by ε k , multiplying by 2, and substituting k = 15, we get: We now generate a vertex set V * of original graph G as follows -include vertex v in V * if a v ≥ 0.823. We complete the proof by showing that V * is a vertex cover of G and |V * | < 1.3605κ. The fact that |V * | < 1.3605κ follows directly from the rounding scheme that is employed. Observe that each a v is scaled upward by a factor of at most 1 0.823 < 1.22. Thus, |V * | < 1.22κ. Now, assume that V * is not a vertex cover. Then, there exists an edge (u, v) ∈ E in the original graph such that a u , a v < 0.823. Thus, we get: (1 + a u ) 15 + (1 + a v ) 15 < 2(1.823) 15 < 16325 < 16384 = 2 14 This violates the reward guarantee for the population starting at node (u, v), thus resulting in a contradiction.
Lily Hu and Yiling Chen. A short-term intervention for long-term fairness in the labor market.

A Preliminaries, continued
A.1 Proof of Claim 1 We will prove both results at once, noting that they both directly follow from showing that there exists matrices M ε 1 , . . . , M ε k that are feasible for the discretized problems, such that for all j ∈ [w], where M * 1 , . . . , M * k−1 is an optimal solution to Program (1), respectively (2). To do so, we first note that it is feasible for Program (4) to pick a split of the budget B ε Now, let us construct M ε t ∈ M such that for every u, Proof. This is a well-known result; we provide a proof for completeness. The first observation is that such a net can be constructed recursively, as follows. Start with an empty set S. Initialize by picking any point D in D, and let S = {D}. Then, recursively keep finding points D ∈ D such that for all D ∈ S, D − D 1 > ε, and augment S := S ∪ D . Finally, stop the algorithm when no such point D ∈ D exists. By construction, it must be that when the algorithm terminates, for all D ∈ D, there exists D ∈ S with D − D 1 ≤ ε. As such, S constitutes an ε-net in 1 distance for D.
Second, we bound the number of steps needed. To do so, we remark that by construction, for all D 1 , D 2 ∈ S, it must be the case that D 1 − D 2 1 > ε; in turn, the 1 -balls of radius ε/2 around each of the elements of S must be disjoint, and the sum of their volumes is less than the volume of D. Since the volume of the probability simplex is given by 1 w! , and the volume of an 1 -ball of radius r is given by 1 w! (2r) w , this yields that |S| × ε w w! ≤ 1 w! , or equivalently |S| ≤ 1 ε w .

B A Separation between Ex-ante and Ex-post Maximin Values
In this section, we show there is a separation between ex-ante and ex-post maximin welfare. We do so by constructing a specific instance I for which the ex-ante maximin value is strictly larger than the ex-post maximin value: We begin by giving a complete description of our instance I. The instance consists of two parts, I 1 (depicted in Figure 2) and I 2 . Note that the transition probabilities from any given node in I 1 , shown in Figure 2, do not sum to 1. Part I 2 of the instance, described below, serves to complete these transitions and ensure that the total outgoing probability of any node is 1. Our proof primarily focuses on part I 1 , as we argue that a centralized designer should only ever invest his budget into increasing the weight on edges with both ends in I 1 , as long as the budget B is small enough.
Formally, the instance consists of four layers (L 1 to L 4 ) and a small enough total budget B. The vertices u 1 to u 4 and v 1 to v 3 , combined with all edges between them can be thought of as the part I 1 of instance I. All the remaining vertices and edges are considered to be part of I 2 .
1. The first layer consists only of vertices u 1 and v 1 .
2. The second layer consists of w + 2 vertices in total. There are two special vertices -u 2 and v 2 , seen in Figure 2. The remaining w vertices are labeled as x 1 to x w .
3. The third layer consists of 2w + 2 vertices in total. There are two special vertices -u 3 and v 3 , seen in Figure 2. The remaining 2w vertices are labeled as y 1 to y 2w .
4. The fourth layer, which is the reward layer, consists of two vertices, vertex u 4 of reward 1 and vertex z, of reward 0.
The initial transition matrices are given as follows: 1. From layer L 1 to layer L 2 -the edge (u 1 , u 2 ) has probability 1 2 . The remaining outgoing probability from u 1 is divided in the following manner -edge (u 1 , x i ) has probability 1 2w ∀i ∈ [w]. Similarly, the edge (v 1 , v 2 ) has probability 1 2 . The remaining outgoing probability from v 1 is divided in the following manner -edge (v 1 , x i ) has probability 1 2w ∀i ∈ [w]. 2. From layer L 2 to layer L 3 -the edge (u 2 , u 3 ) has probability 1 2 . The remaining outgoing probability from u 2 is divided in the following manner -edge (u 2 , y i ) has probability 1 2w ∀i ∈ [w]. Similarly, the edge (v 2 , v 3 ) has probability 1 2 . The remaining outgoing probability from v 2 is divided in the following manner -edge (v 2 , x i ) has probability 1 2w ∀i ∈ [w]. Each edge (x i , y w+i ) has probability 1.
3. From layer L 3 to layer L 4 -the edge (u 3 , u 4 ) has probability 1 2 and the edge (u 3 , z) has the remaining outgoing probability 1 2 from vertex u 3 . Similarly, the edge (v 3 , u 4 ) has probability 1 2 and the edge (v 3 , z) has the remaining outgoing probability 1 2 from vertex v 3 . Each edge (y i , z) has probability 1.
We refer to the path (u 1 , u 2 , u 3 , u 4 ) as path P 1 or the upper path and path (v 1 , v 2 , v 3 , u 4 ) as path P 2 or the lower path. Our proof relies on the following two lemmas: Lemma 7. The ex-ante maximin value that can be guaranteed for instance I is at least Proof. We show a candidate solution that gives expected reward U to both agents. We assign a budget of B/3 each for the transition between L 1 and L 2 , the transition between L 2 and L 3 , and the transition between L 3 and L 4 . We construct a feasible transition matrix M 1 by decreasing the budget invested between any two layers in I 2 by B/6 (which can be done for B small enough), and increasing the probabilities of edges (u 1 , u 2 ), (u 2 , u 3 ), and (u 3 , u 4 ) by B/6. We leave other edges in I 1 untouched. M 1 yields reward 1 2 + B 6 3 for u 1 and 1/8 for u 2 . Symmetrically, we construct a solution M 2 with expected reward 1/8 for u 1 and 1 2 + B 6 3 for u 2 . The solution that picks M 1 with probability 1/2 and M 2 with probability 1/2 guarantees maximin value of U .
We now show that the ex-post maximin value is strictly smaller than U . We will reason exclusively on I 1 , noting that when the budget B is small and w is large enough, investing any money on edges not contained within I 1 is sub-optimal. This can be seen immediately: as B goes to 0, both the input probability and the reward of any node v ∈ I 2 go to 0 for any feasible allocation, while the input probability and the reward of any vertex in I 1 is lower-bounded by 1/8; in turn, for B small enough, nodes in I 1 always have strictly higher rewards and input probabilities than any node in I 2 for any feasible allocation, and it is optimal to invest in improving only the transition probabilities from nodes in I 1 to nodes in I 1 .
To reason about how to optimally use the budget to improve edges in I 1 , we introduce new notations. We let W (v) denote the expected reward obtained by an agent starting at any vertex v in the instance. We define w i u W (u i ) and w i v W (v i ) for i ∈ {1, 2, 3, 4}. We let B 1 , B 2 , B 3 denote the budget split across the three transitions, and let B ≥i represent the budget spent to the right of layer L i . Note that, in our instance, B ≥3 = B 3 . We now state the following the key lemma and show how it implies the desired separation.
Further, w 1 u + w 1 v = 2U only holds when the budget is split equally across the transition between layers, i.e., w 2 u = w 2 v = B 3 = B 3 ; in this case, We defer the proof of Lemma 8 to Appendix B.1, and conclude the proof of separation by showing that Lemma 8 implies the following corollary: Corollary 4. The ex-post maximin value is strictly less than U .
Proof. Observe that the minimum reward over all agents, min{w 1 u , w 1 v }, is upper bounded by w 1 Thus, by Lemma 8, we have that min{w 1 u , w 1 v } ≤ w 1 u +w 1 v 2 ≤ U . If w 1 u + w 1 v < U , the result holds. Hence, we only need to consider the case when w 1 u + w 1 v = U . In this case, the budget split is given by B 1 = B 2 = B 3 = B/3 by Lemma 8. We assume with loss of generality that w 2 u ≥ w 2 v (otherwise invert the roles of u 2 and v 2 ); note that when the budget is small enough, it must be the case that w 2 1 , w 2 2 are necessarily bigger than the rewards on any node in layer 2 in I 2 (as B tends to 0, the rewards on nodes in the second layer in I 1 tend to 1/4 while the rewards on nodes in I 2 tend to 0). This directly implies that there exists an optimal maximin solution in which all of the budget B/6 allocated to improving edges (remembering that we need to spend half the budget, i.e. B/6, decreasing edges in I 2 for our matrix to remain stochastic) is allocated to (u 1 , u 2 ) and (v 1 , u 2 ). Let δ ∈ [0, 1] be such that the probability transition of edge (u 1 , u 2 ) is set to 1 2 + δ B 6 , and the probability transition for (v 1 , u 2 ) is set to (1 − δ) B 6 . We have that there exists δ such that noting that all other transitions to nodes in I 2 yield reward 0, as no budget has been invested to increase their rewards, by Lemma 8. Since w 2 u ≤ 1 2 + B 6 2 , it must be that w 2 u = 1 2 + B 6 2 and w 2 v = 1/4, otherwise we would have w 1 u + w 1 v < 2U which is a contradiction. This implies in particular that A simple calculation shows that for B small enough, which concludes the proof.

B.1 Proof of Lemma 8
We prove the lemma by proving a similar result at each layer by induction, starting backward from the penultimate layer.
Lemma 9. For any layer L i with i ∈ {1, 2, 3}, we have The first inequality is tight at layer L i only when B ≥i is split equally across the transition between layers to the right of L i .
We note that the above lemma applied at layer 1 directly gives that w 1 u + w 1 v ≥ 2U only when B 1 = B 2 = B 3 = B 3 when equality holds. The second part of Lemma 8 holds from applying Lemma 9 at layer 2 with B 2 = B 3 = B 3 or equivalently, B ≥2 = 2B 3 .
Proof. Note that this lemma is trivially true for any layer L i when B ≥i = 0. Henceforth, we only look at layer L i when B ≥i > 0. We begin by proving the lemma statement for Layer L 3 and work backwards towards layer L 1 . Note that w 3 u + w 3 v is maximized by spending B ≥3 /6 = B 3 /6 on edges from either u 3 or v 3 to the reward node u 4 with reward 1. This gives us w 3 u + w 3 v ≤ 1 2 + 1 2 + B ≥3 . Without loss of generality (due to the symmetry in the instance), let w 3 u ≥ w 3 v . Then w 3 u is maximized by spending all the budget B ≥3 on edge (u 3 , u 4 ), i.e., path P 1 (in the other case, all the budget is spent on path P 2 ). Thus, max{w 3 u , w 3 v } ≤ 1 2 + B ≥3 . Thus, both parts of the lemma are true for Layer L 3 . Now, let us assume our induction hypothesis holds at layer L i+1 . Consider layer L i . Let us assume w.l.o.g that w i+1 u ≥ w i+1 v . To maximize w i u + w i v , it is easy to see that all budget must be spent on edges from u i or v i to u i+1 . Thus, we get: where the second and second-to-last inequalities follow from our induction hypothesis. When i = 2, the above bound becomes 1 4 which is uniquely maximized (given total budget B ≥2 for layers more than 2) if and only if B 2 = B 3 = B ≥3 . When i = 1, this bound becomes Note that P f ≥ 1 is always true, by definition. The proof of the other two cases when B ≤ 2w is based on Example 1. We divide the analysis of the construction into the following cases: 1. B ≤ 2. It is easy to see that OP T SW = B 2 (1 − (w − 1)ε), and is achieved by the following transition matrix: Now note that the maximin solution is unique (and in particular, is the maximim solution with the highest social welfare), and this unique maximin solution splits the budget evenly among the starting nodes and yields social welfare B 2w , via transition matrix Therefore, we have that and lim ε→0 P f (ε) = w.
2. Now, consider the case when 2 ≤ B ≤ 2w. On the one hand, note that OP T SW ≥ 1 − (w − 1)ε, as setting M * 1 = 1 0 . . . 0 0 1 . . . 1 only requires a budget of 2 hence is feasible for Program (1). The unique maximin solution is still given by M f 1 and has welfare B 2w . As such, we have In particular, taking ε → 0, we get that a lower bound on the price of fairness is given by 2w B .
The proof for B ≥ 2w is immediate, noting that This can also be seen noting that increasing edges of M 0 t by a total amount of δB t requires decreasing other edges by a total amount of δB t for M t to be a stochastic matrix and so requires a total budget of 2δB t , which in turn implies that δ ≤ 1 2 necessarily. This implies that Applying the above inequality recursively, we have that

C.3.3 Proof of Lemma 4
First, we consider the case when B 2w ≤ 1. We focus on the transition from the second-to-last layer L k−1 to the last layer L k . Remember that on layer L k , R(1) = R ∞ . We re-number (w.l.o.g.) the nodes on layer k − 1 so that M 0 k−1 (1, i) ≥ B 2w for all nodes i ∈ [l], and M 0 k−1 (1, i) < B 2w for all nodes i ∈ {l + 1, . . . , k}, for some l ∈ {0, . . . , w}. Let us set Now, note that M k−1 ∈ M, as all coefficients are between 0 and 1 and the elements within the same column still sum to 1 by choice of α i,j 's. Finally, Therefore, (M k−1 , . . . , M 1 ) is a feasible solution for Programs 1 and 2 under budget B. Now, note that by construction, M k−1 (1, j) ≥ B 2w for all j ∈ [w]. In turn, this implies that for any distribution D k−1 , since w j=1 D k−1 (j) = 1 by virtue of D k−1 being a probability distribution, and because R(1) = R ∞ by choice of node indexing. In particular, for all j, D k−1 = M k−2 . . . M 1 e j is a probability distribution, hence Therefore, there exists a solution to Program (2) that has value B 2w R ∞ , implying any optimal solution to Program (2) has value at least B 2w R ∞ . In turn, such an optimal solution M f 1 , . . . , M f k−1 ∈ S f must have welfare which concludes the proof when B ≤ 2w. When B > 2w, let B = 2w. By the above, any optimal solution to maximin Program (2) with budget B = 2w has value at least B 2w R ∞ = R ∞ . This immediately implies that any optimal solution to Program (2) with budget B also has value at least R ∞ , since any feasible solution for budget B is feasible for budget B. In turn, any optimal solution to maximin Program (2) under budget B > 2w must have welfare at least R ∞ .

C.3.4 Proof of Lemma 5
The proof of the lemma uses the following Claim 3, that shows that an optimal solution to Program (2) spends all the budget B: