Algorithms in Complex Environments
There are many settings in which we must analyze a complex system to make a decision. Two areas that have touched all our lives over the past few years are the COVID pandemic and the rising influence of social media. Aside from the fact that both the management of infections and content moderation are important, contemporaneous issues, they also have other commonalities. For example, both settings involve a network structure, and making decisions in each setting involves analyzing and optimizing a complex system. This thesis studies problems in managing infections and content moderation on social media. We develop theoretical models for each of these settings, and through analyzing our models, show how algorithms can help make decisions about complex systems. For example, in the case of managing infections, we develop a novel mathematical model of contact tracing and show a reduction from our model to the "branching bandits" problem (Weiss, 1988), a variant of the multi-armed bandits problem. Through analyzing this reduction, we show how to construct optimal policies within our model of contact tracing. In the context of content moderation on social media, we model the relationship between content creators and content consumers as a bipartite graph, where consumers are assigned to different creators. Through analyzing the structure of this graph, we discover a tight bound describing how satisfied consumers will be under a specific assignment.