Pipeline Interventions
summary
Layered graphical model where agents follow stochastic transition matrices and a central planner pays convex costs to change those matrices under budget B; algorithms use dynamic programming with epsilon-net discretization to produce near-optimal budget splits but require constant layer width W and lose about K·ε welfare over K layers. Maximin objective needs tracking per-start distribution; maximin is NP-hard to approximate (reduction from vertex cover) so there is a hardness via reduction from vertex cover. For linear costs the price of fairness depends only on W and B.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:22Decisions are made along pipelines...
- 1:14with disparities at each stage
- 1:59Q: where to intervene to eliminate disparities?
- 3:33Contribution 1: stylized pipeline intervention model on layered graphs Starting layer
- 4:33A stylized pipeline intervention model
- 7:51Cost function
- 11:50ADP approach to finding near-optimal SW
- 13:35Start with final layer
- 14:47Discretizing DK
- 15:42Guarantees of our algorithm
- 17:27Super-polynomial dependencies on width a unavoidable
- 21:19Price of fairness results
- 23:06Remarks and future directions
related talks
01h 10mMulti-Dimensional and Non-Linear Mechanism Design and Approximation II
51mMin-max Optimization: From Complexity to Algorithms
35mOnline Optimization and Learning Under Long-Term Convex Constraints and Objectives
01h 00mMin-Max Optimization from a Dynamical Systems Viewpoint
57mComputationally Efficient Alternatives to Nonconvex-Nonconcave Min-Max Optimization
38mFusing Machine Learning and Mixed Integer Linear Programming
44mPlatforms for Efficient and Incentive-Aware Collaboration
30mPolicy Evaluation under Interference