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

Abstract

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.

Keywords

Graph coloring problem network experiment dynamic networks partner choice social coordination

Significance statement

Coordinating individual differences in talents and traits, such as the division of labor in teamwork and collaboration in team sports, is crucial for successful group performance. These coordination challenges can be modeled using the well-known graph coloring game from computer science. However, previous studies have primarily focused on static networks with specific topologies. In reality, both individual actions and the structure of social networks are subject to change and adaptation. Our research demonstrates how the adaptability of networks can enhance group performance in the graph coloring game. We suggest that the self-organizing approach observed in our experiment could inspire the development of behavioral strategies and network topologies to address coordination problems in social networks.

Introduction

Coordination is pivotal to the success of group functioning across a wide range of domains. In team sports, athletes coordinate their moves; in concerts, musicians synchronize their performances; in organizational administrations, board members work toward unanimity in group decision-making. For this kind of coordination, social networks play an important role in facilitating the reaching of consensus (Centola et al., 2018); on the other hand, it also explains how social divisions and even polarization of opinions could occur (Stewart et al., 2019 and see Jusup et al., 2022 for a review).

While the reach of consensus is a typical example of social coordination, there are other goals of coordination people attempt to achieve. In fact, quite on the contrary, sometimes we coordinate to minimize homogeneity. For example, in crowded open spaces, pedestrians coming from different directions adjust their moves to prevent collisions. In such cases, sharing the same direction creates more harm than benefit. In computer science, there exists an elegant task to characterize the coordination of heterogeneity: the graph coloring problem (Garey and Johnson, 1979; Jensen and Toft, 2011; Lewis, 2021).

The Graph Coloring Problem (GCP) presents a challenge in assigning an attribute, represented by a color, to each vertex in a network so that the color of any vertex differs from the colors of vertices linked by edges. Originally presented as a theoretical challenge, the problem finds applications in a variety of domains, ranging from channel allocation in communication networks (Janssen et al., 2000) and air flow management (Barnier and Brisset, 2004) to the emergence of the division of labor in the economy (Erikson and Shirado, 2021) and problem-solving in teamwork (Shore et al., 2015). These examples share a common goal to reduce network homophily, wherein actors of the same attribute are linked together, thereby increasing efficiency and facilitating innovation in teamwork.

While the coordination of heterogeneity in social networks has been characterized and theoretically investigated by the GCP, existing work along this line of research is limited to static networks. In this paper, we extend the research to dynamic networks driven by partner choice (Bravo et al., 2012; Chiang, 2010; Corten and Buskens, 2010; Jackson and Watts, 2002; Rand et al., 2011). Conducting a network experiment with human participants, we show that a dynamic network, which allows agents to switch network neighbors, is more effective and efficient in resolving coloring conflicts than static networks where individuals are only allowed to change color. We analyze the strategies people employ to coordinate their actions in solving the GCP. Taken together, our study demonstrates that a co-adaptation of network links and individual actions can solve coordination problems in social networks.

Related literature

Coordination problem and social networks

The success of social coordination is intriguing from a theoretical perspective. For example, economists and philosophers study the coordination problem in a game setting in which actors have multiple options, each conferring different values (Bicchieri, 2005; Schelling, 2006; Skyrms, 2004). While it is advantageous for individuals to choose the same option as others, the existence of multiple choices leads to a “multi-equilibria” selection problem. Scholars have utilized coordination games to explain why social norms, including some harmful ones, can emerge and remain stable for extended periods (Efferson et al., 2020; Mackie, 1996).

Social networks play a crucial role in the coordination problem for several reasons. Firstly, successful coordination frequently depends on understanding how significant others might behave. As social networks delineate the sphere of attention, the way individuals are interconnected inevitably shapes decisions regarding how to align with others in specific actions (Maroulis et al., 2020). In fact, social networks enable individuals to predict others’ behavior even in one-shot games where direct communication is not possible (Chwe, 1999).

Secondly, social networks confine actors to draw inferences about the global state from a local area. Collective behavior is better understood as a dynamic process in which individuals adjust their decisions based on observing how others behave. Consequently, the structure of social networks critically shapes how coordination dynamics unfold. However, researchers have yet to reach a consensus on which network properties are pivotal and how they influence coordination dynamics. Take network density for instance. While some studies suggest that network connectivity is linked to successful coordination (Kearns et al., 2006; McCubbins et al., 2009), others present conflicting results (Enemark et al., 2011), find no association (Hafner-Burton et al., 2009), or propose that its impact is contingent on more complex factors (Enemark et al., 2014). Network clustering provides another example: its influence on social coordination depends on the complexity of the task at hand (Centola and Macy, 2007). However, it is important to note that discrepancies in research findings regarding how a network attribute influences coordination dynamics can be attributed, in part, to the different tasks or games investigated in research.

All the discussions above treated social coordination as a challenge to reach a consensus among a group of people. In other words, in this case, coordination is equated with the pursuit of homogeneity. However, there are instances in which the goal of coordination is to maximize heterogeneity. Even in these cases, social networks could play an important role. In fact, such tasks have become an important challenge in theoretical computer science over the past decades, as we will briefly review below.

The graph coloring problem

The Graph Coloring Problem features a challenge to assign an attribute, represented by a color, to each vertex in a network so that the color of any vertex is different from the colors of vertices linked by edges (Garey and Johnson, 1979; Jensen and Toft, 2011). GCP is an important theoretical question in computer science and related areas (Malaguti and Toth, 2010). Scholars have developed useful algorithms for solving GCP dating back to earlier types such as the backtracking approach (Kubale and Jackowski, 1985) to more recent ones using heuristic approaches (Mostafaie et al., 2020). Enduring interest remains active in proposing novel algorithms, such as neural networks (Schuetz et al., 2022), to solve the problem more effectively and efficiently.

In an earlier series of studies, Kearns and colleagues formalized GCP as a decentralized coordination problem in social networks (Judd et al., 2010; Kearns et al., 2006, 2009). In their seminal experimental study (Kearns et al., 2006), each human participant, occupying a vertex in the network, is incentivized to choose a color different from those chosen by linked neighbors. They showed that network topology plays an important role in the game: Players solve GCP more successfully and efficiently in certain types of networks, such as lattices where each vertex has two links, than in networks characterized by a highly unequal distribution of node degree, such as those formed by preferential attachment dynamics (Barabási and Albert, 1999). Their studies successfully extended the investigation of GCP to modern network science, shedding light on how network topology influences the performance of GCP.

Progress notwithstanding, the existing literature primarily investigates GCP within predetermined, static networks. This limitation prompts us to consider what would occur if the network could be dynamically updated. The proposal of using a dynamic network approach to GCP can be traced back to the seminal paper by Kearns and colleagues (2006), where they noted, “Rather than imposing a chosen network structure on subjects, it would be interesting to consider scenarios in which the subjects themselves participated in the network formation process, while still allowing some variability of structure” (p. 827). It is rather surprising that, to the best of our knowledge, there has been no work thus far that attempts to relax the assumption of static networks in GCP. In this paper, we present the first study to extend GCP to dynamic networks, aligning with the direction proposed by Kearns and colleagues (2006) more than a decade ago.

So, how would a dynamic network make a difference to GCP? First, note that while players can change neighbors at will, the challenge of coordination in GCP remains. Similar to conventional GCP, either the choice of color or the selection of a neighbor is based on the past records of players, and there is always a risk of whether neighbors would behave as observed. While partner choice provides one more option for solving GCP, it also introduces an additional coordination challenge. Therefore, whether GCP can be solved more easily in dynamic networks than in static ones remains a question that warrants investigation.

Secondly, it is important to keep in mind that when networks change, so does the chromatic nature of the game; that is, the difficulty of solving GCP. Whether adaptive networks driven by partner choice would lead to specific network topologies friendly to the solvability of GCP remains an interesting question (Judd et al., 2010; Kearns et al., 2006, 2009). As it is inefficient and impractical to visit all network topologies, the endogenous formation of networks driven by partner selection can be treated as a decentralized learning process of the relationships between network topologies and the solutions of GCP. Relatedly, dynamic networks driven by actors’ link choices have been shown to play an important role in facilitating the emergence of a myriad of social behaviors (Perc and Szolnoki, 2010), ranging from prosocial actions, such as cooperation (Rand et al., 2011), coordination (Corten and Buskens, 2010; Jackson and Watts, 2002), fairness (Chiang, 2010), innovation (Young, 2011), and trust (Bravo et al., 2012), to antisocial behavior, such as spite (Fulker et al., 2021). We argue that it has a similar potential for coordinating individuals’ actions in GCP.

Method

Experiment design

We consider a lattice network as the default structure. Each node in the lattice has k = 6 neighbors. A player occupying a node in the network selects a color from a total of c = 4 colors.¹ We incentivize players to choose a color different from the colors chosen by their neighbors; the more neighbors whose colors differ from the focal player’s, the higher the score the player would attain. Scores are proportional to the payoffs players receive in the experiment.

We design two treatments to compare their performances in the game. In the “Static Network” (SN) treatment, the network is fixed, following the conventional design of GCP. In each round of this treatment, players can either choose a different color or keep the same color as the last round. In contrast, in the “Dynamic Network” (DN) treatment, in each round a player can: (a) change color, (b) change neighbors, or (c) stay put. We follow a within-subject design in the experiment: Participants in a session underwent the two treatments, the order of which was counterbalanced across sessions.

In the DN treatment, when changing a neighbor, a player first selects an existing neighbor to delete, followed by choosing a new neighbor from a list of actors currently unlinked to the focal player. In doing so, the number of edges or network density remains intact, mitigating the effect of connectedness on task performance in the network (Enemark et al., 2011, 2014; Kearns et al., 2006; McCubbins et al., 2009). Linking to a neighbor is a unilateral decision that can be achieved without the agreement of the added neighbor.² A player can change at most one neighbor in each round.

More specifically, in each round players are provided with the following information for decision-making: (1) the number of neighbors they are currently connected to; (2) the number of neighbors whose colors are different from theirs, and (3) their current scores, calculated as the ratio of (2) to (1) multiplied by 100. Whenever a player wants to change a neighbor, s/he can click on the nodes of the candidates to see the characteristics of the selected neighbor, including (1) the candidate’s past record regarding how often they changed color and changed neighbor, respectively. (2) the candidate’s current score (3) the candidate’s current number of neighbors.

Given the complexity of searching for solutions to GCP (NP-complete), for better experiment management, we adopt a game-termination rule specified as follows: The game ends when at least one of the following conditions is met: (a) when all players’ colors are different from those of their neighbors, that is, GCP is completely solved; or (b) when the game reaches T_max = 15 rounds^.3 (c) all players make no moves of changing colors or changing neighbors consecutively for two rounds.

Experiment procedure

We recruited a convenient sample of college students to participate in our experiment. Our recruitment advertisement was posted on a social media platform accessible to college students, offering financial compensation for participation. A total of 354 participants enrolled, with a mean age of 23.35 and a standard deviation of age of 5. They were randomly assigned to 16 different sessions based on their availability. During the experiment, three sessions encountered technical problems with computer communication, leading us to abort the experiment. The data from these abandoned sessions were not included in the reported data below. The average size of the remaining sessions (network size of GCP) is 20.85 (minimum = 15, maximum = 26, standard deviation = 3.65).

The experiment was conducted online, with the experiment platform programmed using the software oTree (Chen et al., 2016). In each session, participants first read the instructions for the game rules. These instructions also guided participants to preview snapshots of the interfaces they would see during the experiment, particularly those they could click on to receive important information for their decision-making in the game (see the appendix for example, snapshots of the interface). At the end of the instruction phase, we administered a comprehension test to ensure that participants fully understood the contents of the game.

Each session featured one DN and one SN treatment. As mentioned, the order of the two treatments was counterbalanced across sessions. Participants earned a score point in the game worth 1/30 of a US dollar. Payment was determined by the accumulated scores of the two treatments. We paid $3.33 for show-up.

Results

Performance in static versus dynamic networks

We plotted players’ scores over rounds in Figure 1. The results indicate that immediately after the game commenced, players scored significantly higher in the dynamic network (DN) than the static network (SN) treatment. Remarkably, in 77% of the DN sessions, all players managed to fully solve GCP before reaching the round limit of 15, whereas no session achieved this in SN. Further statistical analysis—a two-way repeated measures ANOVA—confirms the significant difference in scores between the two treatments. Table 1 demonstrates a notable variance in players’ scores over rounds (p < 10⁻¹⁵) and between treatments (p < 10⁻¹¹). Additionally, the superiority of the dynamic network over the static network in players’ scores becomes apparent across rounds, as indicated by the interaction effect of treatment and rounds (p < .03).

Figure 1.

Game performance of the DN and SN treatments and the naïve simulation model. Shaded areas represent the 95% confidence interval. Players can achieve perfect scores in the DN treatment, which cannot be achieved either in the SN treatment or in the simulation model that randomly rewires network ties.

Table 1.

Two-way repeated ANOVA comparing players’ performance across rounds in the two network treatments.

Variables	df	Sum of square	F	p-value
Round	1	273685	541.57	<2 × 10⁻¹⁶
Treatment	1	25224	49.914	1.74 × 10⁻¹²
Round × treatment	1	2458	4.865	0.0274
Residual	8122	4104517

So how does a dynamic network outperform a static network in solving the GCP? Can we attribute this solely to the opportunity to update network neighbors? To address this question, we conducted a naïve agent-based simulation to replicate the dynamic network treatment of our experiment, assuming, however, that players’ behavior is randomly determined during the game.

Specifically, we initiated the simulation by configuring a lattice network of identical size to each session of the experiment. Then, in each round, the simulated agents randomly decided, with an equal probability, whether to change color, switch neighbors, or remain in place. Whenever applicable, changes in colors or the selection of new neighbors were determined randomly. The simulation proceeded for the same number of rounds as in the experiment (T_max = 15 rounds), and we repeated the simulation 1,000 times.

We found that the average scores achieved in the simulation were significantly lower than the scores of players in the DN treatment of the experiment (refer to Figure 1). Surprisingly, they were even lower than the players’ performance in the SN treatment, indicating that simply rewiring static networks over time does not enhance performance in solving the GCP. In other words, the effectiveness of a dynamic network in GCP is not solely due to the alteration of network topology itself; rather, it hinges on the specific individuals to whom the links are rewired.

Temporal distribution of action types in static versus dynamic networks

If dynamic networks, driven by partner choice, outperform static networks in solving the GCP, would we expect participants to frequently change network neighbors in the experiment? Figure 2 compares the temporal distributions of the three types of actions chosen by players across rounds. We observed that, except in the early stages of the game, the action “stay put” remained the most dominant choice among players. The prevalence of this action did not differ significantly between the SN and DN treatments (Wilcox test, W = 153.5, p = .09). However, in the DN treatment, participants changed neighbors slightly more frequently than they changed colors (23.47% vs. 18.73%, Wilcox test, W = 159.5, p = .05). Conversely, people changed colors less frequently in the DN treatment compared to the SN treatment (18.73% vs. 35.47%, Wilcox test, W = 195.5, p = .0006). Overall, we found that the option to change neighbors crowded out the choice to change color in the DN treatment, while the inclination to “stay put” did not differ significantly between the two treatments.

Figure 2.

Players’ choices of actions across rounds in the DN treatment (a) and SN treatment (b). Bar heights represent average percentages over sessions. The option of changing neighbors seems to crowd out the adoption of changing color in the DN treatment, while the action of stay-put remains similar between the DN and the SN treatment.

Network topology in dynamic networks

If the dynamic adaptation of networks aids in solving the GCP, what types of networks would emerge towards the end of the game? To address this question, we examine the structural properties of networks as they evolve over time. Specifically, we focus on three well-established network attributes from the literature of network science.

The first attribute, closeness centrality, measures the average path distance between nodes in a network (Newman, 2010). As a normalized metric independent of network size, a higher value of this metric indicates a shorter path distance in the network. It is important to note that closeness centrality is a node-specific attribute. To report the path distance of a network, we average the closeness centrality over nodes.

The second attribute, clustering coefficient, measures the propensity of triadic closure—given a set of three nodes and two links, how likely we are to observe the presence of the third link (Wasserman and Faust, 1994). Notably, closeness centrality and clustering coefficients are the two metrics used by scholars to characterize the small-world networks (Watts and Strogatz, 1998), contrasting them with random networks and regular lattices, with the latter being our default network in the experiment.

Finally, to uncover the distribution of node degree and assess whether a small set of nodes are significantly more connected than the majority of others, we fit the distribution of node degree to a power-law function (Barabási and Albert, 1999). The fitted value of the distribution’s component would indicate whether the evolved network can be classified as a scale-free network—a type of network extensively discussed in the complex network literature over the past decades (Barabási, 2009).

Figure 3 presents the three network statistics across rounds. Firstly, the fitted parameter (α) against the power-law distribution indicates that the evolved networks differed from what one would typically observe for scale-free networks, which are typically characterized by 2 < α < 3. Secondly, we observed that closeness centrality increased while the clustering coefficient decreased as the networks evolved from the initial lattice setup. The trajectories of these two network statistics, closeness centrality and clustering coefficient, precisely mirrored those observed in the well-known small-world model, where scholars perturb the lattice network by probabilistically rewiring a random set of links in the network (Watts and Strogatz, 1998). Taken together, these findings suggest that the evolved networks resemble the small-world networks more closely than the scale-free networks. Specifically, the evolved networks are characterized by minimal inequality in node degree, short path distances, and high triadic clustering.

Figure 3.

Evolution of network attributes in the dynamic network (DN) treatment. The evolved networks resemble the small-world networks more closely than the scale-free networks.

Individuals’ choices of actions in dynamic networks

The efficacy of dynamic networks in solving the GCP can also be assessed by analyzing the actions taken by players in the game. We calculate the proportion of each action type chosen by a player over rounds before the game concludes (either due to the successful resolution of the game or reaching T_max = 15 rounds). We refer to the distribution of the three types of actions as a player’s action profile. Figure 4 illustrates the distribution of participants’ action profiles against the average score they achieved in the game. We observed that high-scoring players are predominantly found in areas characterized by a low frequency of changing neighbors, a high prevalence of “stay put,” and minimal instances of changing colors. Surprisingly, even though participants in the DN treatment had the option to alter network neighbors, we discovered that frequent turnovers of neighbors did not contribute to improving a player’s performance.

Figure 4.

The distribution of players’ action profiles against the average scores they received. High scores are concentrated in areas with minimal cases of changing color.

We additionally run a Tobit regression model to examine which types of action profiles enhance a player’s performance in the game. Since a player’s action profile would sum up to one, causing collinearity of the independent variables in the regression model, we run separate models, each considering only a pair of action types.

The interpretation of the regression results presented in Table 2 can be outlined as follows. In Model 1, it is observed that when a player increases the inclination to change color instead of staying put (treated as an omitted variable), while holding the intensity of changing neighbor constant, the effect of changing color on a player’s performance is negative (−22.45). Similarly, opting to change network neighbors instead of staying put, while maintaining the propensity to change color constant, results in inferior game performance, as indicated by the negative regression coefficient (−7.04). Taken together, these results underscore the significance of the “stay-put” action in the game.

Table 2.

Tobit regression examining the effect of action type on game performance.

Variables	Model 1	Model 2	Model 3
Intercept	95.59*** (1.00)	88.55*** (1.85)	73.14*** (2.00)
Chang Color	−22.45*** (2.57)	−15.41*** (3.16)
Change Network Neighbor	−7.04*** (2.35)		15.41*** (3.16)
Stay Put		7.04*** (2.35)	22.45*** (2.57)

-Standard errors are in parentheses.

***p < .001, **p < .01, *p < .05, ^†p < .1.

Similarly, in Model 2, it can be inferred that altering color instead of changing neighbors, or vice versa, does not enhance game performance, with the propensity to stay put held constant. This suggests a tradeoff between changing color and changing network neighbors for improving game performance. Finally, in Model 3, it is revealed that changing neighbors or staying put instead of changing color contributes to enhancing a player’s performance, implying the relatively lesser importance of changing color in achieving high scores in the game. In conclusion, we contend that a combination of changing neighbors and staying put forms the optimal action profile for achieving a high score in the game.

We have examined how players’ action profiles correlate with their game performance. However, are players genuinely motivated by game performance when selecting actions in each round? To gather more direct evidence, we investigate the information presented to players in the interface: (1) their current score, and (2) the number of neighbors they have. We conduct a multinomial regression model to assess how these two pieces of information influence a player’s choice of action. Since a player makes multiple decisions during the game, to address the issue of repeated measures when estimating the regression model, we employ a conventional econometric method to cluster the standard errors of the regression coefficients within each participant (Cameron et al., 2011). The results are presented in Table 3.

Table 3.

Multinomial regression on player’s choices of action in each round.

	Change neighbor (vs. change color)	Stay put (vs. Change color)
Variables
Intercept	−3.81^*** (0.54)	−4.78^*** (0.58)
Score	0.03^*** (0.002)	0.05^*** (0.005)
Connectivity	0.34^*** (0.08)	0.26^*** (0.08)

-Standard errors are in parentheses.

***p < .001, **p < .01, *p < .05, ^†p < .1.

The results indicate that players are more inclined to change neighbors rather than change colors as their score increases. Likewise, higher scores tend to encourage players to stay put rather than change colors. Network connectivity also plays a significant role: players with more neighbors are more likely to change neighbors or stay put instead of changing colors.

These findings align with the earlier observation that changing colors is more prevalent at the beginning of the game when players’ scores are relatively low (refer to Figure 2). In contrast, changing neighbors tends to enhance a player’s scores and becomes more popular in the later stages of the game. This is followed by the final stage, during which most players, except for those who have not yet solved the game, opt to stay put, awaiting others to make appropriate moves before the entire session successfully completes the game.

Determinants of individual’s choices of network neighbors

To comprehend how the dynamic updating of networks aids in solving the coloring problem, another crucial question arises: how do individuals select their network neighbors? Specifically, what criteria guide their decisions to delete or add neighbors?

In the experiment, whenever players intend to delete an existing or add a new neighbor, they have access to information about each player’s (1) connectivity, (2) score, and two additional items regarding their past performance: the percentage of times a player chose to (3) change color and (4) switch neighbors, respectively. Using this information, we conducted a logistic regression model to examine how these factors influence a participant’s decisions to abandon or add neighbors.

Table 4 illustrates that when deleting a neighbor, individuals are more inclined to remove those with a lower score and a higher frequency of changing color. Notably, a player’s network connectivity does not significantly affect the likelihood of being deleted. Conversely, when adding a new neighbor, players tend to select those with a higher score, lower connectivity, and less frequent changes in color, although the latter two factors are only marginally significant. Overall, these findings suggest that a player’s choice of neighbors is guided by considerations of the quality and stability of a player’s past decisions. Players appear to prefer neighbors who have consistently performed well and exhibited predictable behavior in the game. Such neighbors seemingly make it easier for the focal player to act accordingly.

Table 4.

Logistic regression on choices in neighbor deletion and addition.

Variables	Models
Variables	Deleting neighbor	Adding neighbor
Intercept	−0.20 (0.36)	−2.46^*** (0.37)
Connectivity	0.01 (0.05)	−0.08^† (0.05)
Score	−0.02^*** (0.002)	0.007^* (0.003)
History of changing color	0.91^*** (0.15)	−0.29^† (0.17)
History of changing neighbor	0.35 (0.25)	−0.43 (0.12)

-Standard errors are in parentheses.

***p < .001, **p < .01, *p < .05, ^†p < .1.

Discussion

In a network experiment involving human participants, we demonstrate that GCP can be solved more effectively and efficiently when players are able to update their network neighbors. Our study aligns with the recommendation put forth by Kearns and colleagues (2006) to explore GCP within a dynamic network framework. We observe that in dynamic networks, players tend to alternate between two actions: changing neighbors and remaining in place, although the latter action constitutes a larger proportion. Consequently, the initial network structure established in the experiment transitions from a lattice to a configuration resembling a small-world network, mirroring the trajectory outlined in the seminal model proposed by Watts and Strogatz (1998). Furthermore, our findings indicate a preference among participants for linking with actors who have demonstrated strong performance and consistency in the game. Collectively, these findings illustrate how the dynamic adaptation of network neighbors facilitates coordination of human actions in solving the GCP.

We contend that the success of the dynamic network game implemented in the experiment cannot solely be attributed to the dynamism of link rewiring; rather, partner selection plays a crucial role. Behavioral data reveals that participants tended to choose specific types of players as network neighbors, namely, those who have consistently performed relatively well in past plays. While the experiment provides complete information on existing and potential neighbors, the extent to which such partner choice information can be found in real-life applications remains an open question, expected to vary on a case-by-case basis. For instance, tracking the history of other users on modern social media platforms is arguably much easier than, say, for businessmen in the medieval period who relied on specific reputation systems to gather information on prospective transaction partners (Greif, 1989). Therefore, we do not aim to generalize our experimental findings to all cases, past and present, related to the coordination of heterogeneity in networks, as each case varies in terms of the accessibility of information when actors establish connections with new partners in social networks. Our aim here is to demonstrate that if such information is provided, adaptive networks driven by partner choice can effectively address the coordination problem characterized by GCP. We anticipate that the difficulty of coordination would increase when decision-makers have limited information about prospective partners.

Notably, although our experiment employs a dynamic network approach, we replicate several findings of Kearns et al. (2006) regarding the effects of static networks on GCP. Firstly, the observation that in our experiment the network transitions from a lattice to a small-world network as players progressively solve GCP aligns with Kearns et al.’s (2006) discovery that “cyclic networks with a few cords”—networks resembling small-world networks—outperform “cyclic networks”—lattices where each node has only two links. Secondly, we did not observe the evolution of networks in our experiment towards a state with high inequality in the distribution of node degree, echoing Kearns et al.’s (2006) finding that preferential attachment networks perform poorly in GCP. In essence, the networks that emerge in our experiment towards the conclusion of solving GCP resemble the static networks identified as relatively effective in GCP. Consequently, our study offers insight into the dynamics of network formation, shedding light on how successful networks identified in prior research come into existence.

However, it remains uncertain whether the networks observed in the experiment truly represent the optimal networks for solving GCP. It is noteworthy that the networks evolving in the experiment are formed through players’ actions of changing neighbors and changing colors, although the latter occurred relatively rarely during the experiment. Consequently, it is unclear whether networks that evolve in a setting where players have the choice of changing neighbors or changing colors are equally effective for solving GCP as those that only allow players to change colors. For future research, comprehensive simulations via agent-based models (Bankes, 2002) can be conducted to assess whether the optimal networks for GCP derived from the simulation are compatible across settings where we manipulate the activity levels of different game actions of interest.

Agent-based models can also be utilized to explore action profiles different from those observed in the experiment. Of particular interest is whether alternative action strategies exist that could further enhance performance in GCP. Equally intriguing is considering the heterogeneity of players’ actions in dynamic GCP. Extending along this line is particularly valuable in cases where a wide variety of behaviors in social coordination are observed. For instance, differences in the level of risk aversion may lead some individuals to prefer the status quo over novelty. Actors with such differences in their inclination toward exploration versus exploitation (Lazer and Friedman, 2007), when placed at various positions in the network, are anticipated to significantly influence coordination outcomes (Gaisbauer et al., 2022). Future research could continue to investigate how heterogeneity in individual traits influences coordination in the task of GCP.

As artificial intelligence (AI) increasingly influences humans’ daily lives, it becomes essential to consider how humans coordinate with AI across various tasks, including those characterized by GCP, as studied here. One central question revolves around how algorithm-driven AI can assist humans in solving GCP (Shirado and Christakis, 2017). While algorithms developed by computer scientists may perform well independently, failure to account for human factors such as cognitive biases and affective states can lead to suboptimal outcomes when coupling AI with humans in teamwork (Carroll et al., 2019). Gathering data on human behavior, as exemplified by previous research and demonstrated in our experiment, could offer guidance in designing computer algorithms for productive collaboration with humans.

Supplemental Material

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

Supplemental Material for Adaptive networks driven by partner choice can facilitate coordination among humans in the graph coloring game: Evidence from a network experiment by Yen-Sheng Chiang, Heng-Chin Cho and Chia-Jung Chang in Collective Intelligence.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Science and Technology Council; 110-2410-H-001 -061 -MY3.

ORCID iD

Yen-Sheng Chiang

Supplemental Material

Supplemental material for this article is available online.

Notes

References

Bankes

(2002) Agent-based modeling: a revolution? Proceedings of the National Academy of Sciences 99: 7199–7200.

Barabási

(2009) Scale-free networks: a decade and beyond. Science 325(5939): 412–413.

Barabási

Albert

(1999) Emergence of scaling in random networks. Science 286(5439): 509–512.

Barnier

Brisset

(2004) Graph coloring for air traffic flow management. Annals of Operations Research 130: 163–178.

Bicchieri

(2005) The Grammar of Society: The Nature and Dynamics of Social Norms. Cambridge, UK: Cambridge University Press.

Bravo

Squazzoni

Boero

(2012) Trust and partner selection in social networks: an experimentally grounded model. Social Networks 34(4): 481–492.

Cameron

Gelbach

Miller

(2011) Robust inference with multiway clustering. Journal of Business & Economic Statistics 29(2): 238–249.

Carroll

Shah

, et al. (2019) On the utility of learning about humans for human-ai coordination. Advances in Neural Information Processing Systems 32: 12.

Centola

Macy

(2007) Complex contagions and the weakness of long ties. American Journal of Sociology 113(3): 702–734.

10.

Centola

Becker

Brackbill

, et al. (2018) Experimental evidence for tipping points in social convention. Science 360(6393): 1116–1119.

11.

Chen

Schonger

Wickens

(2016) oTree—an open-source platform for laboratory, online, and field experiments. Journal of Behavioral and Experimental Finance 9: 88–97.

12.

Chiang

(2010) Self-interested partner selection can lead to the emergence of fairness. Evolution and Human Behavior 31(4): 265–270.

13.

Chwe

MSY

(1999) Structure and strategy in collective action. American Journal of Sociology 105(1): 128–156.

14.

Corten

Buskens

(2010) Co-evolution of conventions and networks: an experimental study. Social Networks 32(1): 4–15.

15.

Efferson

Vogt

Fehr

(2020) The promise and the peril of using social influence to reverse harmful traditions. Nature Human Behaviour 4(1): 55–68.

16.

Enemark

McCubbins

Paturi

, et al. (2011) Does more connectivity help groups to solve social problems. In: Proceedings of the 12th ACM conference on electronic commerce, San Jose, California, USA, 5-9 June 2011, 21–26.

17.

Enemark

McCubbins

Weller

(2014) Knowledge and networks: an experimental test of how network knowledge affects coordination. Social Networks 36: 122–133.

18.

Erikson

Shirado

(2021) Networks, property, and the division of labor. American Sociological Review 86(4): 759–786.

19.

Fulker

Forber

Smead

, et al. (2021) Spite is contagious in dynamic networks. Nature Communications 12(1): 260.

20.

Gaisbauer

Strandburg-Peshkin

Giese

(2022) Local majority-with-inertia rule can explain global consensus dynamics in a network coordination game. Social Networks 70: 218–227.

21.

Garey

Johnson

(1979) Computers and Intractability. A Guide to the Theory of NP-Completeness. New York, NY: W.F Freeman and Company.

22.

Greif

(1989) Reputation and coalitions in medieval trade: evidence on the Maghribi traders. The Journal of Economic History 49(4): 857–882.

23.

Hafner-Burton

Kahler

Montgomery

(2009) Network analysis for international relations. International Organization 63(3): 559–592.

24.

Jackson

Watts

(2002) On the formation of interaction networks in social coordination games. Games and Economic Behavior 41(2): 265–291.

25.

Janssen

Krizanc

Narayanan

, et al. (2000) Distributed online frequency assignment in cellular networks. Journal of Algorithms 36(2): 119–151.

26.

Jensen

Toft

(2011) Graph Coloring Problems. Hoboken, NJ: John Wiley & Sons.

27.

Judd

Kearns

Vorobeychik

(2010) Behavioral dynamics and influence in networked coloring and consensus. Proceedings of the National Academy of Sciences 107(34): 14978–14982.

28.

Jusup

Holme

Kanazawa

, et al. (2022) Social physics. Physics Reports 948: 1–148.

29.

Kearns

Suri

Montfort

(2006) An experimental study of the coloring problem on human subject networks. Science 313: 824–827.

30.

Kearns

Judd

Tan

, et al. (2009) Behavioral experiments on biased voting in networks. Proceedings of the National Academy of Sciences 106(5): 1347–1352.

31.

Kubale

Jackowski

(1985) A generalized implicit enumeration algorithm for graph coloring. Communications of the ACM 28(4): 412–418.

32.

Lazer

Friedman

(2007) The network structure of exploration and exploitation. Administrative Science Quarterly 52(4): 667–694.

33.

Lewis

RMR

(2021) Guide to Graph Colouring: Algorithms and Applications. Berlin, Germany: Springer Nature.

34.

Mackie

(1996) Ending footbinding and infibulation: a convention account. American Sociological Review 61: 999–1017.

35.

Malaguti

Toth

(2010) A survey on vertex coloring problems. International Transactions in Operational Research 17(1): 1–34.

36.

Maroulis

Diermeier

Nisar

(2020) Discovery, dissemination, and information diversity in networked groups. Social Networks 61: 67–77.

37.

McCubbins

Paturi

Weller

(2009) Connected coordination: network structure and group coordination. American Politics Research 37(5): 899–920.

38.

Mostafaie

Modarres Khiyabani

Navimipour

(2020) A systematic study on meta-heuristic approaches for solving the graph coloring problem. Computers & Operations Research 120: 104850.

39.

Newman

(2010) Networks: An Introduction. Oxford, UK: Oxford University Press.

40.

Perc

Szolnoki

(2010) Coevolutionary games—a mini review. Biosystems 99(2): 109–125.

41.

Rand

Arbesman

Christakis

(2011) Dynamic social networks promote cooperation in experiments with humans. Proceedings of the National Academy of Sciences 108(48): 19193–19198.

42.

Schelling

(2006) Micromotives and Macrobehavior. New York, New York: WW Norton & Company.

43.

Schuetz

Brubaker

Zhu

, et al. (2022) Graph coloring with physics-inspired graph neural networks. Physical Review Research 4(4): 043131.

44.

Shirado

Christakis

(2017) Locally noisy autonomous agents improve global human coordination in network experiments. Nature 545: 370–374.

45.

Shore

Bernstein

Lazer

(2015) Facts and figuring: an experimental investigation of network structure and performance in information and solution spaces. Organization Science 26(5): 1432–1446.

46.

Skyrms

(2004) The Stag Hunt and the Evolution of Social Structure. Cambridge, UK: Cambridge University Press.

47.

Stewart

Mosleh

Diakonova

, et al. (2019) Information gerrymandering and undemocratic decisions. Nature 573(7772): 117–121.

48.

Wasserman

Faust

(1994) Social Network Analysis. Cambridge, UK: Cambridge University Press.

49.

Watts

Strogatz

(1998) Collective dynamics of ‘small-world’ networks. Nature 393: 440–442.

50.

Young

(2011) The dynamics of social innovation. Proceedings of the National Academy of Sciences 108: 21285–21291.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.41 MB