Complex networks describe the structure of many socio-economic systems. However, in studies of decision-making processes the evolution of the underlying social relations are disregarded. In this report, we aim to understand the formation of self-organizing domains of cooperation ("coalitions") on an acquaintance network. We include both the network's influence on the formation of coalitions and vice versa how the network adapts to the current coalition structure, thus forming a social feedback loop. We increase complexity from simple opinion adaptation processes studied in earlier research to more complex decision-making determined by costs and benefits, and from bilateral to multilateral cooperation. We show how phase transitions emerge from such coevolutionary dynamics, which can be interpreted as processes of great transformations. If the network adaptation rate is high, the social dynamics prevent the formation of a grand coalition and therefore full cooperation. We find some empirical support for our main results: Our model develops a bimodal coalition size distribution over time similar to those found in social structures. Our detection and distinguishing of phase transitions may be exemplary for other models of socio-economic systems with low agent numbers and therefore strong finite-size effects.