USING GRAPHS TO ANALYZE SPORTS DRAFTS

C. Bryan Dawson

1. Introduction. Sports drafts involving two teams, like any two–player game, can very quickly become complicated to analyze because of the great number of moves that must be considered. Even small examples can cause difficulties. My personal experience with this came when I received a referee’s report on the first draft of [1]. Much to my chagrin, I had incorrectly worked an example in the paper. Upon further examination, however, I discovered that the referee’s alternative solution was also incorrect! The purpose of this paper is to offer a correct solution to the example with the help of graphs.

First, we need to know the assumptions under which the problem lies. In a general two–team draft, two owners are to pick teams of n players each from a pool of m ≥ 2n available players. We do not assume additivity of player values, that is, the value of a team is not necessarily the sum of the values of the individual players; therefore, we will place values on complete teams only. We assume that neither owner knows the other owner’s evaluations of the possible teams, and these evaluations may be different. Finally, we assume that the owners will employ a conservative strategy, minimizing risk, rather than a gambling one. It is this last assumption that leads to the difficulties in analysis. For a more complete discussion of these assumptions, see [1].

There are two draft scenarios that we shall consider, leading to two different games. The first scenario is that the two owners will possess the only two teams in existence at the end of the draft. Your goal as an owner is to have a team that you value highly with respect to the other owner’s team, i.e., to maximize the quantity

your evaluation of your team − your evaluation of the other owner’s team.

The second scenario is that of an “expansion draft,” where the two owners are joining a league that already has several other teams. Now, in order to compete with the other teams in the league, your goal as an owner is to maximize your evaluation of your team.

The example we consider is Example 2 from [1].

\underline{Example 2}. Suppose O_{1} and O_{2} are to choose three–player teams from among A, B, C, D, E, and F, and the evaluations (e_{1}, e_{2}) by O_{1} and O_{2} of the possible teams are given by:

{A, B, C} − (9, 10) {A, B, D} − (10, 9) {A, B, E} − (8, 8) {A, B, F } − (8, 8)
{A, C, D} − (8, 8) {A, C, E} − (10, 9) {A, C, F } − (10, 9)
{A, D, E} − (8, 7) {A, D, F } − (8, 7)

{A, E, F } − (8, 7)

{B, C, D} − (5, 6) {B, C, E} − (5, 6) {B, C, F } − (5, 6)
{B, D, E} − (6, 8) {B, D, F } − (6, 8)

{B, E, F } − (7, 9)

{C, D, E} − (7, 9) {C, D, F } − (7, 9)

{C, E, F } − (6, 8) {D, E, F } − (7, 10)

For the purposes of this paper, we will assume that a “modified draft” (not the “cut–and–choose” draft of [1]) is being used, with O_{2} first. The draft order, then, is O_{2}, O_{1}, O_{1}, O_{2}, O_{2}, O_{1}.

2. The Two–Team–Only Case. Who should O_{2} choose first? Note that no matter what team O_{2} ends up with, the quantity O_{2}’s evaluation of O_{2}’s team – O_{2}’s evaluation of O_{1}’s team is either 1, 0, or −1. Since O_{2} goes first, they would certainly hope to be at an advantage, that is, they would hope to make the above quantity 1. Does there exist a strategy to guarantee this? In order to answer the question, we resort to the construction of graphs.

Suppose O_{2} chooses A first. Then O_{1} will choose the next two players, leaving three players from whom O_{2} chooses two. Create a graph with five vertices labeled B, C, D, E, and F. Place an edge between each pair {P_{1}, P_{2}} of vertices for which {A, P_{1}, P_{2}} does not result in an advantage for O_{2} (i.e., in which the above quantity is 0 or 1). If there is a circuit of length three (i.e., if a triangle exists), then O_{1} could choose the two players not in the circuit, meaning that O_{2} would be forced to choose two players connected by an edge. Thus, they would not have an advantage. If there is no circuit of length three in the graph, then no matter what two players O_{1} chooses, O_{2} still is able to pick two remaining players not connected by an edge, and is guaranteed an advantage. By constructing similar graphs for initial choices of B, C, D, E, and F (see Figure 1 at the end of this paper), one can see that O_{2} is guaranteed an advantage by choosing A, E, or F first.

Assuming O_{2} chooses A first, which two players should be chosen by O_{1}? Again, graphs come to the rescue. Notice that since O_{2} has player A, the quantity O_{1}’s evaluation of O_{1}’s team – O_{1}’s evaluation of O_{2}’s team will be negative. In fact, the possible values for that quantity are −1, −2, −3, and −4. Construct a graph with vertices B, C, D, E, and F, and place an edge between P_{1} and P_{2} if {A, P_{1}, P_{2}} is a team for O_{2} for which the quantity above takes on the value −1. If there is a circuit of length three, then O_{1} should choose the other two players, for no matter which two of the remaining three players O_{2} chooses, O_{1} has maximized their quantity at −1. Unfortunately, no such circuit exists (see Figure 2). We then add to the graph edges corresponding to quantities of −2; that is, we add an edge between P_{1} and P_{2} if {A, P_{1}, P_{2}} is a team for O_{2} for which the quantity above takes on the value −2 (see Figure 2). There is still no circuit of length three, and therefore O_{1} does not have a choice that guarantees a quantity of no worse than −2. The edges corresponding to a quantity of −3 are then added. This does result in the presence of circuits of length three. O_{1} then chooses either B and C or C and D to maximize their quantity at −3. O_{2}’s choice of two players is then determined by consulting the graph generated in the previous paragraph as explained there. O_{1} is given the remaining player and the draft ends.

If O_{2} chooses E first, the quantity O_{1}’s evaluation of O_{1}’s team – O_{1}’s evaluation of O_{2}’s team may be as high as 4. We thus begin our graph as in the previous paragraph with edges corresponding to 4, then 3, and so on, continuing until we obtain a circuit of length three. Note that a circuit of length four is present in the graph for quantities 2 or higher, but a circuit of length three is not obtained until the graph for quantities 1 or higher (see Figure 3). At that time, O_{1} chooses A and one other player. As before, O_{2} chooses the next two players by consulting their graph, and the remaining player goes to O_{1}. The analysis corresponding to an initial choice of F by O_{2} is similar.

3. The Expansion Draft Case. When the objective of a game is changed, optimal strategic play may also change. Such is the case when we change to an expansion draft, leaving all other assumptions of the example unchanged. Recall that now our objective is to obtain a team whose value is maximized.

Again, O_{2} is to choose first. The possible values of teams, according to O_{2}, are 6, 7, 8, 9, and 10. Does O_{2} have an initial choice that could guarantee, say, a team worth at least 8? As before, we construct a graph for each of O_{2}’s six possible initial choices. For an initial choice of A, place an edge between P_{1} and P_{2} if {A, P_{1}, P_{2}} is a team valued 7 or less. If a circuit of length three exists, O_{1} could choose the other two players on their turn, leaving O_{2} with a team worth 7 or less. In that case, an initial choice of A would not guarantee O_{2} a team worth 8 or more. However, if no such circuit exists, that initial choice would guarantee O_{2} a team worth 8 or more. One can see that the only initial choice that cannot guarantee O_{2} a team worth 8 is A (see Figure 4).

Now, does there exist an initial choice that can guarantee O_{2} a team worth at least 9? We need only add edges to the graphs for initial choices B, C, D, E, and F that correspond to teams valued 8 in the same manner as before. The addition of those edges creates circuits of length three in all graphs except for the initial choice D, whose graph only contains circuits of length four (see Figure 5). Hence, O_{2} should choose D first.

Next, O_{1} must choose two players. Unfortunately, I have not found graphs helpful in this determination. As O_{1} has only ten possible choices of two players, it is not difficult to check the minimum value that each of those choices could give to O_{1}. The greatest of these minimum values occurs with a choice of A and C, which guarantees O_{1} a team worth no less than 9. After consulting their graph, O_{2} then chooses E and F, leaving B for O_{1}. Notice that O_{2} actually winds up with a team they value 10, and not just the 9 that they were guaranteed by their initial choice.

4. Conclusion. The astute reader has likely noticed that the above procedures apply directly only to drafts with this particular number of available players and players to be chosen. We leave it as a challenge exercise to expand these methods to drafts with differing number of players available and players chosen. Careful — you just might enjoy yourself!

\underline{Reference}

1. B. Dawson, “A Better Draft: Fair Division of the Talent Pool,” The College Mathematics Journal, 28 (1997), 82–88.

C. Bryan Dawson Department of Mathematics and Computer Science Union University – Box 1899 1050 Union University Drive Jackson, TN 38305 email: bdawson@uu.edu 5 6 7