Adaptive networks driven by partner choice can facilitate coordination among humans in the graph coloring game: Evidence from a network experiment

Background Many instances of coordination problems in social networks can be characterized by the well-known graph coloring game—a task in which agents are incentivized to choose an attribute, represented by a color, to be different from linked neighbors. Past work on this topic, however, is limited to static networks of specific topologies of interest. Purpose This study aims to explore whether dynamic networks, where players can choose their partners, perform better in the graph coloring game. Research Design We replicate the conventional graph coloring game experiment and introduce a new version where players can change their network neighbors. Study Sample and Data Collection We recruited over 300 human participants for the experiment, with each session involving an average of 20 participants per network. Results We found that dynamic networks that allow agents to switch network neighbors works more effectively and efficiently in solving coloring conflicts than static networks in which people are allowed to change color alone. The networks in the experiment updated by people’s selection of neighbors tend to evolve to a state similar in structure to the small-world network characterized by short path distance and high triadic clustering. Conclusion We argue that a self-organized approach demonstrated by our experiment can inspire search of behavioral strategies and network topologies for solving coordination problems in social networks.