Our burgeoning reliance on technology has resulted in the integration of algorithms into many real-world decision-making problems. The decisions of these algorithms can have far-reaching consequences, affecting where people live and work, determining who has access to which opportunities or resources, and helping to inform our decisions when crafting public health policies. In light of this, it is important that these decision-making algorithms respect our societal ideals and incorporate our understanding of social dynamics that influence the problems in nuanced ways. In this dissertation, I will consider three different social phenomena that arise in three decision-making problems. First, I'll look at a problem of resource allocation under multi-faceted priorities. Next, I'll consider the problem of forming optimal work groups under a variety of models of team synergy. Finally, I'll consider the problem of estimating the effect of a treatment on a population in the presence of spillover effects in their social network. In each of these problems, I'll posit a model for the corresponding social dynamics and leverage the inherent combinatorial structure in the model to develop an optimal or near-optimal decision-making policy.