The paper studies how to learn optimal treatment assignment policies when you face both a budget constraint (limited resources) and a coverage constraint (must treat at least a minimum number of people). The author shows the problem has a knapsack structure and the optimal policy can be characterized by a threshold rule involving shadow prices for both constraints. The linear programming relaxation has a tight integrality gap, meaning continuous solutions are asymptotically equivalent to discrete allocations. Two practical algorithms are analyzed: a Greedy-Lagrangian approach that closely approximates the optimum, and a rank-and-cut method that works well unless cost heterogeneity interacts with a binding coverage constraint.
Main takeaways:
- Optimal policy learning with both budget and minimum-coverage constraints has a knapsack-type structure
- The optimal policy is an affine threshold rule involving shadow prices for budget and coverage
- Linear programming relaxation is asymptotically tight (O(1) integrality gap)
- Greedy-Lagrangian algorithm achieves near-optimal performance in finite samples
- Rank-and-cut works well when coverage is slack or costs are homogeneous, but misallocates when cost heterogeneity meets binding coverage constraints