|
|
|
|
The study of dominance is an important aspect of sociology
and political science. In the study of dominance, it is assumed
that given a pair A and B (A and B might represent people, or teams, for
example) then either A dominates B or B dominates A, but not both. Dominance
would be of interest when studying gang violence or attending a tournament
in which each team in a league must play every other team exactly once,
with no ties allowed.
As an example, the following chart shows the results
of a tournament among five teams A, B, C, D, and E, where, for example,
AB indicates a game between teams A and B.
|
|
Game |
AB |
AC |
AD |
AE |
BC |
BD |
BE |
CD |
CE |
DE |
Winner |
A |
C |
D |
A |
C |
B |
E |
D |
E |
D |
|
|
A digraph for this tournament is shown in Figure 6.
|
|
Notice that there is no transitive property for dominance.
(Recall the transitive property for less than, for example:
if a < b and b < c, then a <
c.) As shown previously, A dominates (won the game with) B, and
B dominated D, but D dominates A.
The matrix corresponding to the digraph in Figure 6
is as follows.
|
|
|
A |
B |
C |
D |
E |
A |
|
B |
C |
D |
E |
|
|
As mentioned at the end of the previous section, this
matrix is an adjacency matrix. A matrix obtained from a dominance situation
will always be an adjacency matrix, since either A dominates B, or B dominates
A, but not both. Also, if the entry in row i and column j
is 0 (where ),
then the entry in row j and column i must be 1; if the entry
in row i and column j is 1 (where ),
then the entry that is in row j and column i must be 0.
Such a matrix is called asymmetric.
|
|
A digraph obtained from a dominance situation
leads to a matrix that is an asymmetric adjacency matrix. |
|
EXAMPLE 1
Each of the following matrices comes from a dominance
situation. Complete the matrix.
(a)
Because the matrix obtained from a dominance situation
must be asymmetric, the 1 in row 2, column 1 leads to a 0 in row 1, column
2. Complete the matrix as follows.
(b)
The 1 in row 1, column 3
leads to 0 in row 3, column 1, and the 0 in row 2, column 3, leads to
a 1 in row 3, column 2. Complete the matrix as follows.
|
.
|
EXAMPLE 2
Write a matrix for the dominance situation in Figure
7. List all dominances.
The directed edge from Q to P shows that Q dominates
P; also, P dominates R, and Q dominates R. Entering 1 for such dominances
and 0 for a lack of dominance leads to the following matrix.
|
|
|
|
The matrix shows that P dominates R, S, and T; Q dominates
P, R, and T; R dominates S and T; S dominates Q and T; and T dominates
no one.
Since P dominates R, S, and T directly, as seen in
the first row, P is said to have three one-stage dominances. Adding
the numbers in the second row of the matrix shows that Q has three one-stage
dominances; from the third and fourth rows, R and S have two each; from
the fifth row, T has none.
|
|
In Example 2, Q dominates R and R dominated S, but
Q did not dominate S. However, Q does have an indirect dominance over
S, through R. Because of this, Q is said to have a two-stage dominance
over S. Also, S has two-stage dominance over P.
Although we shall not prove it, the number of two-stage
dominances can be found by squaring the adjacency matrix. If we
use M for the matrix above, then
|
|
|
|
|
|
|
P
|
Q
|
R
|
S
|
T
|
|
M2 |
= |
|
|
= |
|
P |
Q |
R |
S |
T |
|
|
The 1 in row 1, column 2 of this result shows that
P has two-stage dominance over Q (through S), while P has two-stage dominance
over T in two ways (through R or through S). Adding the numbers
in each row of this matrix shows that P has a total of 0 + 1 + 0 + 1 +
2 = 4 two-stage dominances, while Q has 5, R has 2, S has 3, and T has
non. (Notice that matrix M2 is not an adjacency matrix.)
Adding matrices M and M2 gives
the total number of one-stage or two-stage dominances.
|
|
|
|
|
|
|
|
|
|
P
|
Q
|
R
|
S
|
T
|
|
M |
+ |
M2 |
= |
|
+ |
|
= |
|
P |
Q |
R |
S |
T |
|
|
The entry 3 in the upper right-hand corner of the result
shows that P has a total of 3 one-stage or two-stage dominances of T.
Also, Q has a total of 2 one-stage or two-stage dominances over both R
and S.
The sum of the entries in the P-column of matrix M
+ M2 gives the numbers of ways that P is dominated. For
example, from the first column, P is dominated in 0 + 1 + 0 + 1 + 0 =
2 ways, while Q is dominated in 3 ways, R in 4 ways, S in 5 ways, and
T in 10 ways. (This dominance is assumed to be in one stage or two stages.)
This process could be continued; finding M3
would give the number of three-stage dominances, M4
would give the number of four-stage dominances, and so on. A generalization
of this idea follows.
|
|
Let M be an adjacency matrix and let k
be a positive integer. Then the entry aij of Mk
gives the number of k-stage dominances of i over j.
Also, the sum of the entries in row i of the matrix
M + M2 + . . . + Mk
is the total number of ways that i is dominant in one, two,
. . ., k stages. |
|
|
EXAMPLE 3
A league is made up of six teams, A, B, C, D, E, and
F. In a recent tournament, the teams played each other exactly once, with
results as shown in the digraph in Figure 8. (No ties were allowed.)
|
|
|
|
The adjacency matrix for the tournament follows.
|
|
|
A |
B |
C |
D |
E |
F |
M |
= |
|
A |
B |
C |
D |
E |
F |
|
|
It is not possible to use this matrix to decide on
a winner, since both teams D and E won four games, while all other teams
won fewer games. To help choose a winner, we could find M2
to get two-stage wins for each team. Find M2 as follows.
|
|
|
|
The sum M + M2 gives the total
number of one-stage and two-stage wins for each team.
|
|
|
|
|
|
|
|
|
|
A |
B |
C |
D |
E |
F |
M |
+ |
M2 |
= |
|
+ |
|
= |
|
A |
B |
C |
D |
E |
F |
|
|
The results show that team D had a total of 2 + 3 +
4 + 0 + 1 + 3 = 13 one- or two-stage wins, while all other teams had fewer
wins. Based on this result, team D could be declared the winner of the
tournament.
|
|
Exercises
For each matrix in Exercises 1-10 that is the
matrix of a dominance digraph, find the matrix representing two-stage
dominance. Assume the matrices represent the result of 2-, 3- 4-, or
5-person games. Find the total number of people dominated by each person
in one or two stages.
1. |
|
A |
B |
A |
|
B |
|
2. |
|
A |
B |
A |
|
B |
|
3. |
|
P |
Q |
R |
P |
|
Q |
R |
|
4. |
|
Z |
W |
T |
Z |
|
W |
T |
|
5. |
|
X |
Y |
Z |
X |
|
Y |
Z |
|
6. |
|
M |
N |
P |
M |
|
N |
P |
|
7. |
|
R |
S |
T |
V |
R |
|
S |
T |
V |
|
8. |
|
P |
Q |
R |
S |
P |
|
Q |
R |
S |
|
9. |
|
A |
B |
C |
D |
E |
A |
|
B |
C |
D |
E |
|
10. |
|
X |
Y |
Z |
W |
T |
X |
|
Y |
Z |
W |
T |
|
For each digraph in Exercises 11-14, write the
corresponding matrix. Find the number of two-stage dominances for
A, B, C, and D. List all two-stage dominances. |
11. |
|
12. |
|
13. |
|
14. |
|
|
|
|
Applications
SOCIAL SCIENCES
|
Determining a Winner
|
Draw a digraph and write a matrix for each of the following situations. |
15. |
Game |
AB |
AC |
AD |
AE |
BC |
BD |
BE |
CD |
CE |
DE |
Winner |
A |
C |
A |
A |
C |
B |
B |
D |
C |
D |
|
|
16. |
Game |
AB |
AC |
AD |
AE |
BC |
BD |
BE |
CD |
CE |
DE |
Winner |
B |
C |
A |
A |
B |
B |
E |
C |
E |
E |
|
|
Preference Tests
|
Another application of dominance comes from taste- or color-preference
tests. For example, a consumer is shown several difference colors for a
new car, two at a time. The consumer then indicates a preference for one
in each pair, for all possible pairs of colors. A "favorite" color can then
be selected, using the methods above. In Exercises 17-20, find one- and
two-stage dominances and then choose the favorite. |
17. |
The colors red, orange, yellow, and green are under consideration
for a new cereal. A consumer is shown samples of the cereal in each
color, two at a time. The results are as follows. |
Pairs of Colors |
RO |
RY |
RG |
OY |
OG |
YG |
Choice |
R |
R |
G |
O |
G |
Y |
|
|
18. |
A perfume company is considering four possible fragrances for a
new perfume: lilac, rose, apple blossom, and gardenia. The results
of one consumer preference survey were as follows. |
Pairs of Fragrances |
LR |
LA |
LG |
RA |
RG |
AG |
Choice |
R |
A |
L |
R |
G |
A |
|
|
19. |
In a wine-tasting session a consumer compared five wines, A, B,
C, D, and E, with the following results. |
Wines |
AB |
AC |
AD |
AE |
BD |
BE |
CD |
CE |
DE |
Choice |
A |
A |
D |
E |
B |
B |
B |
C |
E |
E |
|
|
20. |
A manager made a comparison among five worker: A, B, C, D, and E.
The workers were compared two at a time, with the following results |
Wines |
AB |
AC |
AD |
AE |
BD |
BE |
CD |
CE |
DE |
Choice |
A |
A |
D |
A |
C |
B |
B |
C |
C |
D |
|
|
FOR THE COMPUTER |
Find the number of four-stage dominances for each person in the following
matrices. |
21. |
The matrix in Exercise 9 |
22. |
The matrix in Exercise 10 |
|
| | |