Coordination and equilibrium selection in games: the role of local effects
Pure coordination gameIn 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:$$begin{gathered} begin{array}{*{20}c} {} & {quad ; {text{A}}} &; {text{B}} \ end{array}hfill \ begin{array}{*{20}c} {text{A}} \ {text{B}} \ end{array} left( {begin{array}{*{20}c} 1 & 0 \ 0 & 1 \ end{array} } right) hfill \ end{gathered}$$
(2)
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.Figure 1Time evolution of the coordination rate (alpha) (in MC steps) in individual realisations for different values of the degree k in a random regular network of (N=1000) nodes, using (a) the replicator dynamics, (b) the best response, and (c) the unconditional imitation update rule.Full size imageFigure 2Coordination rate (alpha) and interface density (rho) vs degree k of a random regular network for (N=1000) using (a) the replicator dynamics, (b) the best response, and (c) the unconditional imitation update rule. Each green circle represents one of 500 realisations for each value of the degree k and the average value is plotted with a solid line, separately for (alpha >0.5) and (alpha le 0.5). Results are compared to the ER random network ((alpha _{ER})) with the same average degree.Full size imageFirst, 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 networks76,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 graphs78. 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 networks40.Figure 3Examples of frozen configuration reached under the UI update rule for small values of the average degree k in random regular networks (top row) and Erdős–Rényi networks (bottom row) with 150 nodes. Red colour indicates a player choosing the strategy A, blue colour the strategy B. Note the topological differences between random regular and ER networks when they are sparse. For (k=1) a random regular graph consists of pairs of connected nodes, while an ER network has some slightly larger components and many loose nodes. For (k=2) a random regular graph is a chain (sometimes 2–4 separate chains), while an ER network has one large component and many disconnected nodes. For (k=3) and (k=4) a random regular graph is always composed of one component, while an ER network has still a few disconnected nodes.Full size imageSince 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 length23 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 (kP) (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:$$begin{gathered} begin{array}{*{20}c} {} & {qquad {text{A}}} & {quad quad {text{B}}} \ end{array} ;; hfill \ begin{array}{*{20}c} {text{A}} \ {text{B}} \ end{array} left( {begin{array}{*{20}c} 1 & {frac{{S – P}}{{R – P}}} \ {frac{{T – P}}{{R – P}}} & 0 \ end{array} } right) hfill \ end{gathered}$$
(3)
which, after substituting (S’=frac{S-P}{R-P}) and (T’=frac{T-P}{R-P}), is equivalent to the matrix: $$begin{gathered} begin{array}{*{20}c} {} &quad ;;{text{A}} &; {text{B}} \ end{array} ;quad quad quad quad quad quad begin{array}{*{20}c} {} & quad; {text{A}} & ;{text{B}} \ end{array} hfill \ begin{array}{*{20}c} {text{A}} \ {text{B}} \ end{array} left( {begin{array}{*{20}c} 1 & {S^{prime}} \ {T^{prime}} & 0 \ end{array} } right)xrightarrow[{{text{apostrophes}}}]{{{text{skipping}}}}begin{array}{*{20}c} {text{A}} \ {text{B}} \ end{array} left( {begin{array}{*{20}c} 1 & S \ T & 0 \ end{array} } right) hfill \ end{gathered}$$
(4)
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 dilemma14,46 (for (T >1) and (S More
