Casey Borch, caborch@uab.edu
Department of Sociology
University of Alabama at Birmingham
C. Dudley Girard
Department of Computer Science
Shippensburg University
Abstract: Whereas much theoretical and empirical work concerning exchange networks examines the payoffs to actors in particular positions, a much smaller body of work focuses on exchange patterns (i.e., who exchanges with whom). The problem we address in this paper is that the existing methods to predict patterns of exchange are limited by computational cost to relatively small networks. We develop a computationally efficient method for locating and predicting patterns of exchange. The theory on which we draw argues that each actor’s resistance to unfavorable offers is based on relative position within the exchange network. Using experimental data we first show that the order of exchanges does affect payoffs as the network structure changes over time. We then attempt to predict the ordering of exchanges for a number of networks using three existing methods and one new method derived from our theory. As a test of the predicted orderings, we compare each method’s predictions for six exchange networks against experimental results. In general, the results suggest that our more parsimonious method performs quite well relative to the more computationally complex prediction methods.
The agendas of contemporary network exchange theories constitute a shift in focus from the ones that concerned early social exchange theorists such as Blau (1964) and Homans ([1961] 1974). The primary concern of these early theorists was the creation or transformation of social structures based on interpersonal activity. The move toward economic exchange networks, led by Emerson and colleagues (Emerson 1972a, 1972b; Stolte and Emerson 1977; Cook and Emerson 1978), inspired the development of several theoretical research programs that are mainly interested in predicting economic resource distributions in particular exchange networks.[1] One issue that most exchange theories do not explicitly address is the effect of exchange order. That is, as actors negotiate in the field and in certain experimental designs some actors reach agreement faster than others. This paper argues that the timing of exchange creates conditions under which an actor’s structural power may not be constant. In a number of networks, these power fluctuations lead some actors to increase or decrease in power over time. Thus, actors who were predicted to receive nearly all resources may, unexpectedly, receive much less.
For example, consider the effects of the timing of exchange on actors in a
fiveactor line (A_{1} – B_{1} – C – B_{2} – A_{2}).
In this case, let each actor have only one exchange to make, have full
information about the structure of the network, and have no other alternative
exchange partners. In addition, let the timing of exchange be nonsimultaneous.
Research has shown that the 5Line is a “semistrong” power network, in which
the Bs receive about 75% of the resource pool (or about 18 points out of a
24point resource pool) (Lucas et al. 2001). In this first example, let A_{2}
exchange with B_{2}, causing the A_{1} – B_{1} – C
subnetwork to emerge. Research has found this “3Line” network to be “strong”
power, in which the central position (in this case, B_{1}) receives
nearly all of the resources in a resource pool (or about 23 points out of a
24point resource pool) (e.g., Willer 1999). With full information, B_{1}
is able to recognize his/her newfound structural advantage and act accordingly.
Secondly, consider again the 5Line introduced above: it is important to note
that when C exchanges with B_{2} and the A_{1} – B_{1}
dyad emerges. In this case, B_{1}’s structural power is reduced from
highpower to equalpower and A_{1}’s power is increased from lowpower
to equalpower. Thus, A_{1} is predicted to realize his/her increased
power and decrease offers to B_{1}.
As a test of our assertions, data were gathered on the “line” networks displayed in Figure 1 and results of exchanges between the high power actors and the low power actors are presented in Table 1. (A discussion of the experimental setting under which these results were generated is provided below.) To save space, we omit some of the emergent subnetworks that occurred very infrequently (e.g., the 3Line subnetwork in the 6Line).
Figure 1: The Experimental Networks.
a) 4 Line 
b) 5 Line 
c) 6 Line 
d) 7 Line 
e) KITE 
f) 10person 
Table 1:
Points
Earned by NonExcludable Positions over Time.
Network  Points Earned 
4Line (N=14) 

First Exchange 
14.1 (1.57) 
Dyad (subnetwork) 
12.5 (1.51) 
5Line (N=12) 

First Exchange 
17.5 (3.10) 
3Line (subnetwork) 
18.8 (3.52) 
Dyad (subnetwork) 
13.9 (2.29) 
6Line (N=10) 

First Exchange 
12.4 (0.27) 
4Line (subnetwork) 
12.7 (0.94) 
Dyad (subnetwork) 
12.3 (0.43) 
7Line (N=12) 

First Exchange 
16.4 (2.10) 
4Line (subnetwork) 
18.3 (2.97) 
Dyad (subnetwork) 
13.1 (1.83) 
Note: Points are averaged across the final 10 rounds of negotiations. 

When compared, the data support our presumption that actors were able to deduce
changes in the overall network as exchanges occurred. Specifically, in the
5Line, the dyadic subnetwork caused a significant decrease in the payoffs to
the advantaged position (from 17.3 to 13.9); these values are significantly
different (t = 2.42, p < .05). Further evidence is provided by the 7Line
data. Since the 7Line is a “weak power” network, observed means from first
exchanges were predicted to be less than exchanges in emergent 3Lines, but
greater than exchanges in emergent dyads. This is precisely the order that
transpires (16.4 < 18.3 and 16.4 > 13.1, respectively). Although none of
the figures is significantly different, probably due to the small sample size,
nonetheless, the results are compelling.
In accordance with these results and following work by Friedkin (1995) and Skvoretz and Lovaglia (1995), our paper extends the scope of network exchange theories by devising a method that locates and predicts exchange patterns in any network structure. Simply stated, our theory, Exchange Pattern Theory, assumes that those who are in better bargaining positions will demand more resources and concede more slowly, compared to those in less favorable positions. This assumption implies that, on average, actors will reach agreements with those whose bargaining position is less than or equal to their own before reaching agreements with those who are in better bargaining positions. Therefore, an exchange pattern is evident when agreements in one part of the structure are consistently reached before agreements in another. In general, our method determines the order of exchanges within networks rather than the value of expected payoffs to individual actors.
When two actors who have high positional perseverance are connected to each other,
EPT assumes that the subsequent negotiations will be long and difficult to
resolve. However, when an actor who has high positional perseverance is
connected to an actor who has low positional perseverance the negotiations are
assumed to take less time. Likewise, when two actors with low positional
perseverance are connected to each other the negotiations are assumed to be
even faster still; since both actors are not expected to be especially
stubborn.[3]
Whereas positional perseverance values are actorspecific, “joint perseverance” values are relationspecific. Joint perseverance values are abstract measures of how quickly two actors will reach an agreement. The idea is this: if neither actor in an exchange relation takes a hard bargaining position, then those actors will reach agreement relatively quickly. In sum, joint perseverance values are relational level measures of both actors’ resistance to unfavorable offers. EPT assumes that relations with low joint perseverance values will consummate exchanges before relations with high joint perseverance values. However, if two or more relations’ joint perseverance values are equal, those relations may, or may not, exchange simultaneously. In this case, EPT assumes that the ordering will be randomly distributed with some having the probability of simultaneous exchange.
The second condition is an actor’s degree. Degree is defined as the number of other actors to whom an actor is connected. Beginning with Marsden (1983; see also Friedkin 1992; Skvoretz and Lovaglia 1995), degree (d_{i}) has been used as a predictor of power advantage. The basic assumption is that larger degree values are related to higher positional power. We adopt this assumption, but add that all connections may not be equally beneficial. This leads us to the third condition.
The third condition states that an actor’s perseverance is directly related to that actor’s perception of his or her partner’s perceived ability to be excluded. Termed Relational benefit, this is the extent to which an actor is structurally advantaged visàvis the other actors to whom he/she is connected. For example, consider two excludable actors (A and B), d_{A} = 3; d_{B} = 2. Following the traditional degree assumption, A is considered to have higher perseverance. However, a closer look reveals that A is connected to three nonexcludable actors, while B is connected to two excludable actors. Therefore, is A’s structural position actually more advantageous than B’s position? We argue that, since B is connected to only excludable actors, B should have higher perseverance. Therefore, similar to Granovetter’s (1973) “strength of weak ties” argument or Bonacich’s (1987) power centrality, we assert that it is not just an actor’s number of connections that is important, but also, the potential “benefit” of those connections.
The fourth and final condition is that an actor’s
perseverance will adjust over time as he or she is included or excluded (Thye
et al. 1997; Skvortez and Zhang 1997). Thus, EPT does not assume the same
relations will exchange first in every round of negotiation, but rather each
relation with equal joint perseverance values has a chance to occur first. The
order in which exchanges happen can potentially affect subsequent exchanges as
the network changes shape over time.[4]
We introduce three existing methods to compute patterns of exchange in economic exchange networks; of these methods, only Reciprocity was designed especially for this purpose. For the others, we use their underlying logic to compute patterns of exchange. We recognize the danger in using theories for their unintended purpose but, as will be seen, we make no assumptions that are not already implicit in the theories themselves.
Markovsky et al. (1993) used each actor’s “exchange seek likelihood” to
identify his/her structural power. The exchange seek likelihood procedure
(hereafter ESL) assigns each actor a likelihood of inclusion in an exchange,
such that actors more likely to be included are predicted to be more powerful
than actors less likely to be included. ESL calculates this likelihood by first
assuming that each actor randomly seeks exchange with all connected others.
[1] 
Where “prob” gives the probability of two actors exchanging, and “deg” gives the degree of an actor. Using equation 1, one can easily compute a predicted ordering of exchanges. For example, if an actor has only one connection, he/she seeks exchange with that partner at a rate of 1.0. If an actor has two partners, he/she seeks exchange with each 0.5 of the time and similarly for more connections. However, the actual likelihood that any pair of actors will exchange is determined by computing all possible exchange orderings and determining the likelihood each will occur by using equation 1.
Like ESL, Friedkin’s (1995) Expected Value Theory (EVT) implicitly predicts patterns of exchange. Specifically, EVT argues that the probability of an exchange at time t depends on the “value” (i.e., amount of resources) of an exchange at time t1. Taking each actor’s potential gain from exchange in a focal relation and offsetting it by the potential gain in exchange in his/her other relations constructs relational weights. The weights are then normalized to represent the probability of two actors exchanging along any one relation; the higher the relational weight the more likely that relation will be preferred over others. Using these probabilities, a dependency matrix is constructed and used to predict resource distributions for all relations. The resource distributions are then used to calculate new weighted relational values. This process iterates until equilibrium is reached. By rank ordering the weighted relations, one can predict which actors are more likely to exchange with which other actors. Thus, patterns of exchange are evident.
Skvoretz and Lovaglia (1995) argue that an actor’s perception of those to whom they are connected determines exchange frequencies. Their “Reciprocity” model contends that, “actors are more likely to seek exchange with partners who are more likely to reciprocate the attention” (1995: 167). They calculate a probability of reciprocation based on the number of partners an actor has (i.e., degree). Highdegree actors are those who have many partners, while lowdegree actors are those who have few partners. In their model, actors will seek exchange with lowdegree partners before highdegree partners. The following equation computes an actor’s likelihood to exchange with another actor:
[2] 
Where “deg” gives the degree for an actor and “exch” is the likelihood that actor x will exchange with actor z. Thus, if an actor A is connected to actors B and C, where actor B has degree 4 and actor C has degree 2. Then actor A will seek to exchange with actor B onethird of the time and twothirds of the time with actor C. By then taking actor B’s likelihood to seek exchange with actor A we can compute the likelihood of that exchange occurring by multiplying those two values together. This likelihood of exchanging is further modified by computing all possible exchange patterns and using equation 2 to determine the likelihood of them occurring. Data published by Skvoretz and Lovaglia (1995) support Reciprocity’s accuracy as an exchange pattern predictor across a variety of network shapes and sizes.
Unfortunately, ESL, EVT and Reciprocity are all computationally expensive (see Appendix A). An understanding of this restriction is found in the “time complexity” literature. Time complexity determines how long a specific task will take to compute. For example, the task of counting the number of actors in a network takes one timestep for each actor in the network, thus it would take n steps to complete, where n is the number of actors in the network. For the most part, computational costs are separated into two main groups: polynomial (P) and nonpolynomial (NP) (Cook 1971; Book 1994). Where those tasks that fall into the P group are computationally feasible and those tasks that fall into the NP group are not.[5] For example, a P algorithm might take n^{2} steps to complete while a NP algorithm might take 2^{n} steps to complete. At n=4, the P algorithm takes 4^{2} or 16 time steps to complete, while the NP algorithm takes 2^{4} or 16 time steps to complete. However, at n = 20, the P algorithm takes 20^{2} or 400 time steps to complete, while the NP algorithm takes 2^{20} or 1,048,576 steps to complete. Although simplified, this shows that the costs of NP algorithms increase at a much higher rate than those of P algorithms.
ESL, EVT and Reciprocity fall into the NP group. Thus, these methods can be applied to only small networks (roughly n < 12, but the exact maximum depends on the method and on the network configuration) without using heuristic techniques, such as Monte Carlo, to compute estimated values. Thus, as networks grow in complexity, more actors and connections exponentially increase the computational costs.
We explain the theory in two parts. Part 1 outlines EPM’s initial conditions, while Part 2 outlines variables that represent an actor’s resistance to unfavorable offers and discusses the process by which these variables are used to predict exchange patterns. It is important to note that all discussions to follow assume that actors can exchange maximally once and that resource pools are equal across all relations; however, EPM can be easily extended to allow for multiple exchanges per actor and/or unequal resource pools. We return to these extensions in the discussion section.
Based on the theory presented above, EPM includes three initial conditions. The first is an actor’s “excludability.” In EPM, excludability is a computed as a binary measure in that an actor is either “excludable” if exchange outcomes can be ordered in such a way as to leave him/her without an exchange partner, or “nonexcludable,” if no such ordering exists. For example, in each round of negotiation, the 5 Line network (A – B – C – D – E) has three possible exchange groupings. They are [A – B] [C – D], which excludes E, [B – C] [D – E], which excludes A, and [A – B] [D – E], which excludes C. Thus, actors A, C, and E are excludable, while actors B and D are nonexcludable.
A binary value for excludability can be computed for networks of any size using Optimal Seek Simplified (OSS; for a more technical description of this process and how it applies to larger networks, see Girard and Borch 2003). This method removes the need to examine all possible exchange outcomes by using only local information to determine excludability. Briefly, Optimal Seek Simplified (OSS) labels positions as excludable (E) or nonexcludable (I). To determine whether a node i is I or E, one need only find if there is some pattern of exchange by which i can be excluded by its neighbors. A neighbor is considered to be any node connected to the node in question. The algorithm for determining excludability is as follows (Girard and Borch 2003:231):
1) For any node n,
a) If no pair of n’s neighbors are tied to each other
and each neighbor of n has more than just n as a neighbor, then n is excludable.
Label n “E” and stop.
b) If any of n’s neighbors have only n as a neighbor,
then n is not excludable. Label n “I” and stop.
2) If a pattern of exchange is found by using n’s
neighbors as starting points in which n cannot exchange, then n is excludable.
Label n “E” and stop.
3) If no pattern of exchange is found to satisfy step
2, then n is not excludable. Label n “I” and stop.
By
incorporating this method of assigning excludability into EPM, we solve the NP
problem encountered by ESL, Reciprocity, and EVT.
The second initial condition is an actor’s degree. Degree is defined as the number of other actors to whom an actor is connected. For the third condition, EPM uses the excludability of each actor’s partners as a way to judge their relative relational benefit.
From the initial conditions, a proxy variable for an actor’s stubbornness to unfavorable resource distributions is easily derived. We term this variable “positional perseverance.” (A method for quantifying positional perseverance is given in the next section.) Positional perseverance is simply an actor’s resistance to accepting unfavorable offers from exchange partners, based on that actor’s initial structural conditions. Finally, based on EPT it is reasonable to assume that actors will change their positional perseverance over time as they are included in and/or excluded from exchanges. Thus, EPM does not assume that the same pattern of exchanges will occur in every round of negotiation. The predictions generated by EPM represent the most likely pattern given the set of structural conditions under which actors are exchanging.
There are two issues at hand for comparing our 0.5 value for excludable actors to other possible values. The first is how much does 0.5 differ from the “true” measure of excludability. In some networks, such as the 3Line, 0.5 is exactly correct. But, for other networks, such as the 5Line or the 7Line (A_{1} – B_{1} – C_{1} – D – C_{2} – B_{2} – A_{2}), the excludable nodes have a probability of exclusion that varies not only from 0.5 but also from each other. Comparing EVT probability values and those from EPM in the 7Line, we find that EVT predicts that the As are included at a rate of 0.76, the Cs at 0.71, and D at 0.95. For the 5Line, the excluded nodes are predicted by EVT to be included at rates of A = 0.71 and C = 0.58. Although EPM’s value of 0.5 seems to differ fairly substantially from the more precise predictions, the key is whether our arbitrary value of 0.5 significantly changes the predictions of first exchange visàvis other potential values. By running EPM on the 7Line with values for excludable nodes ranging from 0.2 to 0.85, we found that the predicted first exchange rate changed (i.e., increased or decreased) by an average of about 6.0% for the A – B relation. For the 5Line, there was no change in the first exchange rate. This sensitivity analysis suggests that our measure of 0.5 for excludable nodes will not significantly reduce the predictive power of the method (for more, readers can test this assertion themselves by using the EPM applet embedded in this paper).
For excludable actors, EPM assigns a relational weight of 0.75 to relations connecting them to other excludable actors and a weight of 0.5 to relations connecting them to nonexcludable actors. For nonexcludable actors, EPM assigns a weight of 1.0 to relations connecting them to excludable actors and a weight of 0.75 to relations connecting them to other nonexcludable actors. These values weight the benefit of the relation such that the preference order is maintained.
Some further explanation is required. Since the theoretical rationale behind relational benefit states that connections to lower power actors will be favored above all others, the assignment of 1.0 to these relations is easily derived from the theory. That is, the relation’s expected value is weighted at 100% of its potential payoff capacity. Secondly, 0.5 was chosen to be the lowest value. The logic is also straightforward. If one considers that excludable actors are competing with at least one other actor for exchange with a nonexcludable actor (i.e., in the A – B – C network, A is competing against C with each excludable at a rate of 0.5), then the maximum expected value of a given exchange is 50% of the total resource pool. Thus, we adopt this optimistic value although, in reality, it may be less. Finally, since a connection to an actor of equal power is less optimal than a connection to an actor of lesser power, but is preferred over a connection to an actor of higher power, the weighting should be some amount less than 1.0, but greater than 0.5; but how much lower or higher? The assignment of 0.75 reflects the midpoint between the upper bound of 1.0 and the lower of 0.5. The value of 0.75 represents moderately high relational benefit while still being markedly lower than that for connections to lesser power actors (1.0) and significantly higher than that for connections to higher power actors (0.5). Again, we realize that this is a somewhat arbitrary assignment of values that might sacrifice accuracy for computational efficiency. However, as will be shown, the loss of precision is minimal especially compared to the alternative of not being able to compute the exchange patterns of large networks.
We now address the issue of how much each component of our method contributes to the predictions of first exchange. First, excludability, if we turn this off, then every actor in the network will think it is in as strong a position as any other actor. The only thing that would affect perseverance would be degree (relational benefit is constant for all nodes in the network in this case). This is in essence what Reciprocity is doing and as such the effect of turning this condition off is displayed in Table 2 under the Reciprocity heading. Second, degree, if we turn this off, then each node’s perseverance will be based on looking at each individual relation by itself. This will have the effect that nodes with high degree will have the same level of perseverance with their neighbors as nodes with a degree of 1. Third, relational benefit, if we turn this off, we are in effect turning off excludability as well, so this is again the same as Reciprocity. Finally, perseverance, if we turn this off, then the exchange (or exchanges) with the lowest perseverance rates will be predicted to always exchange first. So, if A – B and D – E are predicted to exchange first in the 5 Line, then node C will never exchange. We know this is not true and EPM takes this into consideration.
1) For any actor (i) compute positional perseverance (S_{i}) as follows:
a. For each actor i in the network, using the definitions presented above, determine excludability (E_{i}), and then assign a value of 0.5 or 1.0 as appropriate.
b. To quantify relational benefit (R_{ij}), for the relation where actor i is connected to any actor j, use the definitions presented above and assign a value to the relation of 0.5, 0.75, or 1.0 as appropriate.
c. To incorporate degree (D_{i}) for actor i, sum R_{ij} across all of i’s relations:
[3] 
d. For each actor in the network, compute positional perseverance values (S_{i}) as follows:
[4] 
2) For any relation that connects actor i to actor j, compute joint perseverance values (J_{ij}) as follows:
[5] 
3) Joint perseverance values are turned into probabilities of exchange, P(o), via the following function:
[6] 
Where J_{F} = the joint perseverance value of the focal relation, and J_{1} … J_{n} = the joint perseverance values for all other relations in the network.
EPM’s prediction method begins by calculating P(o) values for all relations in the network (Steps 13). To compute the second and third exchanges for a specific first exchange, simply remove those actors and their relations from the network and repeat Steps 13. As such, it is possible to efficiently compute any ordering of exchanges (First, Second, Third, etc.).
The EPM Applet is available here.
Figure 2: Application of EPM to the 5Line.
We now apply EPM to the fiveactor line (Figure 2a). To calculate positional perseverance (S_{i}), Step 1a determines whether an actor is excludable or not and assigns each actor a value based on its excludability (Figure 2b):
E_{C} = 0.5; E_{B1,2 }= 1.0; E_{A1,2} = 0.5
Step 1b assigns relational benefit values (R_{i}) to each actor’s relations and Step 1c incorporates degree (D_{i}) by summing across relations using equation 3 (Figure 2c). Thus,
R_{C} = 0.5 + 0.5 = 1.0; R_{B1,2 }= 1.0 + 1.0 = 2.0; R_{A1,2} = 0.5
Step 1d uses equation 4 to compute each actor’s positional perseverance value (Figure 2d). Thus,
S_{C} = 0.5 x 1.0 = 0.5; S_{B1,2 }= 1.0 x 2.0 = 2.0; S_{A1,2} = 0.5 x 0.5 = 0.25
Step 2 uses equation 5 to compute each relation’s joint perseverance value (Figure 2e). Thus,
J_{A1B1} = 0.25 x 2.0 = 0.5; J_{B1C} = 2.0 x 0.5 = 1.0
J_{CB2} = 2.0 x 0.5 = 1.0; J_{B2A2} = 0.25 x 2.0 = 0.5
In Step 3, equation 6 turns each relation’s joint perseverance values into probabilities of exchange, P(o), where the probability of exchange is inversely proportional to the joint perseverance value (Figure 2f). Thus,
Therefore, according to EPM, the [B – A] relations are predicted to exchange first at a rate of 0.333 and the [B – C] relations are predicted to exchange first at a rate of 0.167 (Figure 2g). Below, Table 2 shows that observed first exchange rates in the 5Line adhere closely to those predicted by EPM.
The data come from experiments conducted using ExNet 1.0+, which is a webbased system with full information and nonsimultaneous exchange (Willer and Skvoretz 1997a & b; Willer et al. 2002). ExNet 1.0+ has an intuitive display, which allows participants to easily recognize changes in the network as exchanges take place. Thus, when an exchange occurs in the network its structural effects can be noticed and understood by all participants. Participants can adjust their demands from the minimum amount to the maximum amount during each round. Additionally, participants can send as many offers as time will allow during each round. In ExNet 1.0+, exchanges are completed in a threestep process; offers are sent and either accepted or counter offers are sent. Accepted offers become completed exchanges when the initial sender of the offer confirms the acceptance. Importantly, ExNet 1.0+ allows all participants to know when they have been excluded from exchange, it allows all participants to know the amount of resources earned from their own exchanges, and all participants know whether they are asking for more or less resources than they did in the previous round of negotiations.
At the conclusion of the experiments, all participants were paid for points earned from exchanges. Also, each round was completed when all exchanges possible for that particular structure were completed, or, failing that, when the allotted time had expired. For the purposes of our analyses the relations in which exchange occurred per round was the main outcome of interest.
Table 2 compares some observed first exchange rates from six different networks to predicted probabilities from the four theoretical methods introduced above. A cursory glance at the results suggests that all of the methods do a respectable job predicting which relations will exchange first most often. However, a closer look reveals some differences in the predictive capabilities of the four methods. An explanation of the predicted probabilities and observed exchange rates is important here. Of the relations that could exchange, the predictions represent the predicted likelihoods of exchanging first.
For example, consider the ESL predictions for the
7Line (column 2 of Table 3). They mean that the A – B relation is predicted to
exchange first about 48% of the time; the B – C relation is predicted to exchange
first about 27% of the time; and, the C – D relation is predicted to exchange
first about 25% of the time. These predicted probabilities of first exchange
can be compared to actual exchange rates from experimental data. The seventh
column of Table 2 displays the observed firstexchange rates. That is, for the
7Line, the experimental results show that actors in the A – B relations
exchanged first at a rate of .483 or about 48% of the time; while people in the
C – D relations exchanged first about 36% of the time; and, actors in the B – C
relations exchanged first about 16% of the time.
The key point of this demonstration is how closely each method’s predictions come to the observed exchange rates. Or, better yet, do the predictions fit the pattern of first exchanges seen in the observed data? In the aforementioned example, ESL correctly predicted that the A – B relations would exchange first most often, but failed to predict that the C – D relations would the next most likely relations to exchange first. Instead, ESL predicted that the B – C relations were more likely to exchange first, before the C – D relations (.270 > .250). Thus, ESL did not correctly predict the pattern of first exchanges in the 7Line. The predictions from Reciprocity, EVT, and EPM all closely matched the observed firstexchange rates, with EVT and EPM doing an especially good job predicting the 7Line.
Turning to the 6Line, the observed firstexchange rates were 63% in the A – B relations, 33.5% in the C – C relations, and 3.5% in the B – C relations. While none of the methods came close to predicting the rather small first exchange rate in the B – C relations (3.5%), all of the methods correctly predicted that the A – B relations would be the most likely to exchange first. However, only EVT and EPM predicted that first exchanges should occur more often in the C – C relations than in the B – C relations with EPM coming closest to predicting the actual pattern of first exchanges in the 6Line.
The results of the 5Line, 4Line, and 10person networks all closely matched predictions by all four methods, with Reciprocity coming closest in the 5Line, EVT doing the best in the 4Line, and EVT and EPM doing about equally well in the 10person network. While encouraging, the KITE network presented a problem for EPM. Whereas the other methods correctly predicted that the A – A relations should exchange before the A – B relations, EPM predicted that both sets of relations were equally likely to exchange first. This prediction was far off the 61% firstexchange rate in the A – A relations observed in the KITE network. Again, EVT provided the best predictions for the KITE. (We return to EPM’s problems predicting the KITE below.)
To sum up the results, only EVT correctly predicted the likelihood order of firstexchange rates across all six networks reported in Table 2. With the exception of the KITE, EPM correctly predicted the likelihood rankings of firstexchange rates in five of the six networks. ESL and Reciprocity got four of the six correct, failing to accurately predict likelihood rankings in the 6 and 7Lines. Considering the main goal of this paper, to show that EPM is a computationally efficient but still relatively accurate prediction method for first exchanges, our results suggest that it indeed does a good job of predicting relative to the more computationally expensive methods discussed here. Therefore, we can conclude with some confidence that EPM provides plausible firstexchange predictions across a variety of networks of different sizes and configurations.
However, the KITE network proved to be problematic. One way to address EPM’s failings in predicting exchanges in the KITE is to compare it to EVT, which correctly predicted firstexchange rates for the KITE. First, EVT uses precise values for earnings (used to compute what EPM calls “relational benefit”) and for excludability (used to compute what EPM calls “positional perseverance”). However, if we plug EVT values into EPM and calculate first exchange probabilities, the EPM predictions get worse. This is because excludable actors who perceive their power to be high will probably be excluded more often and likely earn less (e.g., C in the 5Line, B in the Kite, B in the 7 Line). So, using EVT’s predicted earnings and excludability values actually gives worse EPM predictions. Moreover, EVT uses earnings to weight the benefit of each relation, but relative to the expected earnings of all actors’ relations. So, an actor with one relation will always weight its benefit as a 1.0, while an actor with two relations in which he/she is expected to earn the same amount will be weighted at 0.5. This means that, for EVT and regardless of degree, all actors’ relational benefit is always 1.0. This then begs the question: How does EVT preserve the idea of overall relational benefit used by EPM? It computes the likelihood of an exchange occurring along a relation by summing its likelihood across all possible exchange outcomes. Thus, the more often that exchange occurs, the higher its relational benefit. However, this means that one must not only include the focal relation in computing relational benefit, but also consider the second, third, and higher exchanges. Interestingly, incorporating just this aspect of EVT into EPM improves EPM’s predictions for the KITE greatly such that they are on par with EVT, but at the expense of computational parsimony.
Notes: The emergent subnetwork is in parentheses under the “second exchange” column. The Ns for the observed results are smaller than in Table 2 because we counted only those times in which the most likely first exchange occurred. In the 4Line, the proportion of exchanges in the dyadic subnetwork was less than 1.0 because 3 times out of 165 they failed to reach agreement. In the KITE, the relations in the triangle subnetwork all have equal chance of exchanging (.333), but there are two A – B relations so we listed them as (.333 + .333) = .666.
Table 3 presents second exchange predictions from the four methods and some observed results. The data show that exchanges in the emergent subnetworks follow a pattern very similar to that of first exchanges in like networks. Specifically, in the 7Line when one of the A – B relations exchange first, the second exchange occurs between C – D or A – B, which are the end relations in the emergent 5Line. This occurred about 70% of the time.[6] This finding is important to our theory, because it suggests that the EPM method can be iterated as the overall network decays over time into subnetworks. That is, actors treat the emergent subnetworks “as if” they are in new networks and bargaining and negotiations are modified according to their new structural position. This point helps to explain the findings in Table 1 (i.e., the changes in payoffs are due to the emergent subnetworks).
Interestingly, the results in Table 3 suggest that the relations predicted to exchange first in the overall network seemed to skew the results of the second exchanges toward that relation in the emergent subnetwork. For example, in the 5Line, the A – B relation was predicted to exchange first in the complete network, while the A – B and B – C relations are equiprobable in the emergent 3Line subnetwork. The results, however, were slanted toward the other A – B relation, with that exchange happening second about 57% of the time. We surmise that negotiations were further along in the A – B relations and that might explain why agreements were reached more quickly. A second example is seen in the observed results from the KITE network. In it, the A – A relation exchanges first in the overall network at a rate of about 61%. However, in the emergent triangle subnetwork, when all three relations have an equiprobable chance of occurring second, the A – A relation exchanged about 45% of the time. This finding may lend further support to the notion suggested by Markovsky et al. (1993) that actors in the central position of the KITE tend to overestimate the strength of their structural position.
In sum, the results in Table 3 suggest that any network, no matter how large or complex, can be examined by locating first exchanges and then focusing on the emergent subnetworks and analyzing them accordingly. We should note that when the most likely first exchange did not occur, the emergent subnetworks still behaved as if they were “standalone” networks. That is, for example when C and D exchanged in the 7Line, the exchange in the resulting two subnetworks (a dyad and a 3Line) followed the patterns predicted by EPM; as did the emergent 3Lines in the 10person network when A – B exchanged. In Table 3, we decided to show the results when the “most likely” first exchanges occurred because of the more complex and interesting subnetworks and because these subnetworks emerged most often in our data.
Considering implications, EPM can be useful in studying dynamic networks. The study of these networks is relatively new but several scholars have suggested that, in order for network exchange theory to grow, exchange networks must be conceptualized as dynamic systems (Walker et al. 2000). The area of dynamic networks considers the conditions under which actors will choose to add or subtract network ties and the results of these decisions (Leik 1992; Doreian and Stokman 1997; Willer and Willer 2000). In this work, actors must be able to recognize the power of their structural position and act accordingly. It is reasonable to assume that any algorithm to examine dynamic networks should consider actors’ relative abilities to resist unfavorable offers. Additionally, since these networks often are large and complex, current methods of predicting patterns of exchange will probably not apply. Thus, EPM may be an important tool in the study of dynamic networks.
On extensions, although the explanation of the theory included several implicit scope conditions, two can be easily removed. These include the restrictions of one exchange per actor and equal resource pools in all relations. In both cases, to remove the restrictions, perseverance values must be modified. Changing the number of exchanges available to one actor affects the excludability of other actors in the network (Markovsky et al. 1988). In addition, multiple exchanges can cause an actor to be part of multiple power components (i.e., “domains”) simultaneously (Markovsky et al. 1988). By utilizing Markovsky et al.’s (1988) work, multiple exchanges can be accounted for and incorporated in perseverance values. However, we leave the specifics of this extension for future work.
Considering unequal resource pools, this condition serves to lower the joint perseverance values of the relations in which the larger resource pools are located. Consider the following network, [A – 25 – B – 40 – C]. In this network, it is reasonable to assume that the joint perseverance value for the [B – C] relation will be lower than that for the A – B relation. That is, B will probably exchange more frequently with C than with A, because, due to the larger resource pool, C can easily outbid A. Again, we leave this extension for future work.
On limitations, further study is needed to address several potential problems associated with the theory’s assumptions. First, is degree’s influence linear? The assumption of linearity is problematic because it is likely that the affect of degree has an asymptotical quality. That is, after a certain point, the addition of more partners may not increase an actor’s perseverance as much as it did previously. However, it is reasonable to assume that the number of partners will be much larger than that of the networks tested in this paper; therefore, the impact on the current predictions will be quite small.
Secondly, does the amount of information available in exchange settings affect perseverance? In its present form, EPM does not actively control for the influence of information. It is reasonable to assume that the more information an actor has about the network the more likely he/she will be able to react to changes in that network thus influencing perseverance values. This is not problematic if all actors’ perseverance rates increase or decrease uniformly, however, if actors’ perseverance rates show a more complex pattern of change (i.e., nonexcludable actors’ rates change only slightly while excludable actors’ rates change drastically) we may have to consider the way in which the values are computed relative to the amount of information available to actors.
Finally, in this paper we have argued that EPM can be applied to large complex networks, but our tests only involved small, simple ones (up to a 10person network). We thought it more important to establish that the heuristic method works as well as more complex methods in small networks before applying it to large ones. Thus, we were limited to using networks to which those methods applied. Future work will explore larger, more complex networks. In short, we hope that our work will help usher in the study of larger, more complex networks.
Blau, Peter. 1964. Exchange and Power in Social Life. New York: Wiley Publishing Co.
Bonacich, Phillip. 1987. “Power and Centrality: A Family of Measures” American Journal of Sociology 92: 11701182.
Bonacich, Phillip and Noah. 1998. “Unequally Valued Exchange Relations.” Social Psychology Quarterly 61: 16071.
Book, Ronald. 1994. “Relativizations of the P=? NP and Other Problems: Developments in Structural Complexity Theory.” Society for Industrial and Applied Mathematics Review 36: 157175.
Burke, Peter. 1997. “An Identity Model for Network Exchange.” American Sociological Review 62: 134150.
Cheney, Ward and David Kincaid. 1985. Numerical Mathematics and Computing, 2^{nd} Edition. Pacific Grove, CA: Brooks/Cole Publishing Co.
Cook, Karen S. and Richard M. Emerson. 1978. “Power, Equity and Commitment in Exchange Networks.” American Sociological Review 43: 721739.
Cook, Karen S., Richard M. Emerson, Mary R. Gillmore, and Toshio Yamagishi. 1983. “The Distribution of Power in Exchange Networks: Theory and Experimental Results.” American Journal of Sociology 89: 275305.
Cook, Karen S. and Mary R. Gillmore. 1984. “Power, Dependence, and Coalitions.” Pages 2758 in E. J. Lawler, B. Markovsky, K. Heimer, and J. O’Brien (eds.). Advances in Group Processes, vol. 1. Greenwich, CT: JAI Press.
Cook, S. 1971. “The Complexity of TheoremProving Procedures.”Proc. 3^{rd} ACM Symp. Theory of Computing: 151158.
Dahl, Robert. 1957. “The Concept of Power.” Behavioral Science 2: 201218.
Doreian, Patrick
and Frans N.
Emerson, Richard M. 1972a. “Exchange Theory, Part I: A Psychological Basis for Social Exchange.” Pages 3857 in J. Berger, M. Zelditch, Jr., and B. Anderson (eds.). Sociological Theories in Progress, vol. 2. Boston: Houghton Mifflin Co.
______ . 1972b. “Exchange Theory Part II: Exchange Relations and Network Structures.” Pages 5987 in J. Berger, M. Zelditch, Jr., and B. Anderson (eds.). Sociological Theories in Progress, vol. 2. Boston: Houghton Mifflin Co.
Friedkin, Noah E. 1992. “An Expected Value Model of Social Power: Predictions for Selected Exchange Networks.” Social Networks 14: 213230.
______ . 1993. “An Expected Value Model of Social Exchange Outcomes.” Pages 163193 in E. J. Lawler, B. Markovsky, K. Heimer, and J. O’Brien (eds.). Advances in Group Processes, vol. 10. Greenwich, CT: JAI Press.
______ . 1995. “The Incidence of Exchange Networks.” Social Psychology Quarterly 58: 213222.
Girard, Dudley and Casey Borch. 2003. “Optimal Seek Simplified.” Current Research in Social Psychology 8: 225241.
Granovetter, Mark. 1973. “The Strength of Weak Ties.” American Journal of Sociology 78: 13601380.
Hennessy, John L. and David A. Patterson. 1990. Computer Architecture: A Quantitative Approach. San Mateo, CA: Morgan Kaufman Publishers, Inc.
Homans, George. [1961] 1974. Social Behavior its Elementary Forms, Revised Edition. New York: Harcourt, Brace & Jovanovich.
Kozen, Dexter C. 1992. The Design and Analysis of Algorithms. New York: SpringerVerlag.
Lawler, Edward J. and Jeongkoo Yoon. 1993. “Power and the Emergence of Commitment Behavior in Negotiated Exchange.” American Sociological Review 58: 465481.
______ . 1996. “Commitment in Exchange Relations: Test of a Theory of Relational Cohesion.” American Sociological Review 61: 89108.
______ . 1998. “Network Structure and Emotion in Exchange Relations.” American Sociological Review 63: 871894.
Leik, Robert K. 1992. “New Directions for Network Exchange Theory: Strategic Manipulation of Network Linkages.” Social Networks 14: 309323.
Lovaglia, Michael, John Skvoretz, David Willer, and Barry Markovsky. 1995. “Negotiated Outcomes in Social Exchange Networks.” Social Forces 74: 123155.
Lucas, Jeffrey W., C. Wesley Younts, Michael Lovaglia, and Barry Markovsky. 2001. “Lines of Power in Exchange Networks.” Social Forces 80: 185214.
Lukes, Steven. 1974. Power: A Radical View. London, UK: Macmillan.
Markovsky, Barry, David Willer, and Travis Patton. 1988. “Power Relations in Exchange Networks.” American Sociological Review 53: 220236.
Markovsky, Barry, John Skvoretz, David Willer, Michael Lovaglia, and Jeffery Erger. 1993. “The Seeds of Weak Power: An Extension of Network Exchange Theory.” American Sociological Review 58: 197209.
Marsden, Peter V. 1983. “Restricted Access in Networks and Models of Power.” American Journal of Sociology 88: 686717.
Molm, Linda D. 1990. “The Dynamics of Power in Social Exchange.” American Sociological Review 55: 427447.
Molm, Linda D., Gretchen Peterson, and Nobuyuki Takahashi. 1999. “Power in Negotiated and Reciprocal Exchange.” American Sociological Review 64: 876890.
______ . 2001. “The Value of Exchange.” Social Forces 80: 159185.
Mooney, Christopher Z. 1997. Monte Carlo Simulation. Thousand Oaks, CA: Sage.
Patton, Travis and David Willer. 1990. “Connection and Power in Centralized Exchange Networks.” Journal of Mathematical Sociology 16: 3149.
Sedgwick, Robert. 1992. Algorithms in C++. Reading, MA: AddisonWesley.
Simpson, Brent and David Willer. 1999. “A New Method for Finding Power Structures.” Pages 270284 in D. Willer. Network Exchange Theory. Westport, CT: Praeger.
Simpson, Brent and Michael W. Macy. 2001. “Collective Action and Power Inequality: Coalitions in Exchange Networks.” Social Psychology Quarterly 64: 88100.
Skvoretz, John and David Willer. 1991. “Power in Exchange Networks: Setting and Structure Variations.” Social Psychology Quarterly 54: 224238.
______ . 1993. “Exclusion and Power: A Test of Four Theories of Power in Exchange Networks.” American Sociological Review 58: 80118.
Skvoretz, John and Michael J. Lovaglia. 1995. “Who Exchanges with Whom: Structural Determinants of Exchange Frequency in Negotiated Exchange Networks.” Social Psychology Quarterly 58: 163177.
Skvoretz, John and Pidi Zhang. 1997. “Actors’ Responses to Outcomes in Exchange Networks: The Process of Power Development.” Sociological Perspectives 40: 183197.
SPEC Benchmarks. 2002. Available: http://www.specbench.org/osg/cpu2000/results/cpu2000.html. Standard Performance Evaluation Corporation.
Stolte, John and Richard Emerson. 1977. “Structural Inequality: Position and Power in Exchange Structures.” Pages 117138 in R. Hamblin and J. Kunkel (eds.). Behavioral Theory in Sociology. New Brunswick, NJ: Transaction Books.
Thye, Shane, Michael Lovaglia, and Barry Markovsky. 1997. “Responses to Social Exchange and Social Exclusion in Networks.” Social Forces 75: 10311049.
van Assen, M.A.L.M. and Dudley Girard. 2001. “Bargaining in Exchange Networks.” Pages 101135 in M. van Assen (ed.), Essays on Actor Models in Exchange Networks and Social Dilemmas. Groningen, Netherlands: RUG.
Walker, Henry A., Shane R. Thye, Brent Simpson, Michael J. Lovaglia, David Willer, Barry Markovsky. 2000. “Network Exchange Theory: Recent Developments and New Directions.” Social Psychology Quarterly 63: 323337.
Willer, David. 1987. Theory and the Experimental Investigation of Social Structures. New York: Gordon and Breach.
______ (ed.). 1999. Network Exchange Theory. Westport, CT: Praeger.
Willer, David and John Skvoretz. 1997a. “Games and Structures.” Rationality and Society 9: 535.
______ . 1997b. “Network Connection and Exchange Ratios: Theory, Predictions and Experimental Tests.” Pages 199234 in B. Markovsky, M. Lovaglia, and L. Troyer (eds.). Advances in Group Process, vol. 14. Greenwich, CT: JAI Press.
Willer, David, Casey Borch, and Robb Willer. 2002. “Building a Model for Solidarity and Cohesion Using Three Theories.” Group Cohesion, Trust and Solidarity 19: 67107.
Willer, Robb and David Willer. 2000. “Exploring Dynamic Networks: Hypotheses and Conjectures.” Social Networks 22: 251272.
Zelditch, Morris Jr. 1992. “Interpersonal Power.” Pages 9941001 in E. F. Borgatta and M. L. Borgatta (eds.). Encyclopedia of Sociology. New York: Macmillan.
The actual cost for ESL, EVT, and Reciprocity can be visualized as follows: Place all the possible exchange pairs that can occur into a bag. For example, for the 5Line, the following relations A – B, B – C, C – D, and D – E are placed into the bag. Now for each exchange pulled out (A – B for example), remove all the exchanges that can no longer happen (e.g., B – C). So, for the 5Line, there are four possible start points. For each of those start points, repeat the process. For example, in the case of A – B there are two possible outcomes left in the bag (C – D or D – E). The process is repeated for all possible start points. This reveals that there are six total outcomes for the 5Line network, which is computationally feasible (5actor network, only 6 possible exchange outcomes). The problem is that this cost does not scale linearly to larger networks.
Now consider a 50actor network with an average degree of 3. For a network of this size there are 75 relations and a maximum of 25 exchanges that can occur. We can compute a quick upper bound by solving an equation used to compute the total number of permutations where order is important: 75!/(7525)! = 8.16*10^{44}. However, for every exchange that is completed there will be four additional exchanges that can no longer be completed. Using the method presented in the previous paragraph this means there are 75 possible exchange relations initially in the bag. For each of those 75 relations that are chosen (assuming a fairly even distribution of relations) remove four other exchange relations from the bag (two for each node). Thus, for each first exchange there are 70 relations still to choose from. Assuming, for simplicity, that the reduced networks all have about the same degree as the initial network then continuing this reasoning for every stage reduces the number of choices in the bag by five. Thus, the total possible number of outcomes generated would be: 75*70*65*…*10*5, or 3.99*10^{22}. It is useful to note that the excludability equation involves inspecting each node and its ties and its neighbors’ ties, which total no more than 50*3^{9} = 2.22*10^{13}. The advantage of EPM is that, in this example, the 3^{9} factor stays constant as size increases from 50 to 500 nodes, say, but in the other methods one would have to compute 750*745* … *5 outcomes, which is clearly an NP situation.
The actual cost can vary depending on how the actual network is connected. For example, a network with a large branch subnetwork connected to a fully connected subnetwork can have the same average degree as the above network, but the cost will be different as any exchange in the large branch network will pull that whole set of exchanges out of the bag and any exchanges in the fully connected network will have a similar effect. So, its cost will be significantly lower than the exemplar network in that the number of choices might go down by 10 rather than 5. This would give a total cost of 1.3*10^{27}, which is still not cheap. To get an idea of the scale of these numbers, the fastest computer in the world, NEC’s EarthSimulator, can execute about 35 trillion (3.5*10^{13}) operations in 1 second [SOURCE: http: //www.es.jamstec.go.jp/esc/eng/ES/performance.html].
*Note: The authors thank Gordon Gauchat, Barry Markovsky, Brent Simpson, Shane Thye, and David Willer for helpful comments on previous drafts of this paper. The authors also thank Noah Friedkin, Jeffrey Lucas, John Skvoretz, and David Willer for granting us access to their archived data. Direct correspondence to Casey Borch, caborch@uab.edu, Department of Sociology, University of Alabama at Birmingham, HHB 460D, Birmingham, AL 35210.
[1] See Cook, Emerson, Gillmore, and Yamagishi (1983); Cook and Gillmore (1984); Willer (1987, 1999); Markovsky, Willer, and Patton (1988); Patton and Willer (1990); Molm (1990); Skvoretz and Willer (1991, 1993); Bienenstock and Bonacich (1993); Lawler and Yoon (1993, 1996, 1998); Friedkin (1993, 1995); Lovaglia, Skvoretz, Willer, and Markovsky (1995); Willer and Skvoretz (1997a, 1997b); Molm, Peterson, and Takahashi (1999); Simpson and Macy (2001); Lucas, Younts, Lovaglia, and Markovsky (2001); Willer, Borch, and Willer (2002).
[2] Additionally, it could be argued that those who have high positional perseverance can afford to take more risks when negotiating with their partners. However, due to scope limitations, we leave the theorizing of risk to future research.
[3] For EPT, “time” is an abstract term, so it may take many forms (i.e., minutes, hours, rounds, etc.).
[4] The obvious caveat is when exchanges happen at the same time.
[5] This statement is a very simple explanation of P and NP; readers are advised to consult Cook (1971) and Book (1994) for more information.
[6] “Second exchanges” were defined as those exchanges occurring at least 5 seconds after the first exchange. After surveying hundreds of negotiation data, we noticed that participants needed (on average) at least 5 seconds to be able to recognize their new structural position and modify their offers. Those occurring in less than 5 seconds were considered “simultaneous” first exchanges.