Dynamic, Welfare-Maximizing Pooled Testing

Abstract

From isolated cases to global pandemics, testing for disease is fundamental to modern medicine. However, shortages of time, testing supplies, and staff means that it is often not possible for each biological sample to be individually tested. Thus, pooled testing is often used by the American Red Cross, medical clinics across the United States, and health centers throughout the Global South. Under pooled testing, biological samples are grouped together and tested as one sample. In this thesis, I first build upon the work of Finster et al., who developed a general model for this problem. I first provide practical implementations for the algorithms theoretically presented there, and develop methods to determine the posterior probability of health given a history of test results. I then introduce novel algorithms to improve pooled testing assignments by using a dynamic approach. In this setting, tests are sequentially assigned, increasing the expected welfare of pooled testing by conditioning on the results of past tests before determining the next. I develop and discuss four algorithms under the dynamic setting: one that computes the optimal dynamic testing allocation, a quicker but less optimal algorithm that uses a greedy heuristic, and two classes of machine learning-based algorithms, one using supervised learning and one using reinforcement learning. I evaluate these algorithms by their computational complexity, optimality guarantees, and performance across various testing instances. My results show that the benefits of dynamic testing are significant, especially under real-world constraints. While the optimal dynamic testing allocation is welfare-maximizing, the computational complexity of the algorithm makes it infeasible for practical use. The greedy dynamic-assignment algorithm yields an increase in welfare of over 2.75% compared to the previous state-of-the-art algorithm for large populations and outperforms this benchmark in over 53% of instances. While the performances of the machine learning-based algorithms are not currently competitive, the results suggest promise and motivate further work on such an approach. I also use the empirical results to discuss how various changes in constraints, such as testing budget, affect the variance of welfare yielded under dynamic plans. The results show that current pooled testing practices can be meaningfully improved through dynamic assignment, particularly through the greedy dynamic-assignment algorithm. Adopting the proposed methods would result in a variety of welfare-increasing outcomes, from family members being able to visit immunocompromised loved ones more often to an increased number of life-saving blood donations delivered to patients in need.