Welfare-Maximizing Pooled Testing

[2206.10660] Welfare-Maximizing Pooled Testing Skip to main content Search Submit Donate Log in Search arXiv Press Enter to search · Advanced search Computer Science > Computer Science and Game Theory arXiv:2206.10660 (cs) [Submitted on 17 Jun 2022 ( v1 ), last revised 15 Aug 2026 (this version, v4)] Title: Welfare-Maximizing Pooled Testing Authors: Simon Finster , Michelle González Amador , Edwin Lock , Francisco Marmolejo-Cossío , Evi Micha , Ariel D. Procaccia View a PDF of the paper titled Welfare-Maximizing Pooled Testing, by Simon Finster and Michelle Gonz\'alez Amador and Edwin Lock and Francisco Marmolejo-Coss\'io and Evi Micha and Ariel D. Procaccia View PDF HTML (experimental) Abstract: Pooled testing increases the reach of scarce diagnostic resources, but optimally composing pools for individuals differing in infection risk and the utility they derive from a negative test is combinatorially challenging. We study the problem of maximizing the expected welfare of individuals cleared by a negative result, given a testing budget. Assigning a sample to several pools can raise welfare but is operationally burdensome; we show the restriction to non-overlapping allocations costs at most a factor of two for any budget or population, less under a pool-size cap at high health probabilities, and nothing when no health probability exceeds one-half. Welfare decomposes across non-overlapping pools, whereas evaluating overlapping allocations is #P-hard for pools of three or more. Finding optimal allocations is NP-hard and admits no FPTAS, with or without overlap, unless P = NP. We provide single-test routines and greedy algorithms with constant-factor guarantees. On real-world data, greedy achieves over 99% of optimal non-overlapping welfare in milliseconds, against hours for exact benchmarks. In a randomized field experiment at a Mexican research institute, our mechanism conditioned campus access on negative qPCR results. Relative to unrestricted access, we found no statistical evidence of adverse effects on participants' performance, learning, or mental health. Comments: Accepted at EC'23. (Exemplary track paper award) Subjects: Computer Science and Game Theory (cs.GT) Cite as: arXiv:2206.10660 [cs.GT] (or arXiv:2206.10660v4 [cs.GT] for this version) https://doi.org/10.48550/arXiv.2206.10660 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Simon Finster [ view email ] [v1] Fri, 17 Jun 2022 08:25:41 UTC (454 KB) [v2] Mon, 12 Jun 2023 14:35:48 UTC (7,395 KB) [v3] Wed, 20 Sep 2023 19:32:31 UTC (7,030 KB) [v4] Sat, 15 Aug 2026 22:25:46 UTC (287 KB) Full-text links: Access Paper: View a PDF of the paper titled Welfare-Maximizing Pooled Testing, by Simon Finster and Michelle Gonz\'alez Amador and Edwin Lock and Francisco Marmolejo-Coss\'io and Evi Micha and Ariel D. Procaccia View PDF HTML (experimental) TeX Source view license Current browse context: cs.GT < prev | next > new | recent | 2022-06 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar export BibTeX citation Loading... BibTeX formatted citation × loading... Data provided by: Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer ( What is the Explorer? ) Connected Papers Toggle Connected Papers ( What is Connected Papers? ) Litmaps Toggle Litmaps ( What is Litmaps? ) scite.ai Toggle scite Smart Citations ( What are Smart Citations? ) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv ( What is alphaXiv? ) Links to Code Toggle CatalyzeX Code Finder for Papers ( What is CatalyzeX? ) DagsHub Toggle DagsHub ( What is DagsHub? ) GotitPub Toggle Gotit.pub ( What is GotitPub? ) Huggingface Toggle Hugging Face ( What is Huggingface? ) ScienceCast Toggle ScienceCast ( What is ScienceCast? ) Demos Demos Replicate Toggle Replicate ( What is Replicate? ) Spaces Toggle Hugging Face Spaces ( What is Spaces? ) Spaces Toggle TXYZ.AI ( What is TXYZ.AI? ) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower ( What are Influence Flowers? ) Core recommender toggle CORE Recommender ( What is CORE? ) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs . Which authors of this paper are endorsers? | Disable MathJax ( What is MathJax? ) We gratefully acknowledge support from our major funders , member institutions , , and all contributors. About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab) Major funding support from

Related documents

• Welfare-Maximizing Pooled Testing#611218
• Dynamic Welfare-Maximizing Pooled Testing#1104951
• An Argument Against Drug Testing Welfare Recipients#776161
• Social welfare law A#456116
• Social welfare law B#278269