  Contact tracing is a key tool for managing epidemic diseases like HIV,
tuberculosis, and COVID-19. Manual investigations by human contact tracers
remain a dominant way in which this is carried out. This process is limited by
the number of contact tracers available, who are often overburdened during an
outbreak or epidemic. As a result, a crucial decision in any contact tracing
strategy is, given a set of contacts, which person should a tracer trace next?
In this work, we develop a formal model that articulates these questions and
provides a framework for comparing contact tracing strategies. Through
analyzing our model, we give provably optimal prioritization policies via a
clean connection to a tool from operations research called a "branching
bandit". Examining these policies gives qualitative insight into trade-offs in
contact tracing applications.
