Sunday, February 1, 2015

Strength of Schedule & Adjusted Statistics (Part 4)

In the first three parts of this series, I've explained the problem with comparing statistics between teams (because they don't all play the same opponents), described how to measure the strength of a team's schedule, and then how to use that to calculate an "adjusted" statistic that provides a more accurate comparison between teams.  In this post, I'll discuss how to implement this method.

Many metrics of this sort that use symmetric statistics (such as winning percentage) can be expressed as a system of linear equations, which can be solved exactly by easily available software.  However, for asymmetric statistics, the strength of schedule ends up in the denominator of the adjusted statistic, resulting in a non-linear equation, which cannot generally be solved exactly.  We must use a numerical method, such as the iterative method.

The basic idea of the iterative method is to repeatedly recalculate the adjusted statistic using the current values of the adjusted statistic until the numbers stop changing (i.e., the solution converges on an answer).  If the new value of the adjusted statistic is S'_"adj" and the old values are S_"adj" then the iterative equation is:

S'_"adj"(T) = (S(T))/ ((1/(n*m)) sum_(i="opponents"(T))^n sum_(j="opponents"(i))^m (j ne T) S_"adj"(j))

(If this is confusing, see the example in my previous post.)  So now let's talk about how we would implement this iterative calculation.

The term in the numerator of this equation -- S(T) -- is a constant.  It's just the unadjusted value of the statistic S for team T.  The work of the calculation is in the denominator, which represents the average adjusted statistic for all of team T's opponents' opponents.  So how do we calculate this?  The first step is to figure out team T's opponents' opponents.

It turns out that this problem is related to graph theory.  We can represent a season of games as a graph where each node is a team and each edge represents a game.  Suppose that we have a league with four teams: Gold, Blue, Silver and Green.  Each of these will be represented as a node in our graph.  Gold has played Blue, Blue has also played Silver, and Silver has played Green twice.  Each of these games is represented as an edge:

To find all the opponents of a team, we start at the node for the team and traverse one step along every path leading out of the node.  Starting at Gold, our only choice is to walk to Blue -- and that is Gold's only opponent so far.  If we want to find the opponents' opponents, we walk two steps.  For Gold, the first step takes us to Blue and then we have two choices for our second step:  to Silver or back to Gold.  And indeed, Blue (Gold's only opponent) two opponents have been Gold and Silver.

In graph theory, a graph of the sort pictured above is represented by an adjacency matrix.  For a graph with N nodes, this is simply an NxN matrix where the (i,j) entry is 1 if there is an edge between those two nodes, and a 0 otherwise.  If we let Gold=0, Blue=1, Silver=2 and Green = 3, the adjacency matrix for the graph above is:

[[0,1,0,0],[1,0,1,0],[0,1,0,2],[0,0,2,0]]

Silver has played Green twice, so we put a 2 in those spots.  Notice that this matrix is symmetric (i.e., a_"ij" = a_"ji").  For our problem, the matrix will always be symmetric, because if Team A has played Team B, then naturally Team B has played Team A.

An interesting thing about representing a graph this way is that if we multiply the adjacency matrix by itself, the result is a matrix that tells us how many two step paths connect each pair of nodes.  (And if we multiply it three times, it gives us the three step paths, and so on.)  So for our example:

[[0,1,0,0],[1,0,1,0],[0,1,0,2],[0,0,2,0]] * [[0,1,0,0],[1,0,1,0],[0,1,0,2],[0,0,2,0]] =[[1,0,1,0],[0,2,0,2],[1,0,5,0],[0,2,0,4]]

The first row of the result shows us that Gold has had itself and Blue as it's two opponents' opponents, just as we saw above.  If you look at the second row, you'll see that Blue has had Green as an opponents' opponent twice, because there are two edges from Silver to Green.

This provides a straightforward way to calculate any team's opponents' opponents.  We keep a matrix showing which teams have played each other, and then multiply it by itself to get the opponents' opponents.

If you look back at our equation for the adjusted statistic, you'll see that there's a slight twist in the denominator.  We're ignoring any case where a team's opponents' opponent is the team itself:

S'_"adj"(T) = (S(T))/ ((1/(n*m)) sum_(i="opponents"(T))^n sum_(j="opponents"(i))^m (j ne T) S_"adj"(j))

This is easy to do in our matrix formulation.  These are the diagonal entries in the answer matrix, and we can ignore them by setting them to zero.  For our example above:

[[0,0,1,0],[0,0,0,2],[1,0,0,0],[0,2,0,0]]

I'll going to call this the Modified Opponents' Opponents Matrix (MOOM).

The next step in our calculation is to sum up the adjusted statistic for all the opponents' opponents.  It turns out there's an easy way to do this.  We simply multiply the MOOM by a matrix listing the adjusted statistics of all the teams.  So if these are the unadjusted statistic values that we will use as our first guess:

Gold34%
Blue24%
Silver30%
Green15%

Then our matrix multiplication is:

[[0,0,1,0],[0,0,0,2],[1,0,0,0],[0,2,0,0]]*[[0.34],[0.24],[0.30],[0.15]] = [[0.30],[0.30],[0.34],[0.48]]

The resulting matrix provides the sum of the opponents' opponents adjusted statistics for each team.  For example, the first row (0.30) is the sum of all of Gold's opponents' opponents adjusted statistic.  Since Gold's only opponent's opponent was Silver, this is just Silver's adjusted statistic.

Now we have to average each of these values by dividing them by the number of opponents' opponents.  There's an easy way to get this number as well.  We multiply the MOOM by a column of ones:

[[0,0,1,0],[0,0,0,2],[1,0,0,0],[0,2,0,0]]*[[1],[1],[1],[1]] = [[1],[2],[1],[2]]

The resulting matrix provides the number of opponents' opponents for each team.  Now dividing each of the sums by each of the counts gives us the Strength of Schedule for each team (the denominator in the original equation).

[[0.30/1],[0.30/2],[0.34/1],[0.48/2]] = [[0.30],[0.15],[0.34],[0.24]]

And we can use that to calculate new values for the adjusted statistic:

Gold0.340.301.13
Blue0.240.151.60
Silver0.300.340.88
Green0.150.240.63

We then repeat that process until the adjusted statistics converge.

(NOTE:  As it happens, the above example doesn't actually converge.  As noted in the previous post, this method seems to work for NCAA basketball after about 500 games in the season, but I have not proven that it will converge in all cases.)

Finally, notice that the MOOM and the count of the opponents' opponents do not change during the iteration process.  The only things we need to calculate during the iteration process is the new sum of the adjusted statistics, the average, and then the new adjusted statistics.

In the next post I'll talk about how well this works in practice and some alternative approaches.