Lesson 6 of 8 · 15 min

Dominance matrices

Record round-robin results in a dominance matrix, count one-step and two-step dominances with D\bm{D} and D2\bm{D}^2, and use them to rank competitors and break ties.

What you will be able to do

  • Build a dominance matrix from results or a directed graph.
  • Interpret row sums of D\bm{D} as one-step dominances.
  • Use D2\bm{D}^2 to count two-step dominances and D+D2\bm{D} + \bm{D}^2 to rank competitors.

Five netball teams, A to E, play a round robin: every team plays every other team once, and there are no draws. Afterwards three teams have won two games each. Who should be ranked higher?

Counting wins is a start, but a win over a strong team ought to count for more than a win over a weak one. A dominance matrix lets you measure that.

Interactive

The results as a directed graph

An arrow from one team to another means the first team won. Ten arrows, one for each game. A, C and D each have two arrows going out.

Definition

Dominance matrix

For nn competitors, the dominance matrix D\bm{D} is the n×nn \times n matrix with

dij={1if i dominates (beats) j0otherwised_{ij} = \begin{cases} 1 & \text{if } i \text{ dominates (beats) } j \\ 0 & \text{otherwise} \end{cases}

The leading diagonal is all 00 (no one plays themselves). In a round robin with no draws, for each pair exactly one of dijd_{ij} and djid_{ji} is 11.

For the netball results, with rows and columns in the order A, B, C, D, E:

D=[0110000111000111000110000]row sums: [23221]\bm{D} = \begin{bmatrix} 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \end{bmatrix} \qquad \text{row sums: } \begin{bmatrix} 2 \\ 3 \\ 2 \\ 2 \\ 1 \end{bmatrix}

Row ii lists who ii beat, so its row sum is ii's number of wins, its one-step dominances. Columns list losses.

Using the matrix D\bm{D} above, how many games did team B lose?

Now the clever part. A beat C, and C beat D, so A has an indirect, two-step dominance over D. Count them all by squaring the matrix: entry (i,j)(i, j) of D2\bm{D}^2 is ∑kdikdkj\sum_k d_{ik}d_{kj}, and each product dikdkjd_{ik}d_{kj} is 11 exactly when ii beat kk and kk beat jj.

For the netball results (by hand, or with the calculator's matrix editor):

D2=[0012220012200011110001100]row sums: [55332]\bm{D}^2 = \begin{bmatrix} 0 & 0 & 1 & 2 & 2 \\ 2 & 0 & 0 & 1 & 2 \\ 2 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \end{bmatrix} \qquad \text{row sums: } \begin{bmatrix} 5 \\ 5 \\ 3 \\ 3 \\ 2 \end{bmatrix}

Row A is [0  0  1  2  2][0 \; 0 \; 1 \; 2 \; 2]: A beats D in two steps in two ways, through B and through C, and A beats C in two steps once, through B.

Key idea

Ranking with D + D²

  • Row sums of D\bm{D} count one-step dominances.
  • Row sums of D2\bm{D}^2 count two-step dominances.
  • Rank competitors by the row sums of D+D2\bm{D} + \bm{D}^2, the total dominance.

If two competitors are still tied, look at the head-to-head result, or at D3\bm{D}^3.

Worked example

Rank teams with a dominance matrix

  • Complex familiar

In a round-robin netball competition with no draws: A beat B and C; B beat C, D and E; C beat D and E; D beat A and E; E beat A.

Use a dominance matrix to rank the five teams.

4 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Build D\bm{D} with winners as rows.

  2. Find D2\bm{D}^2 (by hand or with technology) and the row sums of D+D2\bm{D} + \bm{D}^2.

  3. Rank by total dominance, then break ties by the head-to-head result.

Watch out for

  • Ranking by column sums, which count losses.

  • Squaring each entry of D\bm{D} instead of multiplying D\bm{D} by itself.

For the netball results, how many two-step dominances does team E have? (That is, the row sum for E in D2\bm{D}^2.)

In a round-robin competition with no draws, which statement is always true of the dominance matrix D\bm{D}, for i≠ji \neq j?

Choose one answer

Common mistake

Rows are wins, columns are losses

Always build D\bm{D} with the winner as the row. Ranking by column sums ranks the teams by their losses, upside down. And don't put 11s on the diagonal: a team does not dominate itself.

Note

Beyond sport

Dominance matrices model any one-way relationship: which species preys on which in a food web, which person influences which in a social network, or which product beats another in head-to-head customer surveys.

Summary

  • In a dominance matrix, dij=1d_{ij} = 1 if ii dominates jj, else 00; the diagonal is all zero.

  • Row sums of D\bm{D} are one-step dominances (wins).

  • D2\bm{D}^2 counts two-step dominances: ii beat someone who beat jj.

  • Rank by the row sums of D+D2\bm{D} + \bm{D}^2; break any remaining tie by the head-to-head result.

Finished the lesson?

Try the 3 quick checks above and the lesson completes itself, or mark it complete now.

Lesson 6 of 80% read

Save your progress with a free account