Endogenous networks and international cooperation

Nash Equilibria and networks

We can conceive of network formation as an n-player game, where each of n players decides whether or not to propose a link with the other (n − 1) players. Each player has a utility function that can be based on their endowments, the endowments of their partners, those of their partners’ partners, and so on. If the desire to form a link is mutual – if player i wants to form a link with player j and player j wants to form a link with player i – then link ij is formed; if either player objects, the link is not formed. Each player’s actions will consist of providing a list of players that they wish to link with, and the final outcome will be a network with all mutual links.

For a network to be a Nash Equilibrium of a network formation game, no player can unilaterally do better by adding or deleting any number of players from the aforementioned list. If, holding the rest of the network constant, a player i would prefer not to form a link with player j, yet they are linked in the network, it is not an equilibrium because the player would strictly prefer an identical list of partners, but with player j removed. If player i and player j were not linked in a network, and player j included player i on her list, then if player i preferred to be linked to player j, this network would not be an equilibrium of the network formation game.

The need for links to be mutual hamstrings the usefulness of Nash Equilibria as a solution concept in network formation games. Consider the following extremely simple game: each player earns $1 for every link formed. Now the obvious solution to this game is for each player to link to each other player, maximizing their profits. However, consider a game where no player includes any other player on their list of potential links. These strategies also comprise a Nash Equilibrium: no player can unilaterally do better by adding any players to the list, because this will not result in the formation of additional links. Similarly, any other non-full network could be a (deeply inefficient) equilibrium of this game. Because Nash Equilibria require only that a player in isolation cannot improve her lot, these equilibria will never check whether players could jointly do better by adding links. Thus, it might be fruitful to turn to solution concepts that are robust to groups of players acting jointly.

Pairwise Stability

The inability of a player to unilaterally generate a link in a network formation game pushes us to a solution concept other than Nash Equilibrium: in particular, a solution concept allowing players to act jointly. The simplest of these concepts is Pairwise Stability. As defined by Jackson & Wolinsky (1996), a network (g) is pairwise stable if both of the following are true:

∀ i j ∈ g , u i ( g ) ≥ u i ( g − i j ) and u j ( g ) ≥ u j ( g − i j )

∀ i j ∉ g , if u i ( g + i j ) > u i ( g ) then u j ( g + i f ) < u j ( g )

The shortcoming of pairwise stability is that, while it can deal with a pair of players acting in unison, it can only compare a network to another that is one link away in either direction. To see the flaw in this solution concept, consider the following utility function for a five-player network formation game – if a player forms one or more links he pays a cost of $10; at the end of the game each player earns $1 for each link formed. This game has two pairwise stable networks, the empty network and the full network, but clearly the empty network is the more plausible result: any player in the full network could easily increase their payoff by changing their list to be an empty one. The ability for players to unilaterally remove any number of links would allow us to weed out this implausible equilibrium. We thus turn to a solution concept which combines the requirements of Nash Equilibrium and Pairwise Stability.

The solution concept: Pairwise Nash Equilibrium

Our solution concept, termed Pairwise Nash Stability, is simply that a network must be both a Nash Equilibrium of the network formation game and a Pairwise Stable Network. A network is considered a Pairwise Nash Equilibrium if:

No player can improve his payoff by unilaterally deleting any number of links that she is a party to.

The Pairwise Nash concept does have flaws. One is that a Pairwise Nash Equilibrium will not always be Pareto-efficient: if improving payoffs would involve three actors behaving in concert, further equilibrium refinements are needed. ¹ In addition, a pairwise Nash Equilibrium may not always exist: every possible network may be part of an improving cycle. An improving cycle is a set of networks C where, for some network formation game, any g ∈ C and g‘ ∈ C, there is a set of rational individual deviations that take us from g to g‘: for instance, decisions made by players to improve their utility in a game (either by adding or deleting links) take us from G to G′, from there to G″, and then back to G. If every possible network is in the improving cycle, there will be no Pairwise Stable Nash Equilibrium.

Thus, choosing a solution concept requires dealing with two competing demands: on the one hand we want to choose a solution concept where equilibria are not suboptimal or unrealistic, and on the other hand we want requirements that are not so stringent that nothing satisfies the solution concept. Pairwise Nash Equilibria will sometimes give second-best outcomes, but this will be driven by many of the collective action problems and fear of individual deviation that we find important in the study of international politics. Further, while Pairwise Nash Equilibrium can feature improving cycles, these are rare, especially when dealing with continuous convex utility functions, and failure to find an equilibrium may be the consequence of chaotic behavior and incentives given to players, rather than a failing of the solution concept. Finally, I find that Pairwise Nash Equilibrium rules allow for international cooperation (the Pairwise component), but does not lose sight of the fact that each actor is a rational maximizer (the Nash component).

An example of the solution concepts

Consider the following set of networks and payoffs, from a simple three-player system given by Jackson (2008: 375). Note here that the particular links in this network do not matter – simply that each player’s utility is determined by the total number of links in the network. If there are no links, each player gains 0 utility; if there is one link, the linked players gain 1 utility and the non-linked player gains 0. If there are two links, all players gain −2 utility, and if there are three links, all players gain −1. This network has three Pairwise Nash Equilibrium outcomes – any pair of players announce links with each other. ² Neither linked player here would choose to delete this link as he would lose utility. Further, no player would like to add an additional link as he would then lose more utility. The empty network is a Nash Equilibrium but not a pairwise equilibrium: if no player announces any other link, then deviation will never be profitable, but two players working in concert could both improve by forming a link. The network with two links is the worst of all possible worlds, and is clearly not an equilibrium, and the deletion of a single link would benefit all players, making it neither pairwise stable nor Nash. Finally, the full network is Pairwise Stable, as removing a link would decrease all players’ utility and adding one is obviously impossible, but it is not a Nash Equilibrium as any player could do better by unilaterally severing two links. This example clarifies the benefits of Pairwise Nash Equilibrium over other solution concepts, but we find the equilibrium network by examining each possible network; if the network were a few nodes larger, or the nodes were not identical, this would be a much more onerous task, so we turn to computational techniques.

Finding an equilibrium algorithmically

It is prohibitively difficult to find an analytic solution to a moderately complex network formation game. What is particularly challenging is that actors’ desires to add a link are conditional on all the other links in the network due to concavity and potential diminishing marginal returns. As a result this article turns to a computational solution via a program that finds a stable equilibrium of the game. The program uses the following algorithm:

Generate a network G. This could be a random network, or a theoretically interesting one (like an empty or full network). Specify a given utility function for each actor.

This equilibrium can, given time, find a Pairwise Stable Nash Equilibrium network. However, there are two remaining issues: multiple equilibria may exist and improving cycles can occur. Multiple equilibria will persist because Pairwise Nash Equilibria will find local maxima, as well as the global maximum to be stable. We want to find all equilibrium networks, especially if we want to compare these theoretical networks to observed networks. I accomplish this by running the algorithm multiple times using different (and random) starting networks – generated by making the links of the starting network the results of a Bernoulli(p) trial with differing values of p. Asymptotically this should give us the set of Pairwise Nash networks for a given utility function. When multiple equilibria are found, the researcher can choose criteria for deciding which to focus on. For example, when studying interstate cooperation (as this article does) one might choose to focus on a Pareto dominant game, given findings that cheap talk enables players to coordinate on the efficient outcome (Blume & Ortmann, 2007).

We also may see a problem with an improving cycle, where the algorithm takes us from G to G′, from there to G″, and then back to G. ⁴ This is both a technical problem and a substantive one. Substantively a network formation game may have no Pairwise Nash Equilibrium because every possible network is part of an improving cycle. This implies that no set of actions by the players in the game will be stable, and we will expect to see great change and upheaval in the network over time. We would like to know if, for a set of parameters, no stable network exists. However, it is also the case that a given game may have certain networks that are part of an improving cycle, and other networks that are on a path which leads to a stable network. Here, improving cycles become more of a technical problem. If the algorithm reaches a network that is part of the cycle, it will run indefinitely. I account for this by keeping a list of the stages the network has passed through, and if we return to one of these networks, we jump to a new, random network, and begin the algorithm anew. Before running the algorithm, one can also specify a threshold for the maximum tolerable cycle length: this is the number of different networks that are established to be part of a cycle before the algorithm terminates, or moves on to a different utility function. If we are particularly interested in finding out whether a given set of parameters has an equilibrium, this cycle length should be 2 ^N (the number of possible networks), but if we are just interested in finding an equilibrium network given approximate parameters, examining the entire network space will be prohibitively costly, in both computational power and time.

To summarize the process, we look at the utility each actor is getting from a network. We then compare that utility to all of the possible networks with one more link and see if both actors would be better off forming that link, and continue to do this until no more links are profitable. We then investigate whether any actor would like to unilaterally remove any number of links: we do this by looking at an actor’s neighbors, and seeing if that actor would be better off with any subset of those neighbors. Once we can iterate through all actors with no one choosing to add or delete any link, we have a Pairwise Stable network. If there are any issues with multiple equilibria, or improving cycles preventing us from finding an existing network, we attempt to avoid them by jumping to a different, random, network. This can require many iterations for a larger network.

A model of cooperation

When considering what to include in this model of network formation, I borrow much from the extant literature on international cooperation. In particular, I focus on the roles of similar domestic institutions, geographic proximity, and the links between conflict and cooperation. It is a model of cooperation generally, heeding Fearon’s (1998) argument that ‘understanding problems of international cooperation as having a common strategic structure is more accurate and perhaps more theoretically fruitful’.

Joint democracy and homophily

There has been a large and fruitful research agenda concerning the link between domestic regime types and conflict. Scholars have found quite consistently that democracies are less likely to engage in conflict with other democracies, and to a lesser degree, that autocracies are less likely to engage in conflict with other autocracies (Maoz & Russett, 1993; Bueno de Mesquita & Smith, 2009). There have been similar, albeit less prominent, findings about the link between regime type and international cooperation. Leeds (1999) finds empirical purchase for the idea that democracies are less likely to cheat and less likely to enter agreements with risk of cheating and so democracies are more likely to cooperate with other democracies, and autocracies with other autocracies, while Bliss & Russett (1998) find support for the existence of greater trade cooperation between democracies. Warren (2016) finds that states with similar domestic politics are likely to ally with each other, and that states allied with democracies are likely to become more democratic. The tendency of states to cooperate with similar regime types maps well onto the concept of homophily in network analysis. In fact, Maoz et al. (2006) found in the international alliance network that a model of homophily on domestic institutions was quite useful in explaining the formation of links. Similar regime types may be more likely to cooperate because of a shared risk and tolerance for cheating, or because domestic pressures reward them for cooperating with ‘good’ regimes more than bad regimes, but it seems both plausible and empirically justified that states should gain somewhat more utility when they cooperate with like regimes.

Contiguity

In recent decades, the proliferation of regional cooperative associations – the EU, ASEAN, NAFTA, to give a few examples – has highlighted the fact that in international cooperation, proximity matters. Partly, this is because many cooperative activities are cheaper when conducted over short distances: trade requires less costs to ship and it is easier to project military power in support of a neighboring ally than a distant one. It is also the case that proximate states are more likely to have similar interests that require cooperations: balancing against an aggressive mutual neighbor, dealing with refugees from a conflict in the region, or creating a larger economy of scale. Thus, when cooperation is with a more proximate stake, there are often higher benefits, and usually lower costs.

Conflict and cooperation

While conflict and cooperation are often seen as opposite actions in the international sphere, some research has shown that their relationship is closer and more complicated than that (Ward, 1982). On the one hand, when cooperating with a foe, states must be concerned with relative gains: there is a risk that a rival will take the benefits of cooperation and if they gained more, use that advantage to triumph in a future conflict (Grieco, 1988). On the other hand, if two states have conflicts, it is a signal that they both have interests in common, and the risk for future conflict. The first means that they have possible areas for cooperation, and the second increases the benefit of cooperation as a way to potentially forestall violent conflict – consider the recent agreement between the United States (and the rest of the P5+1) and Iran; the threat of conflict made cooperation more likely, and if conflict were impossible, no agreement would have been necessary. The presence of conflict makes cooperation more risky – if it fails the consequences may be more severe – but it also significantly increases the potential gains from cooperation and costs of non-cooperation.

Modeling cooperation

Given these stylized facts, I attempt to generate a network of interstate cooperation. To provide a test of concept, I look at the 50 states with the highest level of GDP, and attempt to generate a network of cooperation that would satisfy the Pairwise Nash Stability solution concept. To do this, however, there is a need to translate the thoughts and literature about cooperation into a formal utility function, and determine the functional forms that map each of these factors into utility and state action.

The goal for this utility function is not to provide a novel theoretical model of international cooperation, or to provide a perfect prediction of empirical cooperation. Rather, the goal here is a test of the network formation concept – can we generate a model with some interesting theoretical insights about cooperation that shares some similarities with observed patterns of cooperation? We can then learn from both the things the model gets right, and what it gets wrong. This can show the utility of network formation models and motivate further exploration, both to develop more ambitious theories and to create models that have more close fits to the empirical world.

The first jumping off point for our utility function is Jackson’s work on homophily networks. There the utility of a network to a player is

α log ( s ) + β log ( s + d ) + γ log ( d )

1

where s represents the number of links to nodes of the same type and d the number of links to nodes of different types. if α > γ, a network will exhibit homophily, whereas if γ > α it will exhibit heterophily; these will be mediated by the relative sizes of α, γ to β, as larger values of β will mute the effect of type. I first adapt this utility function to the case of interstate cooperation by mapping the ‘same’ and ‘different’ types to the subject of domestic political institutions. In particular, the distinction is between consolidated democracies on the one hand (Polity democracy score larger than 6) and non-democracy on the other. The next issue is that in interstate politics, not all states are equal – material resources matter and all else being equal, we would expect states to prefer cooperating with richer states rather than poorer states. So I replace s and d with the sum of the capabilities (normalized to between 0 and 1) of similar and different types of states. This maps to the finding in the literature that states are more likely to cooperate with other states if they have similar domestic institutions, and it also incorporates decreasing returns to cooperation, allowing the network to play a role in states’ decisionmaking processes.

I choose to have geographic proximity affect state utility through reducing the costs of war. In particular, this is because many types of cooperative behavior are easier and require fewer material resources when done over a smaller distance. Thus, we have one cost of conflict for non-contiguous states (c > 0) and a second, lower cost gc where g ∈ (0, 1) for those states that share a common border.

Our final factor brings in the possibility for state interactions that are conflictual. We look at event data for conflict above a certain threshold, and then we add (or subtract) utility to a player for cooperating with those states that the state is in conflict with (the additional utility is based on state capability). One could make the argument either way: a player has more zero-sum concerns about cooperating with potential enemies, but it also has higher benefits to improving the relationship, and more common areas of interest to make cooperation fruitful. So our final utility function is

U i ( G ) = α log ( ∑ same k j ) + β log ( ∑ k j ) + γ log ( ∑ ∼ same k j ) + κ ∑ k j I conflict − N close i c g − N far i c

where k_j is the capability of state j, I _conflict is an indicator function that takes on a value of 1 if two states have above a certain threshold of conflict and 0 else, N close i and N f a r i are counts of the number of contiguous and non-contiguous states cooperating with state i.

Data

To test the utility of this model of international cooperation, I take a subset consisting of the world’s 50 richest states. I limit my analysis to these states because increasing the number of states raises the time and computational power required for this analysis factorially. The states are chosen based on their economic prosperity, represented by total GDP in constant 2000 US dollars, from the year 2012. This also provides our measure of the benefits of cooperation. For these 50 countries, I take the square root of their total GDP and then normalize it to 1 by dividing by the largest value (that of the United States).

Our measure of political homophily comes from the Polity Project’s Democracy score (Jaggers & Gurr, 1995). This score is a 0–10 variable that measures the extent to which executive recruitment is open, there are constraints on the actions of the state’s executive, and there is robust political competition. The utility function includes a dyadic variable for contiguity. To obtain this variable I used the CShapes dataset (Weidmann, Kuse & Gleditsch, 2010), which includes values for the shortest distance between the borders of two states. If a state’s borders are less than 150 miles from those of another state, these states are considered contiguous and the cost of a link is adjusted accordingly. I also include a dyadic variable for the number of conflictual events. Here we use the counts of events coded as conflictual according to the CAMEO codebook in the ICEWS data in the year 2013: this is a dataset of machine coded stories taken from news articles.

Description of an equilibrium network

For this set of countries, we sought to find a Pairwise Nash Equilibrium with the parameters α = 1.4, β = 0.6, γ = 0.7, c = 0.075, κ = 0.5, g = 0.45 and the threshold for conflictual action set at 200. The values of α, β, and γ lead the network to exhibit homophily, as a state will gain 1.54 times as much utility only cooperating with similar states than it would if states with the same level of wealth were all different. The size of this effect will change once there is cooperation with both similar and different states, but the relative homophily will remain. The values of g imply that the benefits from cooperation with a neighbor need be less than half as high for it to be worth the cost. The value of κ implies that states will choose to cooperate with most of the richer states with whom they also have conflict, though the high threshold for conflictual action means that this will only inhere when the relative intensity of this conflict is quite large. The choice for the cost of cooperation was done with an eye towards the overall size of the network: if the cost were too low states would all cooperate with all other states; too high and the network would be too sparse for real analysis. This value allowed for a medium-sized network. The results change, but not radically when one makes small changes to the different parameters, and this sensitivity is shown in Figure 4.

The equilibrium network is depicted in Figure 1. ⁵ The 50 states had a total of 158 cooperative edges, with the most connected states being Germany and the United States (both had a degree of 11). The United States is part of a cluster with Germany, Japan, and China, with each linked to the other. The other notable clusters in the theoretic network were generally geographic: there was a cluster in the Middle East with Iran, the UAE, Saudi Arabia, and Turkey, and interestingly, a Pacific cluster centered on Indonesia, Malaysia, the Philippines, and Singapore.

Measures of network comparison

One useful test of the model’s descriptive ability would be looking at the characteristics of a theoretic network and how it compares to the observed networks. Authors working on Exponential Random Graph Models (henceforth ERGM) have proposed a form that looks at four descriptive statistics of graphs to determine how similar two graphs are. These four statistics are geodesic distance distribution, the proportion of dyads in the matrix that have a shortest distance of k links; the edgewise shared partner distribution, the distribution of EP₀, EP₁ ...EP_n−1 where EP_k is the number of links between two nodes that have exactly k neighbors in common, divided by the total number of links in the graph; the degree distribution, which is the distribution of the number of nodes with exactly k relationships; and the triad census distribution, the proportion of triads with exactly 0, 1, 2, and 3 edges between them. The statistics for our model of cooperation are described in Figure 3.

These network statistics drive home the commonalities of the two networks as well as where they diverge. The edgewise shared partner distribution and the triadic census vary little between the empirical and theoretical networks. However, while they share the same number of links, the theoretical network is much less centralized than the empirical one. This is shown most prominently in the degree distribution. The observed network has few very central states and a large number of more peripheral states, while in the theoretical network most states have a moderate number of links. The same seems to hold in the geodesic distance, where a greater number of dyads have no possible path between them, but those states with a path are more likely to have a distance of one or two, compared to the greater connectivity but longer mean distance of the theoretical network. One possible issue here is that the use of concave functions in the utility terms are poorly suited to the data generating process – diminishing returns may not hold for cooperation, as state A cooperating with state B may not reduce the benefit of cooperating with state C. The shared partner distribution and triadic distribution show remarkable similarities between the two networks.

Single value measures of network fit

While the four measures of network similarity in the above section ably characterize different facets of network structure, there is also value in providing single values that characterize how similar two networks are. In Table I, I present two such measures. I follow Koutra et al. (2011) in looking at the ‘eigenvalue method’ – a way of comparing two graphs by looking at the distance between the eigenvalues of the Laplacians. More formally, it generates Laplacians by first creating a diagonal matrix where the diagonals are each node’s degree, and it subtracts the adjacency matrix from the degree matrix. Then the method finds the sum of squared distances between these eigenvalues for the eigenvalues containing 90% of the network’s energy. The other single value metric of network comparison I look at follows Papadimitriou, Dasdan & Molina (2009) and looks at the difference in node ranking between two networks. This method computes Spearman’s ρ for the ranking of each node. It does so by computing:

ρ = 1 − 2 ∑ i = 1 n d i 2 n ( n 2 ) / 3

2

where d_i is the difference in rank between nodes and n is the number of nodes.

OPEN IN VIEWER

Figure 3.

Comparison of theoretical and observed network on four measures of network similarity

OPEN IN VIEWER

Table I.

Measures of network similarity

Method	Score
Eigenvalue method	1,104.87
Spearman’s ρ	0.53

The eigenvalue method compares two networks on the squared distance between their Laplacian’s eigenvalues, where identical networks would score 0 and dissimilar networks would score highly. Spearman’s ρ is used to compare the ranks of nodes in a network based on their out-degree. Identical networks would have a score of 1, perfectly reversed rankings would have −1, and unrelated networks would in expectation score 0.

The single value measures of network similarity show that while the theoretical network captures some valuable facets of interstate cooperation, it still diverges in important ways from the empirical network. The networks are strikingly dissimilar according to the eigenvalue method where small values indicate greater similarity. In particular, here, the greater centrality and degree of a few states leads to an extremely large dissimilarity in the eigenvalues. On a more positive note, the networks are markedly similar in their ranking of the nodes. By this measure, −1 would indicate reverse correlation with the rankings, 1 would indicate a perfect fit, and 0 would be no relation between the rankings, and so a Spearman’s ρ greater than 0.5 indicates serious commonality between the rankings.

OPEN IN VIEWER

Figure 4.

Comparison of theoretical network and ten alternatives on four measures of network similarity

Sensitivity to alternate parameter values

One important question that might be asked is whether the results shown in this article are knife-edged – whether we are presenting and discussing a network equilibrium relying on very precise parameter values. To investigate this possibility, I re-ran our algorithm and found equilibrium networks holding all else equal and changing one of five main parameters (c, g, α, β, γ) increasing or decreasing its value by a factor of 0.05. We can then compare these new equilibrium networks to our previous theoretical equilibrium. These alternative networks range in size from 129 (when γ is decreased to .665) to 168 (when c is increased to .07125). ⁶ The network statistics are compared in Figure 4. As can be seen in the figure, the degree distribution is notably sensitive to the particular parameter values chosen, but the other measures seem comparatively stable. This provides some reassurance that the inferences drawn about the similarities between the triadic distribution and shared partner distribution in our empirical and theoretical networks are stable to small changes in parameter values, and that if I have made small misspecifications of the different parameters it will not lead to inference that is far off-base.