Title

Brian M. Lewis - bigems@gmail.com
Math 213 -- Mathematics with Mathematica, Fall 2009 
December 3, 2009

Abstract

My project investigates how to create a fantasy football schedule for you fantasy league while repeating the least amount of matchups possible.

Section 1. Introduction

1.1 Background

I'm a big fantasy football fan. This year my fantasy football commissioner asked me to create a schedule for our 16 team league in which everybody gets to play everybody else at least once without repeating matchups.  Doing this by hand proved to be very difficult, so I wondered if there was a way to do this automatically and in a random way.

1.2 Problem Statement

The problem statement I answer is:

Can a head to head schedule be generated in a random way?

1.3 Useful Commands

Some of the commands that were necessary for my project was If, Mod, and Table, Combinatorica, and CompleteGraph. Table creates a list of values based on a certain criteria. Mod[m,n] returns the remainder on division of m by n. If executes a certain code only if a certain condition is true, you can also specify what to do if the condition is false. I used these 3 commands in conjuction to help generate my list. Combinatorica is a library which includes important graph structures. CompleteGraph[n] generates a graph with n vertices that are all connected to one another.

Needs["Combinatorica`"]

Section 2. Main Work

2.1 How many unique matchups are there for n teams?

First of all in a head to head league, each team is matched up with another team every week. Every team plays every week so it is necessary to have an even number of teams, otherwise one team will always be left without an opponent. In a complete graph, the vertices could represent the teams and the edges represent the possible matchups. So to figure how many unique matchups there are I counted how many edges there are in a completegraph. There is also a simple formula for the number of edges in a complete graph: (n(n-1))/2.

n=6;(n(n-1))/2

Length[Edges[CompleteGraph[6]]]

(*The Edges command outputs a list of all the edges in CompleteGraph[8], Length outputs how many are in this list.*)

2.2 How many weeks does it take to play all other teams.

If the number of teams in a league is n, there are n-1 other teams for any particular team to play against. Therefore for any number of teams,n, it will take at least n-1 weeks to play everyone else at least once.

2.3 Creating the list of games such that no team plays the same team twice.

Let the numbers from 1 through n represent the teams. This is a problem of creating a table of all pairs of teams, but sorted into weeks where each week no team plays more than once and no matchup is repeated in any other week. Each week there are n/2 matchups, and there are n-1 weeks needed, notice if you multiply the # of matchups times the # of weeks you get the formula in part 2.1. I used what is called the "turning trick" to accomplish this. (Pearls in Graph Theory, Hartsfield and Ringel pg 33). The following code generates this table.

Sched[n_]:=Table[{Mod[i+j,n-1,1],If[j==0,n,Mod[n+i-j-1,n-1,1]]},{i,0,n-2},{j,0,(n/2)-1}]

The function Sched recreates the turning trick found in my graph theory textbook. In essence you take your complete graph and arrange the vertices in a circle. For the first week, connect n/2 pairs of vertices so that all the lines are parallel, then rotate these edges.(This is a simplified explanation, to gain a deeper understanding I suggest reading the book referenced or enrolling in Prof. Hanusa's Math 634- Graph Theory course.)

Sched[6];

{{{5,6},{1,4},{2,3}},
{{1,6},{2,5},{3,4}},
{{2,6},{3,1},{4,5}},
{{3,6},{4,2},{5,1}},
{{4,6},{5,3},{1,2}}};

(* an example of a 6 team schedule. 3 matchups per week, 5 weeks, 15 unique matchups!*)

2.4 Turning Trick in Action

To see how the turning trick works in practice. Use the manipulate below. Set the number of teams you would like(16 looks best) and move the weeks to see how the matchups change. As you will see it appears to rotate, hence the name "turning" trick.

nobrack[{x__}]:=x

(* nobrack is a simple code to remove the brackets from a list so that i can input it into the manipulate*)

Manipulate[ShowLabeledGraph[SetGraphOptions[CompleteGraph[Teams],
{nobrack[Sched[Teams][[Week]]],EdgeColor->Blue},EdgeColor->Transparent
]],{{Teams,16},2,16,2},{Week,1,Teams-1,1}]

Section 3. Conclusion and Future Work

3.1 Summary

It appears that the only way to generate a list like this is to use this turning trick. In my attempts to generate a random list of matchups, I always ran into a situation where only 1 possible pair would fit and this pair was already used. The turning trick guarantees no repeats and no conflicts.

3.2 Discussion

It took a lot of hard work to figure out that I could not generate this list randomly. Prior to discovering the turning trick, I approached the problem in 2 different ways. First I attempted to use what is called a maximal matching to get a list of games for the week. This code would generate a list of all possible games, then get a maximal matching and remove those pairs from the list, then create another matching using the remaining pairs and so on. This code did work very well for powers of 2 (4,8,16) but for numbers like 10 and 12, it ceased to give complete weeks after the 1st 2nd or 3rd week. This is due to the way MaximalMatching algorithm generates it's matchings.

See how my first attempt works here:(Double-Click right side bracket to expand)

Input the command Schedule[n, w] where n is the number of teams (it works for odd numbers too) and w is the number of weeks. Use a week number that is less than the number of teams and try numbers that are not powers of 2, such as 6, 10 or 12. Remember that the length of each week should be n/2, you will notice that the number of games each week are inconsistent.

Schedule[n_,w_]:= 
Module[{league= CompleteGraph[n],i=0, s={}},
While[i<w,s=Append[s,MaximalMatching[league]];league=DeleteEdges[league,MaximalMatching[league]];
i++;
];
RandomSample[s]]

Schedule[7,5]

After failing with the first attempt, I wrote code to generate 1 week of games (see week below). This function first looks at the list of all possible games using Edges[CompleteGraph[n]]. Using RandomChoice, It selects a random pair from that list and adds it as the 1 st matchup of the week. It does this repetitively, each time checking to see if either of the numbers in the pair was already used this week. If a number was used it would discard it from the list and try another pair until the week has n/2 matchups. This worked perfectly for any number of teams in one week. I then tried to generate every week in the same manner, while checking to see if any of the pairs were used in the previous week. This is where the problem began. An example will illustrate why i had a problem. Lets say for 8 teams, in week one, my code generates the list {{1, 2}, {3, 4}, {5, 6}, {7, 8}} then for the second week those 4 choices are removed from the list. As it generates a new week it chooses {{3, 6}, {5, 1}, {2, 4} ....as you see the last pair MUST be {7, 8} but this is not possible since {7, 8} was used in the first week. In order to remedy this I' d have to write a code that swaps out {7, 8} and some other pair while replacing it with some other 2 pairs but this can take forever and it still may not be possible.

See the Week function in action: (Double-Click right side bracket to expand)

Week[n_?EvenQ&&Positive]:=Module[{d={},g=Edges[CompleteGraph[n]]},r=RandomChoice[g];While[Length[d]<(n/2),
If[(Not[MemberQ[d,r[[1]],2]]&&Not[MemberQ[d,r[[2]],2]]),d=Append[d,r]];g =Complement[g,{r}];
r=RandomChoice[g]];d]
Week[n_?OddQ]= "This function Requires an even number of teams.";
Week[n_?NonPositive] = "Please use a positive number.";

It was at this point I realized that random selection is too difficult and there must be an orderly way to accomplish this task. I remembered learning about a turning trick in my Graph Theory course, and also seeing an example that Prof. Hanusa showed us using Mathematica. This was my inspiration to use the turning trick to solve this problem.

3.3 Future Work

The Sched function only generates n-1 weeks. In fantasy football, the regular season usually consists of the first 13 weeks of the regular NFL season. If your fantasy league has less than 14 teams, this will not generate enough weeks to fill the schedule. Depending on your league you may be separated into divisions in which teams play their division teams twice. This may alleviate the problem. If there are no divisions then there would be no choice but to repeat some of the previous matchups, this could be accomplished by copying m matchups from the original schedule and adding them to the schedule until m+n-1=13(or # of weeks needed).

Section 4. References

Turning Trick in Action.nb, Professor Christopher Hanusa, PhD
Pearls in Graph Theory: A Comprehensive Introduction, Hartsfield and Ringel