Overcoming conflicts of interest about where to go and what to do is a primary challenge of group-living. The behavioural strategies organisms use to reach consensus decisions are central to understanding the evolution of social complexity. Democratic processes underlie collective dynamics across a wide range of species, but it remains unknown if similar mechanisms apply when groups are strongly stratified. By simultaneously tracking the movements of members of a wild baboon troop using high-resolution GPS telemetry, we show that shared decision-making governs collective movement decisions, even in these socially complex, highly stratified societies. Baboons are more likely to follow when there is strong directional agreement among multiple movement initiators. When initiators propose movement directions that are different, followers compromise by moving in the average of the proposed directions, but only if this difference is small. If the difference between proposed directions exceeds a critical angle, followers move in one direction or the other, and choose based on a majority rule. Our results highlight the importance of explicitly considering the geometry of decision-making in mobile animal groups, and suggest that collective action based on relatively simple rules may be widespread even in complex animal societies.