🤖 AI

Optimizing Health Coverage in Ethiopia: A Learning-augmented Approach and Persistent Proportionality Under an Online Budget

This paper presents Health Access Resource Planner (HARP), a learning-augmented optimization tool developed in collaboration with Ethiopian health authorities to maximize population health coverage under budget uncertainty while ensuring region-specific proportionality targets are met through sequential facility planning.

Original authors: Davin Choo, Yohai Trabelsi, Fentabil Getnet, Samson Warkaye Lamma, Wondesen Nigatu, Kasahun Sime, Lisa Matay, Milind Tambe, Stéphane Verguet

Published 2026-06-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Davin Choo, Yohai Trabelsi, Fentabil Getnet, Samson Warkaye Lamma, Wondesen Nigatu, Kasahun Sime, Lisa Matay, Milind Tambe, Stéphane Verguet

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine Ethiopia as a massive, bustling city with over 130 million people living in thousands of neighborhoods. The government wants to build "comprehensive health posts" (like fully stocked community clinics) to ensure everyone gets essential care. However, they face a classic problem: They have a limited budget and a lot of work to do. They can't build all the clinics at once; they have to choose which ones to build each year for the next five years.

This paper introduces a smart planning tool called HARP (Health Access Resource Planner) to help the Ministry of Health make these tough choices. Here is how it works, broken down into simple concepts:

1. The Problem: The "Puzzle" of Limited Resources

Think of the country as a giant jigsaw puzzle. The pieces are potential locations for new clinics.

The Goal: Place the pieces so that the most people can reach a clinic within a 2-hour walk.
The Catch: You can only place a few pieces each year (because of the budget).
The Twist: You also have to be fair. You can't just build all the clinics in the richest or most crowded areas. You have to ensure that poorer districts or those with specific health needs (like high rates of home births) also get their fair share of new clinics.

The challenge is that you don't know exactly how much money you'll have next year, and you can't take back a decision once you've built a clinic.

2. The Solution: A "Smart Assistant" (HARP)

The authors created HARP, a digital tool that acts like a super-smart assistant for the planners. It uses math to figure out the best spots to build clinics over time. It does two main things:

A. The "Fairness" Rule (Proportionality)

Imagine you are distributing pizza slices to a group of friends. Some friends are very hungry (high need), and some are less hungry.

Old Way: Just give slices to whoever is loudest or closest.
HARP Way: HARP ensures that every friend gets a slice proportional to their hunger. If a district has a high rate of mothers giving birth at home, HARP makes sure that district gets a "slice" of the new clinics, even if it's not the most crowded place. It keeps a running tally to make sure no one is left behind as the years go by.

B. The "Expert + AI" Team-Up (Learning-Augmented)

Sometimes, the government planners already have a list of where they think they should build clinics based on their experience and local knowledge.

The Old Approach: Either ignore the experts and let the computer decide, or just follow the experts blindly.
The HARP Approach: HARP treats the experts' list as a "draft." It looks at that draft and asks, "Can we tweak this to make it even better?"
- If the experts are right, HARP agrees and keeps the plan.
- If the experts missed a great spot, HARP swaps in a better option.
- The Safety Net: Even if the experts are wrong, HARP guarantees it won't do worse than a standard computer algorithm. It's like having a safety harness: you get the benefit of human wisdom without the risk of human error.

3. How They Tested It

The researchers didn't just write theory; they tested HARP with real data from three regions in Ethiopia (Afar, Benishangul Gumuz, and Somali).

The Test: They simulated building clinics over 5 years with different budgets.
The Result:
- Fairness: When they told HARP to prioritize areas with poor maternal care, it successfully built clinics there, whereas a standard "greedy" computer approach (which just picks the biggest crowds) ignored those areas.
- Efficiency: HARP managed to be fair without losing much overall coverage. It's like getting a fair distribution of pizza without wasting any slices.
- The "Expert" Boost: In some districts, when they fed HARP the planners' original "expert" list, HARP was able to improve the plan, covering about 20% more people than the experts' original list alone.

4. The Bottom Line

This paper presents a decision-support tool. It doesn't build the clinics itself; it tells the government where to build them.

It handles uncertainty: It works even if the budget changes from year to year.
It handles fairness: It ensures specific groups get the care they need, not just the most convenient groups.
It respects humans: It uses expert advice as a starting point and improves upon it, rather than replacing human judgment.

The authors emphasize that this is a proof of concept. They have shown the math works and the tool performs well in simulations with real Ethiopian data, but they are not making official policy recommendations. They are simply handing the Ministry of Health a powerful new compass to navigate the difficult journey of expanding healthcare.

Technical Summary: Optimizing Health Coverage in Ethiopia via HARP

1. Problem Formulation

The paper addresses the challenge of sequentially planning the construction and upgrading of health facilities in Ethiopia under conditions of budget uncertainty and the need for equitable distribution. The Ethiopian Ministry of Health aims to upgrade over 2,000 health posts to "comprehensive" status to meet Universal Health Coverage goals. However, limited annual budgets and varying regional priorities (e.g., prioritizing population density vs. poverty levels) necessitate a strategic, data-driven approach.

The authors formalize this as the Maximizing a non-decreasing submodular function under online partition and global proportional constraints (MOPGP) problem.

Objective: Maximize a non-decreasing submodular function $f$ representing the total population covered within a 2-hour travel time over a multi-year horizon.
Constraints:
1. Online Budget: Budgets $b(t)$ are revealed incrementally at each time step $t$ (year). Decisions are irrevocable.
2. Global Proportionality: The selection must satisfy type-level proportionality constraints (e.g., ensuring a minimum fraction of facilities are built in specific districts) at every time step.
3. Type Feasibility: To handle the impossibility of meeting strict proportionality targets at every single step due to budget constraints, the authors introduce a "type feasible selection" definition. This requires maximizing a "satisfaction ratio" $\alpha_{min}$ (the minimum ratio of achieved proportion to target proportion) and, among sets achieving the best ratio, minimizing the number of types that are "saturated" (i.e., have no remaining candidates to improve the ratio). This structure is designed to hedge against future budget uncertainty.

2. Methodology

The paper proposes the Health Access Resource Planner (HARP), a decision-support tool built on two primary algorithmic components:

A. Learning-Augmented Single-Step Planning

Recognizing that regional planners often possess expert recommendations (advice) for facility placement that may not be globally optimal but encode valuable local knowledge, the authors develop a learning-augmented algorithm for single-step decisions.

Approach: The algorithm takes an expert advice set $A$ of size $b$ and generates subsets $A_i$ (for $i=0$ to $b$ ). For each subset, it greedily fills the remaining $b-i$ slots using elements from the ground set to maximize marginal gain.
Guarantees: The algorithm outputs the best selection found among these combinations. It is proven to be 1-consistent (if the advice is optimal, the output is optimal) and $(1-1/e)$ -robust (if no advice is used, it performs as well as a standard greedy algorithm). This allows planners to refine expert plans without discarding them, ensuring performance never degrades below the baseline greedy approach.

B. Multi-Step Planning under Uncertainty

For the sequential, multi-year planning horizon, the authors propose a greedy algorithm called MultistepPlanning.

Mechanism: At each time step, the algorithm calculates the number of facilities $x_q(t)$ to build in each district $q$ to maintain the target global proportions over the cumulative budget. It then constructs a partition matroid based on these quotas and performs a greedy selection of facilities within the current year's candidate set $V(t)$ .
Theoretical Guarantees: The algorithm outputs a $\sigma$ -type feasible selection (a specific tie-breaking rule for types). The authors prove that if at least $k$ elements of each type are selected per round, the algorithm achieves an approximation ratio of $\frac{k}{k+1}$ relative to the optimal $\sigma$ -type feasible selection. Furthermore, due to the online nature of budget arrivals, the algorithm achieves a $1/2$ -approximation relative to the offline optimum in the worst case.

3. Key Contributions

Problem Formalization: The introduction of MOPGP, a novel optimization framework that integrates online budget constraints with global proportional fairness constraints, specifically tailored for sequential facility planning.
Algorithmic Innovation:
- A learning-augmented algorithm that integrates expert advice into submodular maximization, offering strong worst-case guarantees while improving upon expert plans when possible.
- A greedy multi-step algorithm with provable approximation bounds that operationalizes the abstract "type feasibility" definition for real-world planning.
Empirical Validation: The development and testing of HARP on real-world data from Ethiopia (regions of Afar, Benishangul Gumuz, Somali, and Sidama), utilizing high-resolution population forecasts and travel-time friction surfaces.

4. Experimental Results

The authors evaluated HARP using data from 2026–2030 across four Ethiopian regions under three distributional policies (DP):

DP0: No constraints (unconstrained greedy).
DP1: Proportions based on unassisted home birth rates.
DP2: Proportions based on inverse postnatal care coverage.

Key Findings:

Coverage vs. Equity: Imposing proportional constraints (DP1, DP2) resulted in minimal efficiency loss in total population coverage compared to the unconstrained baseline (DP0). The "price of fairness" (ratio of efficiency loss) was close to 1, indicating that equitable allocation does not significantly compromise overall coverage.
Equity Improvement: The constrained policies significantly improved the minimum satisfaction ratio ( $\alpha_{min}$ ) for the targeted districts compared to the unconstrained baseline, which often resulted in $\alpha_{min} = 0$ for specific districts.
Learning-Augmented Efficacy: In a retrospective analysis of 25 districts, the learning-augmented approach outperformed both the expert-curated selection and the standard greedy baseline in 25 instances, demonstrating that the algorithm can effectively refine existing expert plans.

5. Significance and Claims

The paper positions HARP as a proof of concept rather than an official policy recommendation. Its primary significance lies in:

Bridging Theory and Practice: It demonstrates how complex theoretical constraints (online submodular optimization with fairness) can be applied to real-world public health infrastructure planning.
Respecting Expertise: By utilizing a learning-augmented framework, the tool respects the institutional memory and domain expertise of Ethiopian planners while providing algorithmic rigor to improve upon suboptimal manual decisions.
Scalability and Adaptability: The framework is designed to be a shared decision-support tool that allows different regions to customize allocation strategies based on local priorities (e.g., targeting poverty vs. density) without requiring a complete overhaul of the planning process.

The authors emphasize that while the empirical results are promising, the findings are intended to illustrate the potential of such optimization frameworks in supporting equitable, data-driven infrastructure decisions in resource-constrained settings.