The social organization of mobile hunter-gatherers has several derived features, including low within-camp relatedness and fluid meta-groups. Although these features have been proposed to have provided the selective context for the evolution of human hyper-cooperation and cumulative culture, how such a distinctive social system may have emerged remains unclear. I present an agent-based model suggesting that, even if all individuals in a community seek to live with as many kin as possible, within-camp relatedness is reduced if men and women have equal influence in selecting camp members. This model closely approximates observed patterns of co-residence among Agta and Mbendjele BaYaka hunter-gatherers. The results suggest that pair-bonding along with increased gender egalitarianism in human evolutionary history may have had a transformative effect on human social organization.