Indeed, neocortex size of primates is correlated not only with social-group size but also with social savviness. An outgrowth of this arms race seems to have been a blossoming of many human social instincts, both the good (friendships, reciprocity, reconciliation, trust, sharing) and the bad (tribalism, nepotism, deception). While many aspects of these behavioral changes did not require any particularly clever new brain systems, there was indeed an intellectual feat underlying this politicking: the ability to engage in theory of mind.
