Human groups show a variety of leadership structures from no leader, to changing leaders, to a single long-term leader. When a leader is deposed, the presence of a power vacuum can mean they are often quickly replaced. We lack an explanation of how such phenomena can emerge from simple rules of interaction between individuals. Here, we model transitions between different phases of leadership structure. We find a novel class of group dynamical behaviour where there is a single leader who is quickly replaced when they lose status, demonstrating a power vacuum. The model uses a dynamic network of individuals who non-coercively form and break alliances with one-another, with a key parameter modelling inequality in these alliances. We argue the model can explain transitions in leadership structure in the Neolithic Era from relatively equal hunter-gatherer societies, to groups with chieftains which change over time, to groups with an institutionalised leader on a paternal lineage. Our model demonstrates how these transitions can be explained by the impact of technological developments such as food storage and/or weapons, which meant that alliances became more unequal. In general terms, our approach provides a quantitative understanding of how technology and social norms can affect leadership dynamics and structures.