The Stability of Exchange Networks

Gonul Dogan

Department of Methodology and Statistics, Tilburg University

M.A.L.M. van Assen

Department of Methodology and Statistics, Tilburg University

Arnout van de Rijt

Department of Sociology, Cornell University

Vincent Buskens

Department of Sociology, Utrecht University

Running head: Stability of exchange networks

Word count:

± 8,000

*

We thank Jacob Dijkstra, Willemien Kets, and Hans Reinierse for their comments

and advice. Direct all correspondence to Marcel van Assen, Department of Methodology and Statistics, PO Box 90153, 5000 LE Tilburg, The Netherlands; m.a.l.m.vanassen@uvt.nl.

1

The Evolutionary Stability of Exchange Networks

ABSTRACT

This paper develops a formal model of exchange network stability that combines expected value theory with the economic literature on network dynamics. We identify stable and efficient networks up to size 8 for link costs from 0 to 12. Only a very small number of networks are stable. At high cost the sets of stable and efficient networks coincide. These networks consist of dyads and at most one isolate. At low cost stability and efficiency do not typically go together. We also find that in many stable networks actors obtain unequal payoffs but egalitarian networks are stable in a wide range of costs. The introduction of stronger stability concepts does not resolve the conflict of stability and efficiency.

2

1. INTRODUCTION

An exchange network is a graph where nodes denote players and edges are the links between the players. A link constitutes an exchange relation. An exchange relation is an opportunity to split a common resource pool of size 24 in the present paper. Exchange occurs if two connected actors can agree on a division, if they do not agree they obtain no payoff. Moreover, players can only engage in one exchange, the so-called one-exchange rule. Figure 1 depicts a simple exchange network of four players, the Line4. In this network A has a possibility to exchange with B, B with either A or C, C with either B or D, and D with C. The one-exchange rule together with our representation of exchange networks is ubiquitous in research on exchange networks.

Figure 1

The one-exchange rule together with the position of the players in the graph affects how resource pools are split. The rule provides certain actors with a credible threat in the bargaining process, namely to exclude an exchange partner by turning to an alternative exchange partner. The main result of both theoretical and empirical research on exchange networks is that network structure has a huge impact on what actors earn. Since different positions in the network lead to different payoffs, important questions are how these networks evolve in the first place, and which exchange networks are stable or resistant to change.

Stability of networks has been investigated in economics (e.g., Dutta and Jackson 2003) but has not yet been applied to exchange networks as studied in

A B C D

3

sociology and in the present paper. The question of how exchange networks evolve has received little attention in the literature (Kollock 1994). Only a handful of theoretical studies and, to our knowledge, not a single empirical study on the evolution of exchange networks has been carried out whereas there exist extensive experimental investigations of static exchange networks (Willer and Willer 2000:252). In these experiments, networks are exogenously determined by the experimenters. Hence, by fixing the network, one of the most powerful tools to enhance outcomes of exchange is ignored: negotiating changes in the network itself (Leik 1992:309). Therefore, a desirable step in expanding theory on network exchange is to formally incorporate an actor’s potential to manipulate (i.e., to delete and add) his links, thereby enhancing his bargaining power in subsequent exchanges, thus indirectly increasing his expected payoff.

In the present study we allow actors to manipulate their links in order to answer the following three research questions: (i) (ii) (iii)

Which networks are stable for varying link costs? Are stable networks efficient?

Are stable networks egalitarian and are egalitarian networks stable?

Question (i) reveals that we only study the possible end products of the evolution of an exchange network, and not the evolutionary paths to get there. The notion stability reflects that no actor in the network is willing to change his links, i.e., it can be considered an equilibrium concept. More precisely, a network is defined as stable if no pair of actors can both benefit from initiating a link between themselves and no single actor can benefit from deleting one of his links. This type of stability is called pairwise stability (Jackson and Wolinsky 1996:48), and is borrowed from the game-

4

theoretic literature on network change (see Dutta and Jackson 2003 for a review). Pairwise stability is similar to Nash equilibrium of the game where players simultaneously choose with whom to link. However, different from Nash equilibrium pairwise stability takes into account two players. We will also consider two refinements of pairwise stability, pairwise Nash and unilateral stability.

Question (ii) addresses if stable networks are also efficient. A welcome result

would be that all possible evolutionary paths result in efficient allocations. We mainly employ the standard definition of Pareto efficiency: A network is considered Pareto efficient if there is no other network in which no actor earns less and some actors earn more. Finally, question (iii) concerns the equality of payoffs of actors. Because all actors can start from an equal footing, a ‘fair’ result would be that their payoffs are equal in stable networks.

Since it is reasonable to assume that links are not costless, i.e., both actors

need to invest effort in maintaining the link, we investigate the three questions concerning stability, efficiency, and equality, as a function of the value of link costs.

Related research and the assumptions underlying our analysis are discussed in Section 2. We also motivate our selection of Friedkin’s (1992, 1993, 1995) expected value theory (EVT) to derive our predictions of exchange outcomes and to investigate the stability of exchange networks. In Section 3, we introduce our model of network evolution. Our research questions are explicated. In Section 4, the results of our analyses are presented. We conclude with a discussion in Section 5.

5

2. THEORETICAL BACKGROUND

The basic assumptions underlying our analysis are in line with those employed in the literature on exchange networks (e.g., Leik 1992; Markovksy et al. 1988, Willer and Willer 2000):

(1) The number of nodes in the network is constant. (2) Only directly linked nodes can engage in exchanges. (3) All resource flows must be dyadic.

(4) The joint profit for any exchange is constant.

(5) All actors are involved in at most one exchange (the 1-exchange rule). As a baseline to analyze the dynamics of exchange networks, we add the following conditions:

(6) Actors have complete and accurate information about all network links. (7) Actors act as if they use the same theory to predict the consequences of adding and deleting links.

(8) Actors try to maximize their own payoffs.

Assumption (7) can also be phrased as: “Actors add and delete links and act upon it as if they were applying EVT of Friedkin (1995)”. ‘As if’-assumptions are common in the social sciences, one famous example being the assumption in economics that actors are behaving as if they were rational maximizers (Friedman, 1953).

Many theories of exchange networks have been developed and tested in the last three decades; power-dependence theory (e.g., Cook and Emerson, 1978; Cook and Yamagishi, 1992), exchange-resistance theory (e.g., Skvoretz and Willer, 1993), a

6

graph-analytic theory using the graph-theoretic power index (GPI) (e.g., Markovsky et al., 1988), core theory (e.g., Bienenstock and Bonacich, 1992), optimal seek theory (Willer and Simpson, 1999), identity theory (Burke, 1997), Yamaguchi’s (1996; 2000) rational choice model, expected value theory (e.g., Friedkin, 1992), and non-cooperative bargaining models (Berg and Panther, 1998; Braun and Gautschi, 2006). Four theories have received much more attention in the literature than the other theories. These are the approaches that have appeared in special issue 14 (3-4) of the journal Social Networks on exchange networks; core-theory, power-dependence theory, expected value theory, and NET, which is the collection of exchange-resistance, GPI, and optimal seek theories.

A requirement for our analysis of stability of networks is that the exact effect

of adding and deleting links on actor payoffs is computable. Hence unique point predictions are required. Since core theory and power-dependence theory do not provide unique point predictions they are not suitable in our investigation. We also did not select NET because (i) there are several different versions of the theory, and (ii) there is no computerized version available of the most recent version of NET advocated by its developers (Emanuelson 2005; Emanuelson & Willer 2006).

Consequently, we select the remaining theory, Friedkin’s (1992; 1993; 1995) expected value theory (EVT). Although uniqueness and existence is not proven for all networks, for every network up to 8 actors, the algorithm of EVT generates a point prediction.

There exist two other approaches relevant to the study of the evolution of exchange networks. Firstly, Bonacich (2001) simulates exchange network evolution and finds that in equilibrium payoff differentials are small. In Bonacich’s simulation, agents are myopic satisficers: They change the network if their earnings drop below a

7

certain level. Our actors are myopic maximizers: they keep changing the network as long as marginal benefits outweigh marginal costs. Another difference is that instead of adding or deleting links, Bonacich’ actors move to another cell on a checkerboard, where they can exchange with actors in adjacent squares. Bonacich (2004) provides some intuitions for how this approach can be extended to more general structures.

The second approach is a rapidly growing literature on network formation in economics (e.g., Dutta and Jackson 2003). The networks considered by the standard model in this literature are highly similar to exchange networks. The standard model assumes that networks are simple (Wasserman and Faust 1994:95), i.e. loops (links that go to the same node) are absent and each network has no more than one link between each pair of nodes. Links are also non-valued (Wasserman and Faust 1994:140), i.e., of equal strength, and they are undirected (Wasserman and Faust 1994:72). Note that exchange networks are also simple networks. Moreover, the concept of pairwise stability that we borrow from this literature derives from a model of network formation in which actors try to maximize their own payoff, and add and delete links one by one. Actors derive utility from the network that is obtained immediately after their link manipulation, and only have control over links between themselves and others. Although economists investigate ‘games’ other than the game of network exchange, we share their stability concepts and the network formation model it derives from. We thus explicitly bring together research on network exchange in sociology and research on network change in economics. Expected Value Theory (EVT)

Building upon the theory of social power proposed by French (1956), Friedkin (1986) first suggested the idea of using expected values to predict the outcomes in a power structure. Friedkin (1992; 1993) extended the idea of expected values to analyze

8

outcomes in an exchange network. Friedkin’s model predicts the probability that each maximal exchange pattern occurs, and the outcome distribution of each of these patterns. A pattern is maximal in the sense that no further feasible transaction exists. For example, the Line4 that has two maximal exchange patterns; {{A-B}, {C-D}}, and {{B-C}}. Using an iterative algorithm, each actor’s expected payoff is calculated as the expected value of his payoffs over all possible maximal exchange patterns.

As opposed to what the name of Friedkin’s theory suggests, EVT is not a

theory based upon actors rationally maximizing their payoffs. The algorithm generating the predictions assumes that both actors’ claim of their share of the 24 points in their relation is increasing non-linearly in the probability that each of them is excluded in any exchange. Three rules determine the final allocation in the relation. Which rule is applied depends on the sum both actors’ claims and their claims relative 12 points. An inconvenience of the EVT model is that because of the non-linear function and the three rules the algorithm is analytically intractable. See Friedkin (1995) for details of the EVT model that is used to generate the predictions.

3. STABLE EXCHANGE NETWORKS: APPROACH AND HYPOTHESES A model of exchange network stability is needed in order to be able to evaluate if actors in a network want to add or delete a link in the exchange network. Our model assumes that for establishing a link between two actors mutual consent is required, while deletion of a link is unilateral.

The resource divisions for each exchange network are predicted with EVT (Friedkin 1995). For all exchange relations in each network we check if they are candidates for deletion by comparing the original EVT predictions to the EVT

9

predictions after deleting the link. Similarly, for all pairs of actors without a direct link we check if the absent links are candidates for addition. Note that if two actors are both indifferent with respect to the absence or presence of a link, that link will neither be added to the network that does not contain that link nor be deleted from the network containing it. Hence, ‘not adding’ and ‘deleting’ are not two sides of the same coin.

Friedkin’s EVT is a system of many assumptions and equations that makes a formal analysis very difficult. Therefore, we choose to analyze a large subset of all possible exchange networks; all 13,597 exchange networks of size 2 through 8 are investigated. Of these networks 12,112 are connected and 1,485 are not (see sequence A001349 of Sloane’s Online Encyclopaedia of Integer Numbers). A network is connected if a path exists from each node to every other node. We need to consider unconnected networks as well, because through link deletion networks can become unconnected. Moreover, it will be demonstrated that many stable and efficient networks are unconnected.

Stability and efficiency of exchange networks

In our approach, stable networks are defined as exchange networks that are pairwise stable (PS). An exchange network is PS if (i) adding a currently absent link is costly to at least one of the two actors or leaves both actors equally well off, (ii) removing a present link does not benefit either of the two actors it currently connects. Jackson and Wolinsky (1996) introduced the pairwise stability concept because it is the weakest notion of stability which allows for link formation while narrowing down the set of stable networks substantially. It is important to note that this and the subsequent stability concepts do not say anything about the graph formation; hence how the stable networks are reached is a question that we do not aim to answer in this paper.

10

As an example of how to utilize the notion of PS, consider an 8-actor network where actor H is connected to actors A,B,C but not to other actors, denoted by the ‘adjacency row’ 1110000. Then, with regard to actor H, PS holds if no single change from 1 to 0 (the deletion of one link) increases H’s expected payoff, and if no single change from 0 to 1 (the addition of one link) increases the expected payoff of H while not decreasing the expected payoff of the other actor. Hence, only N-1=7 changes of the network are considered for that actor. A network is PS if this condition holds for each actor in the network.

The PS concept perfectly fits our model of network exchange stability; link

deletion is unilateral and for establishing a link mutual consent is required. Moreover, the PS concept directly tells us which present (absent) exchange relations are profitable for the actors involved compared to a network where this exchange relation is absent (present). That is exactly what we need in order to answer our first research question. In addition, PS is the predominant stability concept employed in the game- theoretic literature on network formation (for an overview, see Dutta and Jackson 2003).

We hypothesize that all complete networks are PS when having links is costless, and that no networks are PS in which one actor earns a very high profit and other actors earn almost nothing (a so-called strong power network). Moreover, we hypothesize that the average degree of PS networks decreases in costs.

We also analyze the stability of exchange networks when there are link costs. In our analysis it is assumed that an equal cost is incurred for both actors involved in the link. Additionally, it is assumed that the cost of a link is independent of the number of links an actor has. Finally, the cost to establish a link is equal to the cost of maintaining a link. In our analyses the cost of a link varies from 0 to 12, where each

11

actor involved in the corresponding link pays this cost. Note that link costs larger than 12 need not to be considered, because an exchange relation can only generate 24 points. Hence, always at least one actor in the relation wants to delete the link for such high costs; only networks without links are then PS.

With the introduction of link costs inefficient PS networks might arise.

Efficiency here is defined as Pareto efficient; there exists no other network in which no actor earns less and at least one actor earns more. To determine if a network of a certain size is Pareto efficient, the actor payoffs in a network are first ordered in a vector from large to small for all exchange networks of the same size. A network is then Pareto efficient if no other network’s payoff vector is strictly larger than that of the network under consideration.

We will categorize both efficient PS and inefficient PS networks. The

inefficiency of PS networks can be due to our limiting of the actors’ action space. PS considers only single link changes. Allowing actors to make multiple link changes at once may help them escape an inefficient PS network. For example, in a complete 3-actor network with link cost 5, the expected payoff of each actor is 8 – 2×5 = −2, while in the empty 3-actor network, each actor’s expected payoff is 0. The complete 3-actor network is nevertheless PS; if one actor deletes one of his links, his expected payoff decreases from –2 to 1.45–5 = –3.55. Only after deletion of two of his links does an actor’s payoff increase to 0. To eliminate such inefficient PS networks, two additional stability concepts are employed that allow for simultaneous actions other than just one deletion or addition of a link at a time. Both stability concepts are refinements of PS, that is, if the networks are stable using one of these concepts, these networks are also PS.

12

A network is strongly pairwise stable (Gilles and Sarangi 2004:13) or pairwise

Nash (PN) (Calvó-Armengol & İlkılıç 2004:7) if (i) adding a presently absent link is costly to at least one of the two actors or leaves both actors equally well off; and (ii) removing a subset of an actor’s present links does not benefit this actor. Note that (i) of PN is identical to condition (i) of PS. The difference between PS and PN is that PN allows for simultaneous deletions in (ii). The complete 3-actor network with link cost equal to 5 is PS but not PN, because an actor profits from deleting both of his links simultaneously. Continuing our other example, consider again the 8-actor network with H’s adjacency row equal to 1110000. PN holds for H if each change of one 0 to 1 does not increase the payoff of H and the other actor is not worse off, and each change of a subset of 1s to 0s does not increase H’s payoff. Hence, in total 4+23–1 = 11 changes are considered for that actor. A network is PN if this condition holds for each actor in the network.

An undesirable feature of PN is that it is asymmetric: it is concerned with the

effect of the deletion of one or more links and of the addition of a single link. It also does not allow for simultaneous addition and deletion of links so that a network in which actors can only make themselves better off by replacing one relation by another relation is still considered stable. In unilateral stability (US), a refinement of PN, this asymmetry problem is resolved. A network is US if no actor can profitably reconfigure his ego-network without objection by his new contacts. In our example, US holds for H if no adjacency row other than 1110000 simultaneously (i) increases H’s payoff, and (ii) makes no actor connected to H in the new adjacency row, but not in the old one, worse off. Only the actors newly connected to H in the new configuration or adjacency row have to agree, because only for creating new links mutual consent is required. Note that H is allowed to consider all possible 2N−1−1 =

13

127 reconfigurations of his ego-network. A network is US if this condition holds for each actor in the network.

4. RESULTS

4.1 Stability as a function of link cost

To see which networks are PS with changing costs, we checked whether each network is PS and if PS then in which cost interval. Across cost intervals 0 to 12, in total, 1 different PS exchange networks exist, which is only 1.39 % of all exchange networks up to size 8. Hence PS is a rare attribute of exchange networks of small size.

When there are no costs of adding, maintaining and deleting a link there are 10 PS networks. As expected, all 7 complete networks are PS. For the networks of size 5 and 7 also networks consisting of two unconnected complete networks are PS. With 5 actors, a dyad and a triangle that are not connected is PS. Likewise, when there are 7 actors, the combination of the complete 3 and 4, and complete 2 and 5-actor networks are PS. These unconnected networks are PS because no one wishes to delete any link and if the two parts in the network are connected, the payoff decreases for the actor in the larger sub-network that connects to the smaller sub-network. As an example consider the disconnected dyad and triangle. The actors cannot gain from deleting any existing link. As for adding a link, the expected payoff of the actor in the triangle connected to the dyad becomes 7.46, while before the addition it was 8 points..

With the introduction of costs, we see a pattern of emerging stable networks. Starting at zero cost and gradually increasing cost, complete networks destabilize, PS networks become less dense and we end up with only dyads when link cost is in the open interval (6.551,12). For example, consider the PS of complete networks at increasing levels of cost. The only PS complete network at cost 12 is the dyad with 2

14

actors. Of all complete networks, the 7-person network destabilizes at cost 0.395, the 5-person at cost 0.839, 8-person network at cost 1.325, the 6-person network at cost 2.1038, the 4-person at cost 4.026 and the triangle at cost 6.551.

We also investigated the cost ranges for which networks are PS. A cost range

is defined as the width of the interval a network is PS. For example, the cost range for which the triangle is stable is 6.551 since it is stable from cost level 0 to 6.551. When we look at the range of costs that networks are PS, we see that only 62 PS networks are stable for a cost range of 0.5 or more; the median cost range is 0.213. A large number of PS networks, 127 of the 1, are stable for a cost range of 0.5 or less. There are only 24 networks which are PS in the cost range between 2.5 and 12. So, the majority of the PS networks are very sensitive to the cost level and destabilize even in small cost changes.

The gradual change in the number of stable networks across size as a function of cost level is shown in the Figure 2. There is a gradual increase in the number of stable networks up to cost 0.42, between 0.42 and 0.72 the number of stable networks is around 21. At cost level 0.84, there is a drop to 14 PS networks but then it increases gradually to 46 at cost level 1.22. This is the maximum number of PS networks across all cost levels. The number of PS networks gradually but not monotonically decreases to 26 at cost level 1.53, increases from there on to 35 at cost 1.73, decreases to 19 at cost 2.43, increases to 36 at cost 3.48, hits the minimum of 7 at cost 6.55 and stays there until cost 12. At cost 12, empty networks are introduced to the set of PS networks, so there is an increase in the number of PS networks from 7 to 23.

The effect of cost on density is apparent from Figure 3. As expected, the average density of stable networks decreases until cost 4.11. Average density is approximately the same from there on until cost 12. At cost 12, the entry of empty PS

15

networks again lowers the average density. As an example of the negative effect of maintenance costs on the density of stable networks, consider the PS networks at size 4. For any cost in the interval [0, 4.03] the complete network is PS. The Box (Figure 1) is PS for any cost in [2.81, 5.14]. Two dyads are PS when cost is in [3.48, 12]. A triangle and an isolate is stable for costs in (4.11, 6.55). At cost 12 or higher, only the empty or null network is PS. Note that the often investigated Line4 network is never stable. Hence our analysis suggests that the Line4 exchange network will not often be found in real-life.

The analysis shows that networks consisting of unconnected dyads and one possible isolate (in case of networks of odd size), further called M(inimal) networks, are PS for high cost. This result can be generalized to networks of any size, as the following theorem shows.

Theorem 1: The M network is PS for any cost c in (3.48, 12).

Proof of Theorem 1: Consider an even sized network consisting of only dyads where everybody earns 12 – c > 0. Deleting a link decreases expected payoffs to 0. Adding a link results in a Line4 where the actor adding a link decreases expected payoff to 15.48 – 2c < 12 – c. Consider an odd sized network. If the only isolate in the network adds a link his expected payoff decreases to 1.45 – c < 0. QED.

From cost 6.551 to 12, only M networks are PS. Between cost 5.950 and 6.551, an additional nine networks are PS. These networks represent all possible networks consisting of at least one triangle complemented with dyads and at most one isolate (triangle; triangle & isolate; triangle & dyad; two triangles; triangle & dyad & isolate; two triangles & isolate; triangle & two dyads; triangle & two dyads & isolate; two triangle & dyad). The triangle is PS for costs c smaller than 6.551 because a

16

deletion of a link decreases the payoff of both actors in the link from 8 – 2c to 1.445 – c < 8 – 2c. Hence, all these 9 networks destabilize when the cost is larger than 6.551.

The absence of any other PS networks than M networks at larger cost than

6.551 suggests that for any cost c in (6.55,12) the only PS networks are M networks. Although we firmly believe this to be true, we were unable to prove it using Friedkin’s EVT. If the conjecture is false, then there exists at least one network in which each link has a marginal benefit to both actors in the link larger than 6.55. In Section 4.3 we will prove that if such a network exists, it is inefficient and the average actor payoff is smaller than 0 (see Theorem 4).

Finally, some important observations can be made from the PS networks in

our analysis. Firstly, no PS network is a so-called strong power network; there is no network up to size 8 with at least one actor who earns almost all points. Also, a majority of the PS networks yield payoffs which are less than or equal to 12 before subtracting the cost of links. Out of 1 PS networks, 32 of them contain payoffs higher than 12 for some players, before subtracting costs. Among these 32 networks, 9 networks include players with payoffs between 13 and 14 and 1 network where one player earns 14.69; in 22 networks some players earn between 12 and 13. After subtracting the costs of links, all payoffs fall below 12-c. The networks’ PS cost levels vary between 0.662 and 2.723. Thus we do not observe PS networks with payoffs higher than 12 after the cost of 2.723. All of the 32 networks are PS within the cost range of 0.428, moreover 25 of the 32 is PS within the cost range of 0.2. So the networks where some players earn substantially more tend to be less stable than the networks where players earn either equal payoffs or similar payoffs. 3 of the 32 networks are size 6, 3 of them size 7 and the rest is size 8. The average density of these networks is 0.538 which suggests that players roughly have half of the links that

17

they would have in a complete network. Hence, in these networks, players tend to over-connect compared to minimal efficient networks. 4.2. Stability and equality of exchange networks

EVT only predicts egalitarian networks if these networks are symmetric, i.e., all actors in the network cannot be distinguished using network positions. Of all 13,597 networks, 56 networks are egalitarian, which is only a very small percentage (% 0.004). Of the 56 networks, 12 of them consist of dyads and isolates but are egalitarian only at cost level 12. Out of 1 different PS networks 42 exchange networks have equal payoffs within the cost range they are stable and a further 12 of them are egalitarian only at cost 12, which amounts to % 28.571 of all PS networks. Except 2 egalitarian networks of size 8, all egalitarian networks are also PS.

Among the 42 egalitarian symmetric PS networks, 7 networks occur at cost level 0, 4 networks emerge between cost 0 and 1, 14 networks between cost 1 and 2, 5 networks between cost 2 and 3, 5 networks between cost 3 and 4, and 7 networks at cost 12.

When we look at the cost range these networks are PS, we see that egalitarian networks tend to be PS over a larger range than non-egalitarian networks. 35 of the 42 egalitarian symmetric PS networks are stable in a cost range of 1 or more. In contrast, all 116 of non-egalitarian PS networks are PS in a cost range less than 1. Also, 88 of the 116 non-egalitarian PS networks are PS only in a cost range of 0.30 or lower. Hence non-egalitarian networks are very sensitive to small changes in cost and tend to destabilize quicker than egalitarian networks.

18

4.3. Stability and efficiency of exchange networks

We address three issues in this section. Firstly, we investigate if there are many Pareto efficient networks that are not PS. Secondly, we check if PS networks are Pareto efficient for the interval of cost levels for which they are stable. Since we compare PS networks to all networks of the same size, we call this global efficiency. An interesting situation would occur if none of the PS networks at a certain cost level is globally efficient. This situation resembles a social dilemma situation with only sub-optimal equilibria. We check if these social dilemma situations exist. Thirdly, we examine Pareto efficiency within the set of PS networks. We call this local efficiency. Here, an interesting situation occurs if at least one PS network is dominated by another PS network at a certain cost level. This situation resembles a coordination problem, and we check if these problems exist. Note that a coordination problem and a social dilemma problem as described here can occur at the same time.

Addressing the first issue, it can easily be shown that many Pareto efficient

networks exist at cost 0. Consider all networks in which always a maximal number of exchanges is completed for that size, called F networks in Theorem 2. This maximum, denoted by FX, is equal to N/2 if N is even and to N/2 – ½ if N is odd, where N is the size of the network.

Theorem 2: F networks are efficient at zero costs.

Proof of Theorem 2: In F networks a maximum sum of payoffs is divided among the N actors. Since the sum of payoffs to be divided in all these networks is equal, one of the networks cannot Pareto-dominate the other. Q.E.D.

There are many F networks. However, there are only very few PS networks at zero costs. Consequently, at zero costs there are many efficient networks that are not PS.

19

When costs are introduced Theorem 2 no longer applies. To derive statements

concerning the efficiency of PS networks another theorem is required.

Theorem 3: An M network is Pareto efficient for any cost in the closed interval [0,12].

Proof Theorem 3: Exactly FX exchanges are carried out in the M network that consists of exactly FX links. Hence the total payoff to be divided in the M network is equal to FX(24 – 2c) ≥ 0 if c ≤ 12. Adding a link decreases the payoff to be divided with 2c, deleting a link decreases the payoff to be divided with 24 – 2c ≥ 0 if c ≤ 12. Since there is no network with a larger payoff to be divided, the M network is Pareto efficient. Q.E.D.

Note that the M network is the only network that is efficient for costs in the interval (0,12) when defining efficiency of a network as the maximum sum of actor payoffs across all networks of the same size.

28 PS networks are globally efficient for all costs in the interval that they are PS. Of the 28, 23 networks either consist of the dyads and isolates or are empty networks. The other 5 undominated networks are PS in a cost range of 0.383 or less. Thus there are only 7 networks consisting of dyads and at most one isolate, for each size from 2 to 8, which are undominated in a wide range of costs. The other PS networks are either dominated on the whole range of costs that they are stable or dominated partially. Out of 1 PS networks, 161 of them are dominated by other PS networks. Since there are 28 undominated networks all PS networks are dominated by other PS networks. Among the 161 PS networks that are dominated by other PS networks, only 16 of them are not completely dominated in the cost range that they are stable. Among these 16 networks only 7 of them are undominated within the range

20

of 0.075 or more. The least dominated PS networks are the triangle, the triangle with a dyad, the pentagon, the pentagon with the dyad and the heptagon. So, in addition to the dyads and at most one isolate at each size, the 3, 5 and 7 cycles are the most stable and efficient networks. Moreover even if we take into account the non-PS networks that might dominate these cycles, the results do not change except in one network where the dominance range slightly increases. So comparison of PS networks in terms of efficiency to all networks do not provide us with additional information; either they are dominated by other PS networks in their whole range of stability or they are partially dominated by other PS networks which gives the same result as the comparison with non-PS networks.

When we analyse the local efficiency of the PS networks, we see that 76 PS networks are totally dominated by other PS networks that are stable in the same range. A further 63 networks are partially dominated within the cost range that they are stable. Since there are 28 globally undominated networks, the remaining 22 PS networks are not dominated by other PS networks within their interval of stability. They are either locally undominated or only dominated by non-PS networks. There exists 7 networks which are locally undominated and 15 of them are only dominated by non-PS networks. There does not exist a cost level for which all networks that are PS at that cost are dominated by unstable networks. Hence, no social dilemma situation exists. However, since most of the PS networks are dominated by other PS networks, there exist coordination problems.

At cost 0 all PS networks are globally efficient. From cost 6 to 12 (excluding 12 itself) only the seven M networks, one for each size, are globally efficient. This result can be generalized to networks of any size.

21

Theorem 4: The only PS networks that can be globally efficient at costs greater than or equal to 6 are M networks.

Proof Theorem 4: Theorem 3 indicates that an M network is efficient. It remains to be shown that an M network is the only efficient network for c ≥ 6. If it can be shown that the theorem is true for c = 6, it is also true for all c > 6 because the actors’ degree and hence their costs are minimized in the M network. The theorem is false if either (i) there is a network in which all actors obtain a positive expected payoff if the number of actors is odd, or (ii) there is a PS network in which one actor obtains more than 12 – c points. Let us first show that (i) is false. First assume the network is odd and of size n + k, with n even and k odd. All n actors form dyads, and the k actors form a connected network. All k actors must connect, otherwise at least one of them does not obtain a positive payoff. The sum S of actor payoffs including costs in the connected k-actor network is never more than S = (k-1)×12 – t×12, with t denoting the number of links. Note that t ≥ k – 1, otherwise the k actors cannot be connected. If t > k – 1 then S < 0 and there must be at least one actor obtaining a negative payoff. If t = k – 1, S = 0 if at most one actor is excluded. If t = k – 1, then there are at least two actors who have only one link. For size ≥ 7 there is a positive probability that both actors are excluded together with an odd number of other actors, hence S < 0 and there must be at least one actor obtaining a negative payoff. Recall that none of the networks with t = k – 1 is stable for size < 7. Hence (i) is false.

Consider part (ii). An actor can only earn more than 12 points if he has more

than one link. If he has one link he obtains at most 12 – c when he is a member of a dyad. If he has three links or more his expected payoff is smaller than 12 – c because he can never gain 24 points excluding costs. Consider an actor having two links. The marginal value of the link for both of his partners must be at least 6. If one of his

22

partners obtains at least 6, he can never get more than 18 in his exchanges with his partners. Consequently, he obtains 18 – 2c < 12 – c. Q.E.D. 4.4. Refinements of Pairwise Stability

Previously we argued that a disadvantage of the notion of PS is that it does not

take into account that an actor can delete more than one of his links simultaneously. Perhaps this disadvantage is the cause of the existence of many (pairwise) stable inefficient networks. The notion of pairwise Nash (PN) eliminates this disadvantage and allows for the deletion of more links at the same time. Although PN eliminates some of the PS networks that are not efficient, PN also eliminates PS networks that are efficient .

A further refinement of PS is US. US enables actors to add more than one link

simultaneously as well. Hence, it eliminates situations where the addition of one link does not increase the expected payoff of the actors involved, but the addition of more than one link does. Moreover, actors can also add links and delete links simultaneously. US further eliminates inefficient PS networks. Many of these networks either contain one isolate [isolate & dyad & box, isolate & 4-cycle or Box, isolate & 5-cycle, isolate & 6-cylce, isolate & 7-cycle] or at least one triangle.

One general result can be proved concerning the US and PN of M-networks.

Theorem 1 is a special case of Theorem 5.

Theorem 5: An M-network of any size is US (and therefore also PN) for any cost c in (3.48,12).

Proof Theorem 5: Consider an odd sized M-network of size 13 or larger. If the network is US, neither a reconfiguration of the ego-network of the isolate nor of a member of a dyad is accepted. Let us first consider each possible reconfiguration of

23

the ego-network of the isolate. The isolate has no links to delete and can maximally profitably add six links, because then c × 3.48 > 24. If the isolate wants to add links to both actors in one dyad, EVT reveals that these actors reject his proposal because their payoff is lowered independent of which other links are added. If links are added to one actor of different dyads, the isolate obtains a disadvantageous position resulting in a low expected payoff that does not exceed the link costs. Consequently, the isolate does not want to add links in odd-sized M-networks smaller than size 13. Let us now consider reconfigurations of the ego-network of an actor in a dyad. This actor cannot improve his payoff by adding more than four links, since then he earns 24 – 5×3.48 or less, which is less than the 12 – 3.48 he earns in the M network. Three changes are possible; (i) If he proposes to connect to the isolate, the isolate always rejects the proposal. (ii) If he proposes to add links to actors of the same dyad, these actors reject the proposal. (iii) Finally, EVT reveals that if he connects to one or more actors of up to four different dyads, the other actors reject his proposal. Hence also in odd-sized M-networks smaller than size 13 actors in dyads do not want to change their ego-network. End of proof for odd sized networks. Note that the combination of (ii) and (iii) complete the proof for even sized networks of any size.

To conclude, US does eliminate both efficient and inefficient PN networks. Because often more than one network is stable and outcomes are often not equal across actors, using stronger stability concepts based on more forward looking actors does not solve many coordination problems.

24

5. DISCUSSION

In the present paper we attempted to analyse exchange networks. Both theoretical and empirical research on exchange networks shows that network structure has a huge impact on what actors earn. Nonetheless, there has not been extensive research on the stability of exchange networks. We investigated exchange networks up to size 8 using Friedkin’s (1992, 1993, 1995) EVT theory. We checked which networks are stable for varying link costs, whether stable networks are efficient, and whether stable networks are egalitarian. We used pairwise stability (Jackson and Wolinsky 1996:48) as the basic stability concept.

Our analysis shows that, out of 13,597 networks, there are 1 different PS networks across cost levels 0 to 12. When there are no costs of adding, maintaining and deleting a link there are 10 PS networks. As expected, all 7 complete networks are PS. With the introduction of costs complete networks destabilize, PS networks become less dense and we end up with only dyads when the link cost is in the open interval (6.551,12). The M network is PS for any cost c in (3.48, 12). The majority of the PS networks are very sensitive to the cost level and destabilize even in small cost changes. Moreover, there is no network up to size 8 with at least one actor earning almost all points. A majority of the PS networks yield payoffs which are less than or equal to 12 before subtracting the cost of links.

When we look at the stability of the network and equality of payoffs, we see

that of all 13,597 networks, 56 networks are egalitarian, which is only a very small percentage (% 0.004). Out of 1 different PS networks 42 exchange networks have equal payoffs and a further 12 of them are egalitarian only at cost 12, which amounts

25

networks are also PS. Although non-egalitarian networks are very sensitive to small changes in cost, most egalitarian networks are stable within a wide range of costs.

For the analysis of efficiency of PS networks we investigated if there are many

Pareto efficient networks that are not PS. It is shown by a theorem that at cost level 0 all networks with maximal exchanges are efficient. It is also the case that there are many efficient unstable networks at other cost levels. We also found that 28 PS networks are globally efficient for all costs in the interval that they are PS. There are only 7 networks consisting of dyads and at most one isolate, for each size from 2 to 8, which are undominated in a wide range of costs. Out of 1 PS networks, 161 of them are dominated by other PS networks. We showed that the only PS networks that can be globally efficient at costs greater than or equal to 6 are M networks. When we analyse the local efficiency of the PS networks, we see that 139 PS networks are either totally or partially dominated by other PS networks that are stable in the same range. There is no cost range where all PS networks are dominated by non-PS networks; hence social dilemma situations don’t exist.

The analysis of PN and US networks reveal that although some inefficient

networks are eliminated through these stronger stability concepts, there still exist coordination problems and inefficiency among stable networks.

Further research on the stability of exchange networks might include the

analysis of actors’ preferences for equality and/or efficiency. It might also be interesting to check the evolution of the networks through simulations.

26

REFERENCES

Berg, Christopher and Stephan Panther. 1998. “Network Exchange as a Non-Cooperative Bargaining Game.” Unpublished manuscript.

Berninghaus, Siegfried K., Karl-Martin Ehrhart and Marion Ott 2005. “A Network

Experiment in Continuous Time: the Influence of Link Costs.” Working paper 05-02. http://www.sfb504.uni-mannheim.de/publications/dp05-02.pdf Bienenstock, Elisa J.and Phillip Bonachich. 1992. “The Core as a Solution to

Exclusionary Networks.” Social Networks 14:231-43.

Bonacich, Phillip. 1998. “A Behavioral Foundation for a Structural Theory of Power

in Exchange Networks.” Social Psychology Quarterly 61:185-98.

Bonacich, Phillip. 1999. “An Algebraic Theory of Strong Power in Negatively

Connected Exchange Networks.” Journal of Mathematical Sociology 23:203-24.

Bonacich, Phillip. 2001. “The Evolution of Exchange Networks: A Simulation

Study.” Journal of Social Structure 2 (5).

Bonacich , Phillip. 2004. “Social Capital in Exchange Networks: A Simulation Study

of Network Evolution. Pp. 104-115 in Henk Flap and BeateVölker (Eds.), Creation and Returns of Social Capital: A New Research Program, London: Routledge.

Bonacich, Phillip and Elisa J. Bienenstock. 1995. When Rationality Fails: Unstable

Exchange Networks with Empty Cores. Rationality and Society 7:293-320. Bonacich, Phillip and Elisa J. Bienenstock. 1997. “Latent Classes in Exchange

Networks: Sets of Positions with Common Interests.” Journal of Mathematical Psychology 22:1-28.

27

Braun, Norman and Thomas Gautschi. 2000. “Who gets how much in which relation?

A non-cooperative bargaining approach to exchange networks.” Unpublished manuscript.

Burke, Peter J. 1997. “An Identity Model for Network Exchange.” American

Sociological Review 62:134-50.

Calvó-Armengol, Antoni and Rahmi Ilkiliç. 2004. “Pairwise Stability and Nash

Equilibria in Network Formation.” Unpublished manuscript.

Cook, Karen S. and Richard M. Emerson. 1978. “Power, Equity, and Commitment in

Exchange Networks.” American Sociological Review 43:721-39.

Cook, Karen S. and Toshio Yamagishi. 1992. “Power in Exchange Networks: A

Power-Dependence Formulation.” Social Networks 14:245-65.

Corominas-Bosch, Margarida. 2004. “Bargaining in a Network of Buyers and

Sellers.” Journal of Economic Theory 115:35-77.

Dutta, Bhaskar and Matthew O. Jackson. 2003. Networks and Groups. Berlin:

Springer.

Emanuelson, P. 2005. “Improving the Precision and Parsimony of Network Exchange

Theory: A Comparison of Three Network Exchange Models.” Contemporary Research in Social Psychology 10:149-65.

Emanuelson, P., and Willer, D. (2006). Testing Ten Theories. Unpublished

manuscript.

Emerson, Richard M. 1962. “Power-Dependence Relations.” American Sociological

Review 27:31-40.

Friedkin, Noah E. 1992. “An Expected Value Model of Social Power: Predictions for

Selected Exchange Networks.” Social Networks 14:213-29.

28

Friedkin, Noah E. 1993. “An Expected Value Model of Social Exchange Outcomes.”

Advances in Group Processes 10:163-93.

Friedkin, Noah E. 1995. “The Incidence of Exchange Networks.” Social Psychology

Quarterly 58:213-21.

Gilles, Robert P. and Sudipta Sarangi. 2004. The Role of Trust in Costly Network

Formation. Working paper.

Girard, C. Dudley and Casey Borch. 2002. “Predicting the Pattern of Exchange in

Economic Exchange Networks.” Unpublished manuscript.

Jackson, Matthew O. and Asher Wolinsky. 1996. “A Strategic Model of Social and

Economic Networks.” Journal of Economic Theory 71:44-74.

Kollock, Peter. 1994. “The Emergence of Exchange Structures: An Experimental

Study of Uncertainty, Commitment, and Trust.” American Journal of Sociology 100:313-45.

Leik, Robert K. 1991. “Strategic Timing in Network Processes.” Advances in Group

Processes 8:1-28.

Leik, Robert K. 1992. “New Directions for Network Exchange Theory: Strategic

Manipulation of Network Linkages.” Social Networks 14:309-24.

Markovsky, Barry, David Willer, and Travis Patton. 1988. “Power Relations in

Exchange Networks.” American Sociological Review 53:220-36.

Molm, Linda D. 1997. Coercive Power in Social Exchange. Cambridge: Cambridge

University Press.

Schmeidler, David. 1969. “The Nucleolus of a Characteristic Function Game.” SIAM

Journal on Applied Mathematics 17:1163-1170.

Skvoretz, John and David Willer. 1993. “Exclusion and Power: a test of four theories

of power in exchange networks.” American Sociological Review 58:801-18.

29

Van Assen, Marcel A. L. M. 2003. “Exchange Networks: An Analysis of All

Networks Up To Size 9.” Advances in Group Processes 20:67-103.

Van de Rijt, Arnout and Vincent Buskens. 2005. “A Nash Refinement for Myerson’s

Network Formation Game.” Unpublished manuscript.

Wasserman, S., & Faust, K. (1994). Social network analysis: methods and applications. Cambridge: Cambridge University Press.

Willer, David. 1999. Network Exchange Theory. New York: Greenwood.

Willer, David and Brent Simpson. 1999. “A New Method for Finding Power

Structures.” Pp. 270-284 in David Willer (Ed.), Network Exchange Theory, Westport, CT: Praeger Press.

Willer, Robb and David Willer. 2000. “Exploring Dynamic Networks: Hypotheses

and Conjectures.” Social Networks 22:251-72.

Yamaguchi, Kazuo. 1996. “Power in Networks of Substitutable and Complementary

Exchange Relations: A Rational-Choice Model and an Analysis of Power Centralization. American Sociological Review 61:308-32.

Yamaguchi, Kazuo. 2000. “Power in Mixed Exchange Networks: A Rational-Choice

Model.” Social Networks 22:93-121.

30

Number of PS Networks45403530Number25201510500.002.004.006.00Cost8.0010.0012.00

Figure 2: Number of PS networks as a function of cost

Average density as a function of cost0.900.800.70Average density0.600.500.400.300.200.100.000.00

1.002.003.004.005.006.00Cost7.008.009.0010.0011.0012.00

Figure 3: Average density of PS networks as a function of cost

31