Coordination and equilibrium selection in games: the role of local effects

Pure coordination game

In this section we study the Pure Coordination Game (PCG) (also known as doorway game, or driving game) in which (R=1), (S=0), (T=0), and (P=1), resulting in a symmetric payoff matrix with respect to the two strategies:

There are two equivalent equilibria for both players coordinating at the strategy A or B (a third Nash equilibrium exists for players using a mix strategy of 50% A and 50% B). As the absolute values of the payoff matrix are irrelevant and the dynamics is defined by ratios between payoffs from different strategies, the payoff matrix (2) represents all games for which the relation (R=P>S=T) is fulfilled.

In the PCG the dilemma of choosing between safety and benefit does not exist, because there is no distinction between risk-dominant and payoff-dominant equilibrium. Both strategies yield equal payoffs when players coordinate on them and both have the same punishment (no payoff) when players fail to coordinate. Therefore, the PCG is the simplest framework to test when coordination is possible and which factors influence it and how. It is in every player’s interest to use the same strategy as others. Two strategies, however, are present in the system at the beginning of the simulation in equal amounts. From the symmetry of the game we can expect no difference in frequency of each strategy being played, when averaged over many realisations. Still, the problem of when the system reaches full coordination in one of the strategies is not trivial. We address this question here.

First, we look at single trajectories as presented in Fig. 1. Some of them quickly reach (alpha =0) or 1, or stop in a frozen state without obtaining global coordination. Other trajectories take much longer and extend beyond the time scale showed in the figure. What we can already tell is that the process of reaching coordination is slower in the replicator dynamics where it usually takes more time than in the best response and unconditional imitation to reach a frozen configuration. For all update rules the qualitative effect of the connectivity is similar—for bigger degree it is more likely to obtain full coordination and it happens faster. For the UI, however, larger values of degree than for the RD and BR are required to observe coordination. For example, in the case of (k=10) or 20 the system stops in a frozen disorder when using UI, while for the RD and BR it quickly reaches a coordinated state of (alpha =0) or 1.

To confirm the conclusions from observation of trajectories, we present the average outcome of the system’s evolution in the Fig. 2. The first thing to notice is that all plots are symmetrical with respect to the horizontal line of (alpha = 0.5). It indicates that the strategies are indeed equivalent as expected. In all cases there is a minimal connectivity required to obtain global coordination. For the RD and BR update rules this minimum value is (k=4), although in the case of BR the system fails to coordinate for small odd values of k due to regular character of the graph. This oscillating behaviour does not exist in Erdős–Rényi random networks. When nodes choose their strategies following the UI rule much larger values of k are required to obtain full coordination. Single realisations can result in (alpha = 0), or 1 already for (k=15). However, even for (k=60) there is still a possibility of reaching a frozen uncoordinated configuration.

The important conclusion is that there is no coordination without a sufficient level of connectivity. In order to confirm that this is not a mere artefact of the random regular graphs we compare our results with those obtained for Erdős–Rényi (ER) random networks^76,77 (black dashed line in Fig. 2). The level of coordination starts to increase earlier for the three update rules, but the general trend is the same. The only qualitative difference can be found in the BR. The oscillating level of coordination disappears and it doesn’t matter if the degree is odd or even. This shows that different behaviour for odd values of k is due to topological traps in random regular graphs⁷⁸. Our results for the UI update rule are also consistent with previous work reporting coordination for a complete graph but failure of global coordination in sparse networks⁴⁰.

Since agents using the RD and BR update rule do not achieve coordination for small values of degree, one might suspect that the network is just not sufficiently connected for these values of the degree, i.e. there are separate components. This is only partially true. In Fig. 3, we can see the structures generated by random regular graph and by ER random graph algorithms. Indeed, for (k=1) and 2 the topology is trivial and a large (infinite for (k=1)) average path length²³ can be the underlying feature stopping the system to reach coordination. For (k=3), however, the network is well connected with one giant component and the system still does not reach the global coordination when using RD or BR. For the UI update rule coordination arrives even for larger values of k. Looking at the strategies used by players in Fig. 3 we can see how frozen configuration without coordination can be achieved. There are various types of topological traps where nodes with different strategies are connected, but none of them is willing to change the strategy in the given update rule.

We next consider the question of how the two strategies are distributed in the situations in which full coordination is not reached. Looking at the trajectories in Fig. 1 we can see that there are only few successful strategy updates in such scenario and the value of (alpha) remains close to 0.5 until arriving at a frozen state for (k=2) (also (k=7) for UI). This suggests that there is not enough time, in the sense of the number of updates, to cluster the different strategies in the network. Therefore, one might expect that they are well mixed as at the end of each simulation. However, an analysis of the density of active links in the final state of the dynamics, presented in Fig. 2, shows a slightly more complex behaviour. When the two strategies are randomly distributed (i.e. well mixed) in a network, the interface density takes the value (rho =0.5). When the two strategies are spatially clustered in the network there are only few links connecting them and therefore the interface density takes small values. Looking at the dependence of (rho) on k, we find that for the replicator dynamics the active link density starts at 0.5 for (k=1), then drops below 0.2 for (k=2) and 3 indicating good clustering between strategies, to fall to zero for (k=4) where full coordination is already obtained. When using the best response update rule the situation is quite different. For (k=1) there are no active links, (rho =0), and hardly any for (k=2). There is a slight increase of the active link density for (k=3), to drop to zero again for (k=4) due to full coordination. Because of the oscillatory level of coordination there are still active links for odd values of (k<10), but (rho) is always smaller than 0.2. In the case of the unconditional imitation we again start at (rho =0.5) for (k=1), before it drops below 0.2 for (k=2). Subsequently, the active link density grows to obtain its maximum value for (k=7) and starts decreasing towards zero. These differences in behaviour can be better understood when studying the actual topology of regular graphs for small values of the degree. In Fig. 3 we present frozen configurations for the UI update rule in networks with (k=1,2,3), and 4. For the smallest degree, (k=1), the network consists of connected pairs of nodes. Whatever strategies are initially assigned to those pairs they will not change when using RD or UI. In both cases—two nodes using the same strategy and two nodes using different strategies—both nodes in a pair receive the same payoff, therefore no imitation can happen. Hence, the active link density is (rho =0.5) for RD and UI. On the other hand, the BR update rule will cause every pair to coordinate, as this is the best possibility for any node, and therefore (rho =0). The case of (k=2) still results in a quite particular structure—it is a chain of nodes (or a 1D lattice). For every update rule the shortest possible cluster of one strategy must contain at least two nodes. The RD and UI separate different strategies relatively well obtaining (rho <0.2), however still worse than the BR. For the latter there are almost no active links, i.e. two strategies are perfectly clustered in two (or only few) clusters. From (k=3) onwards random regular graphs form well connected networks with one giant component and small average path length. This is the largest value of k for which the RD and BR update rules do not lead to full coordination. Given the value of the active link density (rho <0.2) we can say they both cluster strategies relatively well. For the UI update rule coordination still does not exist for (k=3), and the number of active links increases with growing degree. This is to be expected—the more links in the network the more connections between nodes playing different strategies. The level of (rho) starts to drop only when the coordination begins to settle and we observe that the strategies are well mixed in the network before this point.

Coordination transition

One way of investigating the transition between frozen disorder and global coordination is to look at the probability distribution of the coordination rate (alpha). If the distribution is unimodal and centred in the middle at the value of (alpha =0.5), we have a disordered state with roughly equal numbers of players using the strategy A and the strategy B. If the distribution is bimodal with two peaks at the boundary values of (alpha =0) or 1, all players use the same strategy A or B and coordination was reached. We can see a transition from the first scenario into the second one for all update rules in Fig. 4. The transition point can be identified by the lowest degree for which the distribution is not unimodal (and centred in the middle). The specifics of these transitions, however, differ from one rule to another. For the RD the distribution is unimodal for (k=1,2,3), becomes trimodal for (k = 4) (in ER random networks for (k = 3)), and later bimodal for (k ge 5). Therefore, the transition point can be defined as the threshold value of the degree (k_c^{RD}=4). When players use the BR update rule, the distribution becomes bimodal at (k=4), but is trimodal for (k=5,7,9,11), i.e. small odd degree values. No such effect of odd degree exists if the network is an ER random network, but also here a trimodal distribution is obtained up to (k=9). The transition point for the BR is the same as in the RD, (k_c^{BR}=4), but in the RD beyond this point coordination is always reached, while for the BR there is still a possibility of stopping at a frozen discorded configuration up to (k=11). While the behavior of the probability distribution of (alpha) for the RD and BR update rules is a signature of a first order transition, the transition is less abrupt for the UI update rule. Here the distribution of the coordination rate (alpha) is unimodal up to (k=8), although its variance increases with growing degree of the network. At (k_c^{UI}=9) the distribution becomes trimodal ((k=6) for ER random networks), but the side maxima are placed far from the coordinated state—rougly at (alpha = 0.2) and 0.8. The trimodal distribution is present up to (k=15) and the side peaks keep shifting towards boundary values. For (k>15) the distribution is bimodal, but the peaks are much wider than in other update rules. Additionally, the distribution is not zero between them. This means that the simulation sometimes freezes at a disordered configuration or close to the global coordination, but with a group of agents playing the opposite strategy.

An important question is what role do the finite size effects play in our results. A larger population could need higher or lower connectivity to obtain the same level of coordination. The answer is given in Fig. 5. From panels (a) and (b) we observe that when players use the RD or BR update rule the resulting level of coordination for a given value of degree is the same for any system size. In other words, even for very large populations we obtain full coordination already for (k=4). Interestingly, the drop in the coordination rate (alpha) for odd values of k visible in the BR is also the same for different system sizes. This again suggests that it is an effect of topological traps in regular graphs and not of finite size.

Finite size effects turn out to be quite different when players update their strategies according to the UI update rule. From Fig. 5 we observe that the level of coordination decreases when the population grows at a given fixed connectivity. Or equivalently, the transition from frozen disorder into full coordination is shifted towards higher values of the degree k. A proper way of identifying the transition point is by looking at the maximum of the convergence time. In the inset plots of Fig. 5 we see that, when increasing system size, the value of the degree for which the convergence time becomes maximum shift to larger values for the UI update rule, whereas it stays at the same value of k for the RD and BR update rules. Additionally, the maximum number of the Monte Carlo time steps necessary to reach a frozen configuration grows with the system size in the case of UI, but stays the same for other update rules. The transition point (k_c) defined by the maximum convergence time (tau _{max}) is equal (k_c^{RD}=4) for the replicator dynamics, (k_c^{BR}=4) for the best response, and (k_c^{UI}=9) for the unconditional imitation for (N=1000) nodes. Note, that for the BR the convergence time is higher for (k=2), but we do not take it into account due to the trivial topology. Those threshold values of k coincide with the ones discussed above in terms of the changes in the (alpha) probability distribution.

The scaling behaviour under the UI update rule raises a question about the minimal connectivity necessary to observe coordination in the thermodynamic limit . In Fig. 5c in the bottom inset plot we present the dependence of the transition point (k_c^{UI}) on the system size N. Two functions can be fitted to these data points—logarithmic function ((R^2=0.997)) and power law ((R^2=0.973)). In the latter case the transition depends on the number of nodes as (k_c^{UI} sim N^{0.1}). For both functions the minimum degree required to obtain coordination goes to infinity in the thermodynamic limit. However, (k_c^{UI}/N rightarrow 0) when (N rightarrow infty) so that full coordination is achieved in the thermodynamic limit for connectivity much lower than in a complete graph.

Our analysis of the simple PCG already uncovers significant differences among the update rules, including different finite size effects. To achieve global coordination in the population the network must have a minimal connectivity. In random regular graphs this minimum is higher than in ER random networks. Looking at the update rules, players using the RD achieve coordination for the lowest connectivity, or in other words the drive towards global coordination is the strongest in this update rule. When using the BR a slightly higher values of the degree are required for the same level of coordination to appear. Moreover, in random regular graphs the minimal connectivity for the BR update rule is different for odd and even values of the degree. For the UI update rule coordination requires much higher values of the degree k and often freezes just before obtaining full coordination (at (alpha) close but not equal 0 or 1). System size scaling indicates that even higher connectivity is required for coordination to happen in larger networks, while the transition to coordination for the RD and the BR update rules is size-independent. Interpreting the results one also has to bear in mind that cases of (k=1,2) produce very particular topologies with large average path lengths, which hinder the coordination. However, for (k ge 3) the network is well connected and in principle there is no structural reason why coordination should not emerge. Nevertheless, in many cases it doesn’t.

General coordination game

After considering the role of local and finite size effects in the simplest case of two equivalent equilibria for coordination, we address in this section the question of equilibrium selection for nonequivalent states of global coordination. We therefore consider the payoff matrix (1) where (R ne P). Without loss of generality we can assume that (R>P) (otherwise we can rename the strategies and shuffle the columns and rows). What defines the outcome of a game are the greater than and smaller than relations among the payoffs. Therefore we can add/subtract any value from all payoffs, or multiply them by a factor grater than zero, without changing the game. Thus, the payoff matrix (1) can be rewritten as:

which, after substituting (S’=frac{S-P}{R-P}) and (T’=frac{T-P}{R-P}), is equivalent to the matrix:

From now on we omit the apostrophes and simply refer to parameters S and T. This payoff matrix can represent many games, including e.g. the prisoner’s dilemma^14,46 (for (T>1) and (S<0)). We restrict our analysis to coordination games which correspond to (S<0) and (T<1)^67,79. In these games there are pure Nash equilibria at coordinated states, i.e. for both players using the same strategy. We call games that fit in this range of parameters by one name—the General Coordination Game (GCG). In fact, it covers any two-player symmetrical coordination game with different payoffs at coordinated states. For example, the popular game of stag hunt^26,80 is a special case of the GCG for (0<T<1) and (-1<S<0) (the condition (S>-1) is not always imposed, however conventionally the stag hunt is investigated only in the indicated square area). For (T=-1) we obtain a game which in a different parametrisation is often studied in literature^42,81. We shall discuss it in more detail further in the text. Figure 6 illustrates the plane of parameters of the GCG.

An important feature of the GCG is that is possesses a payoff-dominant (aka Pareto-optimal) equilibrium and a risk-dominant equilibrium. The strategy A is Pareto-optimal—it provides the largest possible payoff for both players if they coordinate on it. To establish which strategy is risk-dominant we need to compute the average payoffs of strategies A and B, (Pi _{mathrm {A}}) and (Pi _{mathrm {B}}), assuming random and uniform strategy choice in the population. For both strategies having probability 1/2 of being played, from the payoff matrix (4) we obtain (Pi _{mathrm {A}} = frac{S+1}{2}) and (Pi _{mathrm {B}} = frac{T}{2}). Therefore, the strategy A will be risk dominant for (T<S+1) and the strategy B will be risk dominant for (T>S+1). This calculation provides a theoretical transition line (T=S+1) between two phases, depending which of the strategies A or B is the risk-dominant strategy (see Fig. 6).

Whether the risk dominance is a sufficient condition for a strategy to prevail in an evolutionary setup is to be examined. It is intuitively clear that when one strategy is both risk-dominant and payoff-dominant at the same time it should be evolutionary favoured. Therefore, we expect to see coordination on the strategy A for (T<S+1). The question is what happens when there is a choice between a risk-dominant strategy and a payoff-dominant one. We explore in the following paragraphs the effect of update rule, local effects and finite size in equilibrium selection.

We present phase diagrams obtained from our numerical simulations for the three update rules in Fig. 7. For the replicator dynamics and the best response update rules there is a transition in the equilibrium selection at the line (T=S+1). For (T<S+1) the strategy A, which is there both payoff-dominant and risk-dominant, is selected, but for (T>S+1) the risk-dominant strategy B is selected. Importantly, the transition line from A to B selection is independent of the degree or size of the network. These findings are also consistent with analytical calculations based on the replicator equation for the RD and mean field approach for the BR (see “Methods” for details). Interestingly, when players use the unconditional imitation the transition is shifted towards larger values of T (and smaller S) for sparser networks. The transition line moves to (T=S+1) with growing degree of the network and finally reaches this line for a complete graph. Note, that for the stag hunt area and small values of k our results are consistent with Roca et al.⁴⁶.

The important consequence of local effects is that players can still coordinate on the Pareto-optimal strategy A even when this strategy is far from being risk-dominant. However, this only happens for the UI update rule and small enough connectivity in the population. This is in a sense opposite to the results in the PCG. There, the optimal outcome, i.e. any coordination, could be achieved only above a threshold value of the degree. Here, for a given range of the parameters S and T the optimal outcome, i.e. coordination on the Pareto-optimal strategy, can be achieved only for networks with small enough connectivity. It is important to note that a previous most explicit result on the importance of local effects was given for rings (circular city)⁵⁶. The behaviour there was different—for sparse networks a larger connectivity was required to coordinate on the Pareto-optimal strategy (for densely connected networks the risk-dominant equilibrium was indirectly suggested). Including more complex structure without noise in strategy imitation, as we show, changes this relation. One might imagine that our results could change when analysing networks with the degree smaller than 8. In such sparse networks we observe coordination on the Pareto-optimal strategy or no coordination. However, the risk-dominant equilibrium is the only possibility for very small values of the parameter S (see Fig. 10, Supplementary Figures S2, S3 for results on very sparse networks).

We next consider the average convergence time (tau) to the selected equilibrium. Results for two different values of T are shown in Fig. 8. As previously, RD is the update rule least affected by local effects (changes in the value of the degree). A maximum convergence time is always found at the transition point of equilibrium selection. Additionally, the time to reach a frozen configuration is similar for all values of k, except sparse networks ((k=8)) where it becomes bigger. When using the BR update rule converge times are in general slightly shorter. For smaller degree ((k=8)) the transition point of equilibrium selection is firmly marked by a narrowly peaked maximum value of (tau). For (k=32) there is very small increase in the convergence time and for larger values of degree the transition is not identified at all. In the case of the UI update rule the transition in equilibrium selection does not coincide with the change of risk-dominant strategy and the equilibrium selection transition only manifests itself as a maximum in the convergence time for (T>0). In the panel (c) of Fig. 8 the maximum of (tau) is obtained at a different point for each value of k, because the equilibrium selection transition moves with changing degree. Every peak corresponds to the transition for the given k. For (T le 0), however, the maximum convergence time is not associated with the transition. Note, that comparing this behaviour with our results for the PCG, one must remember that in the PCG the maximum of the convergence time was associated with a transition from a frozen disorder to coordination, while in the GCG the transition is only a change of the selected equilibrium of full coordination.

Local effects and size effects in GCG

A particular coordination game often studied in the literature is the one described by the following payoff matrix^42,43,56,81:

where usually a restriction (b>0) is imposed, although it is still a coordination game up to (b>-1). Note, that the strategy symbols changed their positions. In a typical notation the upper left strategy is Pareto-optimal, i.e. it is the strategy that gives the largest payoff. We denoted it before as the strategy A. Therefore, to stay consistent we change the denotation to maintain (A, A) the Pareto-optimal configuration.

The game described by the payoff matrix (5) is fully equivalent to the GCG with (T=-1). To see this, it is enough to interchange the positions of strategies A and B and subtract 1 from every entry to obtain:

In this notation it is clear that the game described in the literature by the payoff matrix (5) is equivalent to the GCG described by the payoff matrix (4) for (T=-1) and (S=-b-1). In this parametrisation the change of risk-dominant strategy from A to B lays at (S=-2) ((b=1)). For (S>-2) ((b<1)) the strategy A is risk-dominant and for (S<-2) ((b>1)) the strategy B is risk-dominant. For the RD or BR update rules the transition in equilibrium selection obtained in numerical simulations presented in Fig. 7 occurs at this same point (S_c=-2) ((b_c=1)) (also in ER random networks, not presented due to identical character). For this reason, here we focus on transition for the unconditional imitation update rule. In order to study how does equilibrium selection depend on the degree k, we have to fix the payoff matrix. We consider the case with (T=-1) that was already studied in the literature (under parametrisation with b). Then, we analyse local effects and size effects in coordination and equilibrium selection for different values of the parameter S.

In Fig. 9a we present the dependence of coordination rate (alpha) on the parameter S (and b). We can see that the transition in equilibrium selection from (alpha =0) to (alpha =1) is shifted towards lower values of S (or larger values of b) in comparison to the values at which risk-dominant strategy changes. Interestingly, all realisations lay very close to the average value of (alpha). Therefore, the coordination is well predefined by the parameter S (with other parameters fixed). We can see that in ER random graphs the transition in equilibrium selection is slightly closer to the (S=-2) ((b=1)) point and also the increase of coordination rate is smoother. The inset of panel (a) shows representative trajectories, which quickly converge into a frozen configuration for different parameter values. In Fig. 9b we show the average coordination rate (alpha) for different degrees of the network. The transition point (S_c) of equilibrium selection from B-coordination to A-coordination shifts towards the value (S=-2) with growing connectivity to finally coincide with this point of change in the risk-dominant strategy for a complete graph. Additionally, the coordination rate changes directly from (alpha =0) to (alpha =1) for higher degree values, without the intermediate plateau visible for (k=8) (see Supplementary Figures S2, S3 for results on very sparse networks). These results are robust regardless of the network size, as the standard deviation (alpha _{std}) decreases with growing N (see the inset plot of Fig. 9b). In order to investigate further the dependence of the transition point (S_c) (and (b_c)) on the network’s degree we plot it for different network sizes in Fig. 9c. Up to (k approx 250) the transition point follows a power law (S_c(k) sim k^{-0.17}) ((R^2>0.99)) for every size of the network. Then, the lines separate as each of them has the upper limit of (S_c=-2) which is obtained for a complete graph, i.e. for (k=N-1) which depends on the number of nodes. Note, that the found dependence (S_c(k)) can be reversed to obtain the critical value of the connectivity (k_c(S) sim S^{5.88}) above which the system coordinates at the risk-dominant equilibrium and below at the payoff-dominant one.

Finally, to study the degree dependence for particular values of the payoff matrix we set both parameters T and S to specific values and run simulation for various connectivities, as presented in Fig. 10. In the panel (a) for (T=-1) and (S=-3) we can see that for very sparse networks ((k=2) and 3) coordination can not be obtained and the system freezes in a disordered configuration (see Supplementary Figure S3 for a close-up on very sparse networks). Then, for a range of degrees from 4 to approximately 20 the system fully coordinates exclusively on the strategy A, i.e. in the Pareto-optimal equilibrium. Increasing k further a discontinuous transition with hysteresis follows. Up to approximately (k=55) the players can either fully coordinate in the payoff-dominant equilibrium or end up in a frozen configuration with (alpha in [0, 0.5])—a disordered state or a risk-dominant equilibrium. For even bigger connectivity only the frozen disorder or risk-dominant equilibrium are possible, to finally around (k=100) coordinate at the risk-dominant equilibrium in every realisation.

In Fig. 10b, we present the average coordination rate for a larger range of connectivity and several values of the parameter S. We only show results for (S<-2), since for (S>-2) the same strategy A is both payoff- and risk-dominant. Therefore, the game lacks the competition between those two factors and the strategy A is always chosen in the full coordination state. As visible in the figure, the phase of Pareto-optimal equilibrium is present only for larger values of the parameter S. For (S=-4) and smaller the system never coordinates on the payoff-dominant strategy. Instead we observe a transition from no coordination directly into the risk-dominant equilibrium. This is consistent with the results from Fig. 9b where we could see that the Pareto-optimal coordination could be obtained only for a small range of S below (-2) for every value of the degree. One can say that the Pareto-optimal equilibrium is fragile, it requires fine tuning of the parameters. For (T=-1) the parameter S must be bigger than (-4) and the network can not be very sparse nor too densely connected.

Source: Ecology - nature.com