This paper surveys five human societal types – mobile foragers, horticulturalists, pre-state agriculturalists, state-based agriculturalists and liberal democracies – from the perspective of three core social problems faced by interacting individuals: coordination problems, social dilemmas and contest problems. We characterise the occurrence of these problems in the different societal types and enquire into the main force keeping societies together given the prevalence of these. To address this, we consider the social problems in light of the theory of repeated games, and delineate the role of intertemporal incentives in sustaining cooperative behaviour through the reciprocity principle. We analyse the population, economic and political structural features of the five societal types, and show that intertemporal incentives have been adapted to the changes in scope and scale of the core social problems as societies have grown in size. In all societies, reciprocity mechanisms appear to solve the social problems by enabling lifetime direct benefits to individuals for cooperation. Our analysis leads us to predict that as societies increase in complexity, they need more of the following four features to enable the scalability and adaptability of the reciprocity principle: nested grouping, decentralised enforcement and local information, centralised enforcement and coercive power, and formal rules.