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

Davin Choo, Yohai Trabelsi, Fentabil Getnet, Samson Warkaye Lamma, Wondesen Nigatu, Kasahun Sime, Lisa Matay, Milind Tambe, Stéphane VerguetarXiv 2025 · DOI · arXiv

Introduction

Expanding healthcare access in developing nations like Ethiopia requires navigating complex trade-offs between maximizing population coverage and ensuring regional equity. This paper introduces the Health Access Resource Planner (HARP), a decision-support tool designed to assist the Ethiopian Ministry of Health in the strategic placement of health facilities. By framing facility placement as a novel optimization problem, the authors provide a principled framework to manage limited annual budgets and strict fairness requirements.

Problem Formulation: Budget Uncertainty and Equity

Ethiopia aims to achieve Universal Health Coverage by upgrading thousands of basic health posts to "comprehensive" status. However, planners face two primary challenges:

  1. Online Budgeting: Funding arrives in annual, uncertain increments, complicating long-term infrastructure planning.
  2. Proportional Distribution: To maintain social equity, upgrades must be distributed fairly across diverse districts (proportionality), rather than solely clustering in high-density urban centers.

The authors formalize this as Maximizing a non-decreasing submodular function under Online Partition and Global Proportional constraints (MOPGP).

Map of Ethiopia showing population density (left) and existing health facility locations (right).

Methodology

The HARP framework utilizes submodular optimization to model the "diminishing returns" of healthcare coverage—where adding a facility near an existing one provides less marginal benefit than placing it in an unserved region.

The core algorithmic contributions include:

  • Learning-Augmented Single-Step Planning: This algorithm integrates "advice" (e.g., human expert recommendations) with a greedy refinement process. It ensures the final selection is at least as effective as the advice while maintaining provable performance guarantees.
  • Multistep Planning under Uncertainty: This approach manages multi-year horizons by enforcing "type feasibility." It ensures that every annual allocation moves toward long-term proportionality targets, providing robustness against future budget fluctuations.

Data and Evaluation

The tool was evaluated using high-resolution spatial datasets, including WorldPop for 1km-grid population forecasts (2026–2030) and the Global Friction Surface to estimate walking travel times based on terrain. Evaluation focused on four Ethiopian regions: Afar, Benishangul Gumuz, Somali, and Sidama.

Key Insights

  • The Low Price of Fairness: Enforcing proportionality (ensuring each district receives its fair share) results in minimal loss of overall population coverage. Efficiency remains high even with strict equity constraints.
  • Human-AI Collaboration: The learning-augmented approach treats human expertise as a valuable input to be refined rather than replaced. This synergy leads to outcomes superior to those achieved by either experts or algorithms in isolation.
  • Robustness through Type Feasibility: By maintaining proportional balance at every step, the system remains resilient to sudden budget cuts or changes in funding availability.

Results

In retrospective analyses across 25 districts, the learning-augmented selection consistently outperformed both original expert-curated plans and standard greedy baselines.

Comparison of coverage outcomes: The learning-augmented approach (right) achieves higher coverage (67) than pure greedy (62) or expert advice (60) by strategically combining both.

Empirical tests confirmed that the MultistepPlanning algorithm achieves a $1/2$-approximation ratio relative to the offline optimum, even under significant budget uncertainty.

Limitations and Future Directions

While HARP provides a robust framework, it currently assumes facilities remain fully operational indefinitely, without accounting for staffing or supply chain issues. Future work could incorporate facility capacity constraints and more direct health outcome metrics. Additionally, extending the provable performance guarantees of the learning-augmented algorithm to the full multi-year horizon remains an open theoretical challenge.

Summary updated

Abstract

As part of nationwide efforts aligned with the United Nations' Sustainable Development Goal 3 on Universal Health Coverage, Ethiopia's Ministry of Health is strengthening health posts to expand access to essential healthcare services. However, only a fraction of this health system strengthening effort can be implemented each year due to limited budgets and other competing priorities, thus the need for an optimization framework to guide prioritization across the regions of Ethiopia. In this paper, we develop a tool, Health Access Resource Planner (HARP), based on a principled decision-support optimization framework for sequential facility planning that aims to maximize population coverage under budget uncertainty while satisfying region-specific proportionality targets at every time step. We then propose two algorithms: (i) a learning-augmented approach that improves upon expert recommendations at any single-step; and (ii) a greedy algorithm for multi-step planning, both with strong worst-case approximation estimation. In collaboration with the Ethiopian Public Health Institute and Ministry of Health, we demonstrated the empirical efficacy of our method on three regions across various planning scenarios.
BibTeX
@misc{choo2025optimizing,
  author = {Davin Choo and Yohai Trabelsi and Fentabil Getnet and Samson Warkaye Lamma and Wondesen Nigatu and Kasahun Sime and Lisa Matay and Milind Tambe and Stéphane Verguet},
  title = {{Optimizing Health Coverage in Ethiopia: A Learning-augmented Approach and Persistent Proportionality Under an Online Budget}},
  year = {2025},
  eprint = {2509.00135},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.00135},
}
Figure