Dynamic Welfare-Maximizing Pooled Testing

arXiv:2601.22419v2 Announce Type: replace-cross Abstract: Pooled testing uses one test to certify several agents as healthy when the pooled result is negative. We study a budget-constrained welfare problem in which agents have heterogeneous utilities and independent prior probabilities of being healthy. Welfare is earned when an agent is certified healthy, and a dynamic policy may choose each pool after observing earlier test outcomes. We ask how much such adaptation can improve over a static allocation that fixes all pools in advance. Our main result proves that the optimal dynamic policy has value at most twice that of the optimal static overlapping allocation, for every population, test budget, and pool-size cap. The proof samples a path through the dynamic policy using an independent health profile, randomly thins the selected pools, and compares the resulting static allocation with the dynamic policy one agent at a time. A Boolean-cube argument proves the comparison on uniform subcubes, and a complementary-profile coupling lifts the result to arbitrary heterogeneous product priors. We also identify regimes in which adaptivity has no value, show that strict adaptive gains require re-pooling agents after positive tests, and give a three-agent instance in which adaptation is strictly beneficial. Exact-Joint Greedy obtains a $1/(e+1)$ fraction of optimal static overlapping welfare. The static non-overlapping Greedy algorithm of Finster et al. has the same guarantee, hence our factor-two theorem newly implies that each is a $2(e+1)$-approximation to the optimal dynamic policy. Finally, a reproducible exact small-instance study compares the dynamic and static benchmarks and greedy policies. The appendix records separate exploratory results for Gibbs-marginal and reinforcement-learning approaches at larger scales.

Abstract:Pooled testing uses one test to certify several agents as healthy when the pooled result is negative. We study a budget-constrained welfare problem in which agents have heterogeneous utilities and independent prior probabilities of being healthy. Welfare is earned when an agent is certified healthy, and a dynamic policy may choose each pool after observing earlier test outcomes. We ask how much such adaptation can improve over a static allocation that fixes all pools in advance. Our main result proves that the optimal dynamic policy has value at most twice that of the optimal static overlapping allocation, for every population, test budget, and pool-size cap. The proof samples a path through the dynamic policy using an independent health profile, randomly thins the selected pools, and compares the resulting static allocation with the dynamic policy one agent at a time. A Boolean-cube argument proves the comparison on uniform subcubes, and a complementary-profile coupling lifts the result to arbitrary heterogeneous product priors. We also identify regimes in which adaptivity has no value, show that strict adaptive gains require re-pooling agents after positive tests, and give a three-agent instance in which adaptation is strictly beneficial. Exact-Joint Greedy obtains a $1/(e+1)$ fraction of optimal static overlapping welfare. The static non-overlapping Greedy algorithm of Finster et al. has the same guarantee, hence our factor-two theorem newly implies that each is a $2(e+1)$-approximation to the optimal dynamic policy. Finally, a reproducible exact small-instance study compares the dynamic and static benchmarks and greedy policies. The appendix records separate exploratory results for Gibbs-marginal and reinforcement-learning approaches at larger scales.

34 pages, 4 tables. Substantially revised and expanded; adds a uniform factor-two bound on the adaptivity gap, new structural and approximation results, and updated exact experiments. Edwin Lock added as a coauthor

Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI)

arXiv:2601.22419 [cs.GT]

(or arXiv:2601.22419v2 [cs.GT] for this version)

Off-topic for aiqbench

Dynamic Welfare-Maximizing Pooled Testing

Related coverage