Large brain size in mammals has been related to the number and complexity of social relationships, particularly social alliances within groups. The largest within–group male alliance known outside of humans is found in a social network (>400) of Indian Ocean bottlenose dolphins (Tursiops aduncus) in Shark Bay, Western Australia. Members of this dolphin ‘super–alliance’ cooperate against other alliances over access to females. Males within the super–alliance form temporary trios and occasionally pairs in order to consort with individual females. The frequent switching of alliance partners suggests that social relationships among males within the super–alliance might be relatively simple and based on an ‘equivalence rule’, thereby allowing dolphins to form large alliances without taxing their ‘social intelligence’. The equivalence model predicts that the 14 males in the super–alliance should not exhibit differences in alliance stability or partner preferences. However, data from 100 consortships do not support the equivalence hypothesis. The 14 males exhibited striking differences in alliance stability and partner preferences suggesting that the super–alliance has a complex internal structure. Further, within the super–alliance, alliance stability correlates with consortship rate, suggesting that differentiated relationships within the super–alliance are based on competition for access to females.