From as early as the Roman Empire to the present day, governments have grappled with how best to respond to political violence from organized insurgent groups. In response to insurgent groups, some governments have emphasized a direct military response or what is often called 'attrition'. Other states have stressed a softer, political strategy or what is often called the 'hearts and minds' approach. Either approach places the population at the center of a struggle between the government and violent dissidents. Despite numerous works emphasizing either 'attrition' or 'hearts and minds', few theoretical studies have attempted to compare their relative success. Using an agent-based computational model, we examine which approach is more successful at quelling insurgencies and find that a hearts and minds approach is superior to an attrition strategy. We illustrate the model with insights from the Iraqi insurgency and, more generally, the model has implications for other insurgencies, such as in Chechnya.