Who Won!

Competitions are a staple of American life whether they take the form of an end of season basketball tournament between a collection of colleges, a little league baseball team playoff, or a group of individuals competing for the American chess championship. Many schemes have been devised to get at the best player or team.

One mathematical concern is how to schedule such tournaments. Here the situation for hockey, which requires a special kind of locale (ice rink), differs from chess or bridge where the space that can be used to conduct the tournament is more flexible. Such scheduling problems draw on ideas from combinatorics and finite geometry (balanced incomplete block designs).

After the tournament is played, an important aspect of tournaments is to decide how well the teams or players performed. Was there a clear winner? What might be a good ranking of the teams from strongest team to weakest team? Were some teams equally strong so that a "tie" should be declared? We shall see that some of the same tools that help with scheduling problems can also be brought to bear on these ranking questions.

To try to answer questions of this type we will begin by using a simple mathematical model as shown in Figure 1. Here the teams or players are represented by dots (small circles) and the number inside the dot is the name of the team or player. We consider tournament situations which cannot result in ties between the teams or players. Many sports, to make the matches more dramatic, have a way to avoid having ties occur. Thus, if player i has a match against player j, then either i beats j or j beats i. We show this in a diagram such as Figure 1 by putting a line segment with an arrow directed from team i to team j when in the match that they play team i beats team j. Now we can read off how many matches were won by a particular player. In Figure 1, for example, player 3 won 2 matches, those played against teams 4 and 5. Of course, if one knows how many matches a player wins in a round robin tournament without ties, one can figure out how many matches the player lost. Each team plays the same number of games as every other team and this number is one less than the number of teams in the tournament. As is often the case in constructing a mathematical model or representation for some situation in order to obtain insight, we have simplified (thrown away) some information in the process of drawing a graph such as the one in Figure 1. Thus, while i may beat j, we are not trying to record by "how much" i beat j. Sometimes this information is available as in basketball or baseball where each team has a score and we know by how much one team beat the other.

Who do you think should be declared the winner for the tournaments whose results are shown in Figure 1? Which team performed least well?

 

 

Winners and rankings

The diagram in Figure 1 is an example of a geometrical problem solving tool called a digraph, a short term for directed graph. It generalizes the concept of a graph, which is a diagram consisting of dots and line segments. The diagram in Figure 2 arises from suppressing the directions on the edges of the digraph in Figure 1:

 

The dots in a graph or digraph are called vertices or nodes, while the line segments are known as edges or arcs. Note that we don't pay attention to the physical points in Figures 1 and 2 where lines between the (large) dots may meet. (In Figure 2 there are 5 such points but one can redraw the picture so that only one such non-vertex "crossing" occurs; the diagram shows connections between the same vertices.) Sometimes an effort is made to use different terms for the dots and lines in graphs and directed graphs to keep track of which of these two mathematical worlds one is working in, but here I will use the generic terms vertices for the dots and edges for the line segments. Other examples of graphs and digraphs are shown in Figures 3 and 4. Such diagrams are useful in a wide variety of applications other than for the study of tournaments.

 

 

Note that in a (general) digraph one can have (directed) edges from i to j and j to i (Figure 4 (b)) and this is useful for some applications (e.g. streets that allow traffic in both directions). When one wants to model that something can occur in both directions, this can be done by using edges that have no arrows (where other edges have them), or by having arrows on the same edge in each direction. For the questions we will study here we will not need to have this flexibility.

It is helpful to have terminology for digraphs that enables us get insight into using them to model tournaments. First, we count the number of edges whose arrows point into a particular vertex v, and the number of arrows that point out of v. In the tournament graph context this would represent the number of players that beat v and the number of players that v beat, respectively. These two numbers are called the indegree (invalence) of v and outdegree (outvalence) of v, respectively.

In Figure 1 we get the following:

Vertex 1: outdegree 4; indegree 0

Vertex 2: outdegree 3; indegree 1

Vertex 3: outdegree 2; indegree 2

Vertex 4; outdegree 1; indegree 3

Vertex 5; outdegree 0, indegree 4

Probably not too may people would disagree about who should win this tournament, or how to provide a ranking of the players. One player won all the games that she played, one player lost only one game. One player lost all of the games he played. Ranking the players in the order 1, 2, 3, 4 5 seems natural.

Now consider the results of the tournament shown in Figure 5.
 

 

Here is the won-lost record of the players based on computing the indegrees and outdegrees for each player in this example.

Player 1: won 1, lost 3

Player 2: won 2, lost 2

Player 3: won 3, lost 1

Player 4: won 2, lost 2

Player 5: won 2, lost 2

Now the situation is not so clear cut. First of all notice a structural aspect of this tournament graph (Figure 5) which did not occur for the tournament in Figure 1. We can find three players (in this case players 2, 3, 5 provide an example, and there are others as well) with the property that player i beat player j, player j beat player k but player k beat player i. For some characteristics of objects or people this type of "relationship" cannot occur. If Josh weighs more than Bill, and Bill weighs more than Bob, Bob cannot weigh more than Josh. However, for teams beating other teams in a tournament this phenomenon is quite common. It is called a cycle or circuit. In Figure 5 there are other cycles. Can you find a cycle of length 4 and one of length 5?

Given a collection (set) of objects S there are many relationships that can be thought of that elements of S might share. For example, if S is a set of people, one can compare their weights, their heights, who can beat whom in Scrabble, whether a pair of people have the same hair color, etc.

Different relationships have different properties, and mathematicians have studied various properties these relations can have. This circle of ideas, having to do with "order relations," belongs to the large part of mathematics that has come to be called discrete mathematics.

If S is a set, and if a and b are two elements of S, we write a R b to denote that a has the relation R to b. Here are two different relations R and R* that can be defined on the set S consisting of 4 people: S = { Mary, Adam, John, Sally }

R = "is heavier than"

R* = "is older than"

Here are some properties of "relations" that come up often in practice:

(Reflexive): a R a for all a in S

(Symmetric): a R b implies b R a for all a and b in S

(Transitive): a R b and b R c implies a R c for all a, b, and c in S.

For many relations R that one can define on a set S, there may be elements of the set which are "not comparable," that is, the relationship R does not hold for particular pairs of elements in S. For example, suppose S is the set of subsets of the set {a , b , c} . Let R be the relation "subset of." Thus, if X and Y are two subsets of {a , b , c} , then X R Y if X is a subset of Y. Hence, since {a} is a subset of {a , b}, {a} R {a , b}. However, for the subsets {c, b} and {a , c} neither is a subset of the other so we do not have {c, b} R {a , c} or {a , c} R {c, b}. When this happens we say that R is a "partial order." When discussing teams in a tournament, when there are no ties in the individual matches, we can compare any pair of teams from the point of view of who beat whom. However, if we look at the won-lost records for the teams in the tournament and try to rank team i above team j when team i has a better won-lost record than team j, we may not be able to do this for some tournaments because i and j may have the same won-lost record as for teams 2, 4 and 5 for the tournament in Figure 5.

For each of these properties one can play the following game. For a particular relation R it either obeys one of these rules (axioms) or not. Thus, a priori, there might be 8 possible cases depending on whether or not relation R does or does not obey each of these three rules. So here is a mathematical game: Can you find an example which shows that each of these 8 cases can occur, or prove that a particular case is impossible? To get you started, suppose that the relation R = "not equal" where S is the set of integers, then R fails to obey being reflexive, is symmetric, and fails to be transitive, while R* = "equal" where S is the set of integers is reflexive, symmetric, and transitive.

While transitivity holds in many mathematical situations, we cannot expect to have the results of tournaments to not have cycles, triples (or longer cycles) of players where, in the tournament graph of the matches played, we have i beats j, j beats k, but k beats i. Hardly any season goes by where some "cub reporter" does not provide an example of what is sometimes called the "sportswriters' paradox." This involves some weak team, via some sequence of victory chains (weak team beats team A, which beats team B, ...) having a "path" of wins to the "highest and mightiest" team in the league. We all know many examples of relations which are not transitive but when the phenomenon is pointed out explicitly, it still often comes as a surprise!

Returning to the tournament in Figure 5 and the won-lost record for the 5 teams that we computed, perhaps you feel comfortable declaring Team 3 the winner because that team had the largest number of wins. However, if not only a winner but a ranking for the tournament is required, as mentioned above, we cannot "totally order" the teams based on their won-lost records because there may be teams which have the same won-lost records.

Consider an extreme case, the tournament in Figure 6.

 

For this tournament each of the teams won exactly two games and lost exactly two games. It is unclear how to use the won-lost information to declare a winner for this tournament. Below, we will consider if there is other information in the tournament digraph which would enable us to do this.

Suppose we have a list of the number of wins that the teams in a tournament had. I will refer to these as the scores of the tournament. Can we tell if these numbers can arise as the outdegrees of some tournament graph? Of course, if one knows the number of wins for each team one also knows the number of losses for each team because if there are n players, each player plays n-1 matches.

For example: Can 4, 4, 4, 3, 3, 2 be the scores of a tournament with six players?

One easy condition to check is that the sum of these numbers reflects the total number of matches that are won when one conducts a round robin tournament. If there are n teams, then each team plays n -1 others, and, hence, since in each match one of the teams must win (remember we allow no ties), we can conclude that the sum of the scores must be n(n-1)/2. Adding up the numbers above we see that the sum is 20, which is too big. These numbers cannot be the scores of a tournament with 6 players.

Can a score sequence have all equal entries? We've seen one example (Fig. 6), but is this always possible. Suppose there are n teams. We can use a bit of algebra to see if each of the teams might win w games. The total number of games played when n teams compete is:
 

Since there are no ties in each one of these matches, there must be a winner, so the sum of the scores we obtain is also n(n-1)/2. However, if each player is to have w wins, we also can conclude that the sum of the scores is n times w or nw. Equating these two quantities we get the equation:
 

As long as n is not zero we can divide both sides of this equation by n and, simplifying, obtain the relationship that:
 

This means that we can have identical scores for each player only in the case that n is odd (and bigger than 3), but doing this algebra does not guarantee that there actually is a tournament for every odd n where each player attains an equal number of wins. To finish the analysis one needs to actually construct examples for odd values of n (bigger than 3). Do you see a way to actually construct these examples? More specifically, for each odd n find a way to assign directions to the n(n-1)/2 edges of a complete graph with n vertices (n vertices, each joined to the others by exactly one edge) so that the outdegree and indegree of every vertex is equal to (n-1)/2. If you think you have a method that works in general, you can try it out on Figure 7:

 

 

Tournaments outside of sports

One of the early pioneers of understanding the structure of tournament graphs was H. G. Landau (1909-1966). Although Landau is sometimes described as a sociologist or psychologist, his academic training was as a statistician. Landau (his full name was Hyman Garshin Landau) got his doctorate in statistics in 1946 from the University of Pittsburgh. It appears that he worked during World War II at the Ballistics Research Laboratory and left there to join the Committee on Mathematical Biology at the University of Chicago. He was forced to leave the University of Chicago due to accusations by the House Un-American Activities Committee (HUAC), but did subsequently find work at Columbia University. However, Landau's interest in what are now known as tournaments did not arise from his studying of sports competitions. As so often happens in mathematics, the source of Landau's interest was something rather different. He was interested in animal behavior and the work he did grew out of dealing with the pecking orders of poultry (chickens). For each pair of chickens there appeared to be one of the two that in the chicken hierarchy was the dominant chicken with respect to that pair. Landau became interested in understanding the nature of these hierarchies for chickens and their properties.

Studying pecking orders in chickens is just one of the other reasons that studying tournament graphs is of interest beyond the world of sports. Over and over again, one of the reasons for pursuing mathematics for its own sake is that what one learns often turns out to be of value in a variety of settings that were not dreamed of when the original work was done. Even if new mathematics is developed for a particular reason, say, to try to design a system for ranking teams in a round robin tournament, it is very common for one to see related or distant other applications.

For example, the notation of a tournament graph also comes up in attempts by psychologists to see if human beings are consistent in their judgments or preferences.

Here is an experiment you can do for yourself to see how this might work. Consider these fruits: apple (A), Banana (B), Cherry (C), Grapefruit (G), Orange (O), Pineapple (P), Raspberry (R), and Strawberry (S).

For every pair of these fruits decide which one you prefer in that pair. You are not allowed to say that two fruits are tied. For example, in the pairing of cherry and grapefruit (assume that equal amounts by weight are available) you would rather have cherries. Do this without looking at what you said for prior pairs as you go through all the possible pairings. (This, by the way, requires 28 comparisons!)

Now complete the tournament graph associated with your paired comparisons. Here is a diagram that you can use for doing that (Figure 8). Your job is to compute the "winner" for each of the 28 different pairs of fruits one can consider, by deciding which fruit in the pair you like better, and then transfer the results to the diagram shown (Figure 8). (Only transfer your results to the diagram after you have completed all 28 paired comparisons.)
 

 

It might be fun to do this experiment with a friend and compare your two tournament graphs.

The first thing to look at is to see if you (or your friend) have any cycles in your graph. What would a cycle mean in this case? In our earlier analysis for teams it would have meant, for example, that there would be a collection of teams where A beat B, B beat C, C beat D, and D beat A. (Here we have a cycle of length 4 but one could have a shorter or longer cycle.) This kind of situation is very common. However, in the context of your personal preferences it would represent an "inconsistency" in the way you think about the fruits that you have judged. Most people, if they see a cycle in this type of situation, feel that they somehow made a mistake. When they look at the cycle they find one of the paired comparisons that they now wish to change, and say they made an error earlier.

The issue comes down to what we consider rational or consistent human behavior. For relationships that involve preference, many would argue that "transitivity" would be expected. One argument about the reason why transitivity may not hold has to do with detecting thresholds of change. Suppose I like coffee with one teaspoon of sugar but not with two teaspoons of sugar. If I am asked whether I am indifferent between coffee with one teaspoon of sugar, coffee with one teaspoon and 1 grain of sugar, coffee with one teaspoon and 2 grains of sugar, it may be that I will say I am indifferent. However, if one adds enough grains of sugar they eventually amount to another whole teaspoon of sugar. When adding one grain of sugar at a time, I probably will not be able to say where the switch will occur between one teaspoon of sugar with x extra grains of sugar and (x+1) extra grains. I may not have "switched" preference and I prefer coffee with one teaspoon of sugar to coffee with two teaspoons of sugar. However, there must be some place in between these two choices where the transition between indifference and preference changes.

In his study of pecking orders for chickens, Landau discovered a very charming and appealing result about scores of tournaments. He was able to say explicitly when a sequence of numbers does or does not represent the scores that could arise from the wins of teams in a sports tournament, rankings of chickens, or a person's preferences for fruits.

Landau's Score Sequence Theorem:

Given a sequence of integers (s₁, s₂, s₃, ..., s_n ) arranged so that they are in non-decreasing order (the integers get no smaller as one moves to the right) then these numbers can arise as the scores of teams in a tournament with n teams if and only if:
 

for each k = 1, 2, ..., n where equality must hold when k = n and denotes the number of ways of choosing 2 things from k (a binomial coefficient). Landau's results allow one to see if there is a tournament with scores: 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 (nine 4's). Since (9x8)/2 = 9x4 (the case n = k = 9, above), and the other sum conditions hold, the answer is yes. Thus, we know that for 9 teams we can have a tournament which ends in a 9-way tie with each team winning 4 games. This is related to the question asked above about actually placing arrows on a complete graph on 9 vertices so that the outdegrees are all 4. We now know the answer is yes, but because Landau's theorem is an "existence" theorem it does not actually tell us how to do the labeling so that we achieve the goal of outdegree 4 at each vertex.

Other approaches to rankings

Consider the tournament graph in Figure 9.

Work out the won-lost record for each player in this tournament and you will see that based on most matches won, there would be a tie. One way to construct a ranking would be to construct a sequence of teams where each team in the sequence beat the next team. For example, we have this string of wins: 6, 1, 5, 7, 3, 4, 2. This list means that 6 beat 1, 1 beat 5, ...., 4 beat 2. Unfortunately, there are other such strings! We also have this sequence: 6, 3, 4, 2, 7, 1, 5, 2. If all the vertices of a digraph (or graph) can be listed in a tour moving from one to another along (directed) edges so that all the vertices are listed without repeats, then the tour is known as a Hamiltonian path. The name reflects tribute to an early pioneer of graph theory who studied this idea, William Rowan Hamilton, an Irish mathematician, perhaps most famous for his work on quaternions.
 

 

Not only does the tournament in Figure 9 have directed paths that start at a particular vertex and which run through all the other vertices without repeats, Figure 9 also has a Hamiltonian circuit (cycle) which is a tour that follows directed edges, starts and ends at the same vertex, and runs through the other vertices exactly once. Such a circuit in this case would be: 1, 2, 3, 4, 5, 6, 7, 8, 1. Note that player 1 did not win that many games. Player 1 only won two games, while players 5 and 6 won 4 games. When a tournament graph has a Hamiltonian circuit, it also has Hamiltonian paths that start at any of the vertices of the tournament graph. For example, 3, 4, 5, 6, 7, 8, 1, 2 is a Hamiltonian path that starts with team 3. Not every tournament digraph has a Hamiltonian circuit. For example, the tournament graph in Figure 1 has no Hamiltonian circuit and, in fact, no directed circuits of any length. Note, however, that every tournament always has a directed Hamiltonian path. The realities here suggest that this may not be a good approach to ranking teams in a tournament. Many other ideas have been put forward including the use of methods from linear algebra of the kind that have been of value in ranking web pages. The fact that tournaments can have cycles may seem disconcerting but such tournaments are the norm rather than the exception. In fact, as the number of teams grows, if one looks at the number of non-isomorphic tournament graphs involving n teams, the portion of such tournaments with cycles gets closer to one. (A random tournament is very likely to have cycles.)

A tournament digraph is called reducible if one can partition its vertices into two non-empty sets X and Y so that all the teams in one of the sets, say X, beats all of the teams in Y. Otherwise the tournament is called irreducible. With regard to circuit structure there is the following surprising theorem.

Theorem (Leo Moser and Frank Harary)

Each vertex in an irreducible tournament involving n teams is contained in some m-cycle, where m is 3, 4, ...., n.

Psychologists, mathematicians, and statisticians have studied cycles in tournaments because of the insights that the existence of cycles give in "inconsistencies" of things such as the way preferences are expressed when people rank candidates for office or fruits in pairs. You might enjoy the challenge of trying to find a way to put directions on the edges in the graph below so that the number of different 3-cycles is as large as possible.

 

 

It is worth noting that as the number of teams in a tournament goes up, the number of inequivalent (non-isomorphic) tournament digraphs grows rapidly. Here are the beginning statistics:
 

number of teams	inequivalent tournaments
2	1
3	2
4	4
5	12
6	56
7	456
8	6880
9	191536

Remember that non-isomorphic tournaments might have the same score sequence, so determining the number of different score sequences with n teams is a different problem. The table below shows the number of different score sequences which can arise for n teams. Many different tournaments give rise to the same score sequence as the number of teams grows.
 

number of teams	different score sequences
2	1
3	2
4	4
5	9
6	22
7	59
8	167
9	490

Mathematicians, political scientists, psychologists and computer scientists, as well as other scholars, continue to explore many different aspects of tournaments because there are so many traditional and new environments where ideas related to tournaments come into play. While the mathematics used is often very technical, the questions they are answering are often easy to state and understand. Sports fans await further progress!

References

Cook, W. and I. Golan, M. Kress, Heuristics for ranking players in round robin tournaments, Computers and Operations Research 15 (1988) 135-144.

Fulkerson, D., Upsets in round robin tournaments, Canadian J. Math. 17 (1965) 957-969.

Gross, J. and J. Yellen, Handbook of Graph Theory, CRC Press, Boca Raton, 2004.

Harary, F. and L. Moser, The theory of round robin tournaments, Amer. Math. Monthly, 73 (1966) 231-246.

Kano, M. and A. Sakamoto, Ranking the vertices of a paired comparison digraph, SIAM J. on Algebraic and Discrete Methods 6 (1985) 79-92.

Landau, H. G., On dominance relations and the structure of animal societies. III. The condition for a score structure, Bull. Math. Biophys. 15 (1953), 143-148.

Laslier, J.-F., Tournament Solutions and Majority Voting, Springer, Berlin, 1997.

Maurer, S., The king chicken theorems, Math. Mag. 53 (1980) 67-80.

Moon, J., Topics in Tournaments, Holt, Rinehart, and Winston, NY, 1968

Narayana, T. V. and Best, D. H. "Computation of the Number of Score Sequences in Round-Robin Tournaments." Canad. Math. Bull. 7, 133-136, 1964.

Reshevsky, N., Hyman Garshin Landau, Obituary, Bulletin Mathematical Biology
29 (1967) 189-190.

Reid, K., On sets of arcs containing no cycles in a tournament, Canadian J. Math.. 12 (1969) 261-267.

Reid, K., Majority tournaments: sincere and sophisticated voting decisions under amendment procedure, Math. Soc. Sci. 21 (1991) 23-28.

Reid, K., The relationship between two algorithms for decisions via sophisticated majority voting with an agenda, Discrete Appl. Math. 31 (1991) 23-28.

Reid, K., Every vertex a king, Discrete Math. 28 (1982) 93-98.

Reid, K., Tournaments: scores, kings, generalizations and special topics, Congressus Numer. 115 (1996) 171-211.

Reid, K. and L. Beineke, Tournaments, in Selected Topics in Graph Theory, Academic Press, London, pp. 169-204.

Ruskey, F. "Information on Score Sequences." http://www.theory.csc.uvic.ca/~cos/inf/nump/ScoreSequence.html

Rubenstein, A., Ranking the participants in a tournament, SIAM J. Applied Math 38 (1980) 108-111.

Ryser, H., Matrices of zeros and ones in combinatorial mathematics, in Recent Advances in Matrix Theory, U. of Wisconsin Press, Madison, 1964, pp. 103-124.