Pipeline Interventions

Eshwar Ram Arunachaleswaran (), Sampath Kannan (), Aaron Roth () and Juba Ziani ()
Additional contact information
Eshwar Ram Arunachaleswaran: University of Pennsylvania, Philadelphia, Pennsylvania 19104
Sampath Kannan: University of Pennsylvania, Philadelphia, Pennsylvania 19104
Aaron Roth: University of Pennsylvania, Philadelphia, Pennsylvania 19104
Juba Ziani: Georgia Institute of Technology, Atlanta, Georgia 30318

Mathematics of Operations Research, 2022, vol. 47, issue 4, 3207-3238

Abstract: We introduce the 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 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 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 fully polynomial-time approximation scheme) 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 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.

Keywords: Primary: 91B32; 91B06; 68W25; 68Q25; interventions for fairness; fairness in navigating life paths; social welfare; maximin welfare; budget-constrained optimization (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1245 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:4:p:3207-3238

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().