JoSS Article: Volume 10
Predicting Patterns of Exchange in Economic Exchange Networks*
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.
1. Introduction
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
five-actor line (A1 – B1 – C – B2 – A2).
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 non-simultaneous.
Research has shown that the 5-Line is a “semi-strong” power network, in which
the Bs receive about 75% of the resource pool (or about 18 points out of a
24-point resource pool) (Lucas et al. 2001). In this first example, let A2
exchange with B2, causing the A1 – B1 – C
sub-network to emerge. Research has found this “3-Line” network to be “strong”
power, in which the central position (in this case, B1) receives
nearly all of the resources in a resource pool (or about 23 points out of a
24-point resource pool) (e.g., Willer 1999). With full information, B1
is able to recognize his/her newfound structural advantage and act accordingly.
Secondly, consider again the 5-Line introduced above: it is important to note
that when C exchanges with B2 and the A1 – B1
dyad emerges. In this case, B1’s structural power is reduced from
high-power to equal-power and A1’s power is increased from low-power
to equal-power. Thus, A1 is predicted to realize his/her increased
power and decrease offers to B1.
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 sub-networks that occurred very infrequently (e.g., the 3-Line sub-network in the 6-Line).
Figure 1: The Experimental Networks.
a) 4 Line  |
b) 5 Line |
c) 6 Line |
d) 7 Line |
e) KITE |
f) 10-person |
Table 1:
Points
Earned by Non-Excludable Positions over Time.
| Network | Points Earned |
|
4-Line (N=14) |
|
|
First Exchange |
14.1 (1.57) |
|
Dyad (sub-network) |
12.5 (1.51) |
|
5-Line (N=12) |
|
|
First Exchange |
17.5 (3.10) |
|
3-Line (sub-network) |
18.8 (3.52) |
|
Dyad (sub-network) |
13.9 (2.29) |
|
6-Line (N=10) |
|
|
First Exchange |
12.4 (0.27) |
|
4-Line (sub-network) |
12.7 (0.94) |
|
Dyad (sub-network) |
12.3 (0.43) |
|
7-Line (N=12) |
|
|
First Exchange |
16.4 (2.10) |
|
4-Line (sub-network) |
18.3 (2.97) |
|
Dyad (sub-network) |
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
5-Line, the dyadic sub-network 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 7-Line
data. Since the 7-Line is a “weak power” network, observed means from first
exchanges were predicted to be less than exchanges in emergent 3-Lines, 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.
2. Exchange Pattern Theory
Exchange Pattern Theory (EPT) uses a network’s structure and exchange conditions to determine the order in which actors will exchange. From this information, an actor’s “stubbornness” to unfavorable resource distributions can be derived. We term this “positional perseverance.” Positional perseverance is defined as an actor’s resistance to accepting unfavorable offers from exchange partners based on that actor’s initial structural conditions. For example, if an actor’s positional perseverance is high, then that actor is expected to be a “hard bargainer” who is not easily pushed into accepting unfavorable resource divisions (Skvoretz and Zhang 1997).[2]
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 actor-specific, “joint perseverance” values are relation-specific. 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.
2.1 Four Conditions to Predict Ordering
Four conditions, which are common to all actors in exchange networks, can determine an actor’s willingness to exchange. The first is an actor’s perseverance, which is inversely related that actor’s “excludability.” Excludability is the probability that an actor will not be included in any agreements that are reached. Studies have shown (e.g., Thye, Lovaglia, and Markovsky 1997) that excludability strongly affects an actor’s willingness to concede resources.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 (di) 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), dA = 3; dB = 2. Following the traditional degree assumption, A is considered to have higher perseverance. However, a closer look reveals that A is connected to three non-excludable 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]
3. Existing Methods to Compute Exchange Patterns
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 t-1. 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). High-degree actors are those who have many partners, while low-degree actors are those who have few partners. In their model, actors will seek exchange with low-degree partners before high-degree 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 one-third of the time and two-thirds 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 time-step 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 non-polynomial (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 n2 steps to complete while a NP algorithm might take 2n steps to complete. At n=4, the P algorithm takes 42 or 16 time steps to complete, while the NP algorithm takes 24 or 16 time steps to complete. However, at n = 20, the P algorithm takes 202 or 400 time steps to complete, while the NP algorithm takes 220 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.
4. The Exchange Pattern Method
In this section, we present a method to determine the pattern of exchanges in economic exchange networks. Recall that “exchange patterns” are defined as the ordering of exchanges in exchange networks through time. As stated above, currently few theories of network exchange predict, or even consider, exchange patterns. Importantly, those that do are computationally expensive and thus are restricted to small networks (e.g., ESL, EVT and Reciprocity). The exchange pattern method (EPM) presented in this section reduces the complexity necessary to compute predictions and thus is applicable to networks of any size. EPM gains its parsimony by treating the excludability of a node as a binary measure; hence, a node is either excludible or it is not. We then apply heuristically-derived scalar values to these non-scalar representations of excludability.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
“non-excludable,” 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 non-excludable.
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 non-excludable (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 3-Line, 0.5 is exactly
correct. But, for other networks, such as the 5-Line or the 7-Line (A1
– B1 – C1 – D – C2 – B2 – A2),
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 7-Line, 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 5-Line, 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 7-Line 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 5-Line,
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 non-excludable actors. For
non-excludable 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
non-excludable 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 non-excludable 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 (Si)
as follows: a. For each actor i in the network, using the definitions presented
above, determine excludability (Ei), and then assign a value
of 0.5 or 1.0 as appropriate. b. To quantify relational benefit (Rij), 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 (Di) for actor i, sum Rij
across all of i’s relations: [3] d. For each actor in the network, compute positional perseverance values (Si)
as follows: [4]4.1 Initial Conditions
5. Predicting Patterns of Exchange
5.1 Measuring Exclusion
For the sake of parsimony, EPM takes a binary
approach to operationalizing excludability. Unlike previous measures, which
sought to determine the exact rate at which an actor is excluded (e.g., ESL),
we assign one value for actors who are excludable (0.5) and another for those
who are non-excludable (1.0). The non-excludable value of 1.0 is self-evident
(i.e., they are included in an exchange 100% of the time), but the excludable
value of 0.5 requires further explanation. To determine this value we simply
took the best (1.0) possible structural position and added it to the worst
(0.0) and divided by two. However, we also provide comparison values using 0.25
and 0.75 to show how little the actual value matters so long as it is a reasonable
value below 1.0 and above 0.0. As
expected, this approach sacrifices some degree of accuracy for computational
efficiency.
5.2 Measuring Relational Benefit
Again,
for the sake of parsimony, EPM takes a heuristic approach to operationalizing
relational benefit. If known, it is reasonable to assume that rational actors
prefer exchange with partners of lesser power than to exchange with partners of
equal or greater power. These preferences can be rank ordered: lesser power
partners > equal power partners > higher power partners.
5.3 EPM’s Prediction Method
Formally, the prediction method can be expressed in
the following three steps:
2) For any relation that connects actor i to actor j, compute joint perseverance values (Jij) as follows:
 |
[5] |
3) Joint perseverance values are turned into probabilities of exchange, P(o), via the following function:
 |
[6] |
Where JF = the joint perseverance value of the focal relation, and J1 … Jn = 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 1-3). 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 1-3. As such, it is possible to efficiently compute any ordering of exchanges (First, Second, Third, etc.).
The EPM Applet is available here.
5.4 An Application
Figure 2: Application of EPM to the 5-Line.
 |
We now apply EPM to the five-actor line (Figure 2a). To calculate positional perseverance (Si), Step 1a determines whether an actor is excludable or not and assigns each actor a value based on its excludability (Figure 2b):
EC = 0.5; EB1,2 = 1.0; EA1,2 = 0.5
Step 1b assigns relational benefit values (Ri) to each actor’s relations and Step 1c incorporates degree (Di) by summing across relations using equation 3 (Figure 2c). Thus,
RC = 0.5 + 0.5 = 1.0; RB1,2 = 1.0 + 1.0 = 2.0; RA1,2 = 0.5
Step 1d uses equation 4 to compute each actor’s positional perseverance value (Figure 2d). Thus,
SC = 0.5 x 1.0 = 0.5; SB1,2 = 1.0 x 2.0 = 2.0; SA1,2 = 0.5 x 0.5 = 0.25
Step 2 uses equation 5 to compute each relation’s joint perseverance value (Figure 2e). Thus,
JA1-B1 = 0.25 x 2.0 = 0.5; JB1-C = 2.0 x 0.5 = 1.0
JC-B2 = 2.0 x 0.5 = 1.0; JB2-A2 = 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 5-Line adhere closely to those predicted by EPM.
6. Data
To test our theory and method, we analyze data from the six networks of Figure 1. The networks chosen for comparison do not represent a random sample of all possible exchange networks. They are a convenient sample gathered from existing, archived data that several researchers provided to us. There were many other networks from which we could have chosen, but the included networks met three criteria. First, they each contain the possibility of emergent sub-networks that differ in some way from the “strength” of the overall network (i.e., if the overall network is weak power, an equal power sub-network must have the potential to emerge). This restriction effectively eliminates all centrally-connected “star” networks and 3-Lines. Second, there must be enough observations so that the sub-networks actually emerge. If no sub-networks emerged, then we would not be able to uncover any shifts in positional power due to network dynamics. Finally, third, the data must come from experiments in which participants had full information on all aspects of the exchange process (negotiations, resource pool divisions, and the like) and could exchange maximally once. This restriction virtually eliminated all the experiments run under the NETS experimental system (Lovaglia et al. 1995) as well as those from any unique exchange settings such as the “generalized exchange” experiments run by Linda Molm and colleagues (Molm et al. 1999, 2001).The data come from experiments conducted using ExNet 1.0+, which is a web-based system with full information and non-simultaneous 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 three-step 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.
7. Results
7.1 A Comparison of Probabilities of First Exchange
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
7-Line (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 first-exchange rates. That is, for the
7-Line, 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 7-Line. The predictions from Reciprocity, EVT, and EPM all closely matched the observed first-exchange rates, with EVT and EPM doing an especially good job predicting the 7-Line.
Turning to the 6-Line, the observed first-exchange 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 6-Line.
The results of the 5-Line, 4-Line, and 10-person networks all closely matched predictions by all four methods, with Reciprocity coming closest in the 5-Line, EVT doing the best in the 4-Line, and EVT and EPM doing about equally well in the 10-person 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% first-exchange 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 first-exchange rates across all six networks reported in Table 2. With the exception of the KITE, EPM correctly predicted the likelihood rankings of first-exchange 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 7-Lines. 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 first-exchange 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 first-exchange 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 5-Line, 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.
7.2 Predicting Second (and Further) Exchanges
Notes: The emergent sub-network 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 4-Line, the proportion of exchanges in the dyadic sub-network was less than 1.0 because 3 times out of 165 they failed to reach agreement. In the KITE, the relations in the triangle sub-network 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 sub-networks follow a pattern very similar to that of first exchanges in like networks. Specifically, in the 7-Line 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 5-Line. 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 sub-networks. That is, actors treat the emergent sub-networks “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 sub-networks).
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 sub-network. For example, in the 5-Line, the A – B relation was predicted to exchange first in the complete network, while the A – B and B – C relations are equi-probable in the emergent 3-Line sub-network. 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 sub-network, when all three relations have an equi-probable 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 sub-networks and analyzing them accordingly. We should note that when the most likely first exchange did not occur, the emergent sub-networks still behaved as if they were “stand-alone” networks. That is, for example when C and D exchanged in the 7-Line, the exchange in the resulting two sub-networks (a dyad and a 3-Line) followed the patterns predicted by EPM; as did the emergent 3-Lines in the 10-person 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 sub-networks and because these sub-networks emerged most often in our data.
8. Discussion and Future Directions
This paper has suggested that strategic choices by actors cause specific exchange patterns to emerge and that these patterns can be predicted a priori based on structural cues. This argument was supported by data gathered from experiments on a variety of exchange networks. Specifically, in head to head comparisons of exchange frequency predictions, the Exchange Pattern Method (EPM) performed nearly as well as the more complex Expected Value Theory (EVT) and better than ESL and Reciprocity. Additionally, since EPM’s accuracy supports the use of heuristic methods, the study of exchange patterns in large complex networks is now possible. However, we do not suggest that researchers abandon the more rigorous theoretical methods for one that includes heuristically-derived values. Hence, when possible (i.e., in small networks), Reciprocity or EVT should be used to predict patterns of exchange leaving EPM for application in larger exchange networks. The remainder of this section considers some implications, extensions, and potential problems associated with EPM.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., non-excludable 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 10-person 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.
References
Bienenstock, Elisa Jayne and Phillip Bonacich. 1993. “Game-Theory Models for Exchange Networks: Experimental Results.” Sociological Perspectives 36: 117-135.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: 1170-1182.
Bonacich, Phillip and Noah. 1998. “Unequally Valued Exchange Relations.” Social Psychology Quarterly 61: 160-71.
Book, Ronald. 1994. “Relativizations of the P=? NP and Other Problems: Developments in Structural Complexity Theory.” Society for Industrial and Applied Mathematics Review 36: 157-175.
Burke, Peter. 1997. “An Identity Model for Network Exchange.” American Sociological Review 62: 134-150.
Cheney, Ward and David Kincaid. 1985. Numerical Mathematics and Computing, 2nd 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: 721-739.
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: 275-305.
Cook, Karen S. and Mary R. Gillmore. 1984. “Power, Dependence, and Coalitions.” Pages 27-58 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 Theorem-Proving Procedures.”Proc. 3rd ACM Symp. Theory of Computing: 151-158.
Dahl, Robert. 1957. “The Concept of Power.” Behavioral Science 2: 201-218.
Doreian, Patrick
and Frans N.
Emerson, Richard M. 1972a. “Exchange Theory, Part I: A Psychological Basis for Social Exchange.”
Pages 38-57 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 59-87 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: 213-230.
______ . 1993. “An
Expected Value Model of Social Exchange Outcomes.” Pages 163-193 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: 213-222.
Girard, Dudley and Casey Borch. 2003. “Optimal Seek
Simplified.” Current Research in Social Psychology 8: 225-241.
Granovetter, Mark. 1973. “The Strength of Weak Ties.” American
Journal of Sociology 78: 1360-1380.
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: Springer-Verlag.
Lawler, Edward J. and Jeongkoo Yoon. 1993. “Power and the Emergence of Commitment Behavior in Negotiated Exchange.” American Sociological Review 58: 465-481.
______ . 1996. “Commitment
in Exchange Relations: Test of a Theory of Relational Cohesion.” American
Sociological Review 61: 89-108.
______ . 1998. “Network Structure and Emotion in Exchange Relations.” American Sociological Review 63: 871-894.
Leik, Robert K. 1992. “New Directions for Network Exchange
Theory: Strategic Manipulation of Network Linkages.” Social Networks 14: 309-323.
Lovaglia, Michael, John Skvoretz, David Willer,
and Barry Markovsky. 1995. “Negotiated
Outcomes in Social Exchange Networks.” Social
Forces 74: 123-155.
Lucas, Jeffrey W., C. Wesley Younts, Michael Lovaglia,
and Barry Markovsky. 2001. “Lines of Power in Exchange Networks.” Social
Forces 80: 185-214.
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:
220-236.
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: 197-209.
Marsden, Peter V. 1983. “Restricted Access in Networks and Models of Power.”
American Journal of Sociology 88: 686-717.
Molm, Linda D. 1990. “The Dynamics of
Power in Social Exchange.” American
Sociological Review 55: 427-447.
Molm, Linda D., Gretchen Peterson, and Nobuyuki Takahashi. 1999. “Power in Negotiated
and Reciprocal Exchange.” American
Sociological Review 64: 876-890.
______ . 2001. “The Value of Exchange.” Social
Forces 80: 159-185.
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: 31-49.
Sedgwick, Robert. 1992. Algorithms in
C++. Reading, MA: Addison-Wesley.
Simpson, Brent and David Willer.
1999. “A New Method for Finding Power Structures.” Pages 270-284 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: 88-100.
Skvoretz, John and David Willer. 1991. “Power in Exchange
Networks: Setting and Structure Variations.” Social Psychology Quarterly 54: 224-238.
______ . 1993. “Exclusion
and Power: A Test of Four Theories of Power in Exchange Networks.” American
Sociological Review 58: 801-18.
Skvoretz, John and Michael J. Lovaglia. 1995. “Who Exchanges
with Whom: Structural Determinants of Exchange Frequency in Negotiated Exchange
Networks.” Social Psychology Quarterly 58: 163-177.
Skvoretz, John and Pidi Zhang. 1997. “Actors’ Responses to Outcomes in Exchange
Networks: The Process of Power Development.” Sociological Perspectives 40: 183-197.
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 117-138 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: 1031-1049.
van Assen, M.A.L.M. and Dudley Girard. 2001. “Bargaining
in Exchange Networks.” Pages 101-135 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: 323-337.
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: 5-35.
______ . 1997b. “Network
Connection and Exchange Ratios: Theory, Predictions and Experimental Tests.” Pages
199-234 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: 67-107.
Willer, Robb and David Willer. 2000. “Exploring Dynamic
Networks: Hypotheses and Conjectures.” Social
Networks 22: 251-272.
Zelditch, Morris Jr. 1992. “Interpersonal
Power.” Pages 994-1001 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
5-Line, 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
5-Line, 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 5-Line network, which is computationally feasible (5-actor network, only 6 possible exchange outcomes). The
problem is that this cost does not scale linearly to larger networks.
Now consider a 50-actor
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!/(75-25)! = 8.16*1044. 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*1022. 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*39 = 2.22*1013.
The advantage of EPM is that, in this example, the 39 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 sub-network connected to a fully
connected sub-network 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*1027, which is still not cheap. To
get an idea of the scale of these numbers, the fastest computer in the world,
NEC’s Earth-Simulator, can execute about 35 trillion (3.5*1013)
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. Appendix A
The key to ESL, EVT, and Reciprocity’s computational cost
relative to EPM is that all possible exchange outcomes for a given network must be computed, while this is not the case for EPM. Finding
one valid group of exchanges for a network can be done efficiently. However, a problem occurs if all valid exchanges for a network must be found. In computer science, this is called finding a
“perfect matching” for a network (Kozen 1992). Research
has shown that finding the number of perfect “matchings”
in a network becomes computationally unfeasible as the size of the network
increases (Kozen 1992). In computer science, these
types of problems are called #P – complete (NP).
This means that one valid solution can be found efficiently, but finding all valid solutions is computationally unfeasible. Therefore,
since ESL, EVT, and Reciprocity must find all possible exchange outcomes, and
thus all perfect matches, they are computationally unfeasible to solve as the
number of nodes and edges increase past a relatively small number.