Out before the table says so

Every sports section prints a table with a column saying how far each team is behind the leader. Late in a season a team is declared mathematically out once its wins, plus all its remaining games, cannot reach the leader’s present total. That test is wrong. It says a team is alive when it is already dead, because it treats each rival separately, when in fact rivals must play one another, and those games have to be won by somebody.

The right test seems to need a search through every result of every remaining game, and with 27 games left that is as many as two to the power 27 outcomes. In 1966 Alan Schwartz noticed that no search is needed at all. The question is a single maximum flow. And the minimum cut that comes with the answer is a certificate that anyone can check by hand, a set of teams and one average.

A team that is out at 83 #

The smallest example is four teams, near the end of a season.

Atlanta has 83 wins. Montreal has 77 and three games left, so it can reach only 80. That is the elementary kind of elimination, and it can be read from the table. Philadelphia has 80 and three left, so it can reach 83. On the table it could tie for first.

But look at the games between Atlanta and New York, of which six remain. If Philadelphia is to finish first it needs Atlanta to win no more games, since Atlanta is already at 83. So New York has to win all six of them. New York has 78, and six more wins would take it to 84, which is past Philadelphia’s limit. There is no way out. Somebody passes 83. The conclusion holds whatever else happens, and no column of the table shows it, since it comes from one game’s outcome being forced to land on someone.

This is the whole phenomenon in its smallest form. A rival’s capacity to absorb wins is limited, and the wins that must be absorbed are fixed by the schedule. Is there enough capacity for all of them? That wording makes it sound like a transport problem, and that is exactly what it is.

Wins as a commodity #

Fix a team $x$, and let it win all of its remaining games, the best it can do, reaching a total $W$. Now look at the games the other teams play against one another. Every such game produces one win, which has to go to one of the two teams playing it. Each rival $i$ with $w_i$ wins already can absorb at most $W - w_i$ more, or it passes $x$. So build a network:

• a source sends $g_{ij}$ units to a node for each pair of rivals, one unit per game they have left;
• each such node sends its units on to either of its two teams;
• each team $i$ sends at most $W - w_i$ units to the sink.

If some flow saturates every edge out of the source, then all the games have been assigned a winner with nobody passing $x$. Flows of whole numbers exist whenever real ones do, and that is the integrality that made flow theory so useful for counting, so such a flow really is a season’s results. If no such flow exists, then no such results exist. A search through all $2^{27}$ results has become a computation on a network of about a dozen nodes, with the fast methods of the augmenting-path story to finish it in microseconds.

The first figure is that network for a harder example. Detroit has 49 wins and 27 games left, for a best total of 76. New York, at 75, is the leader, and Baltimore, Boston and Toronto are at 71, 69 and 63. Those four teams have 27 games left among themselves. The flow fits 26 of them, as the labels in the left column show. One win has nowhere to go, and Detroit is out, even though the table says it could still pass everyone.

The cut is the explanation #

A flow algorithm’s output can be read in a much better way. When a flow fails to fill the source edges, the search for augmenting paths finds a minimum cut, and that cut names a set $S$ of rivals. What that set means can be stated without any mention of networks. Between them, the teams in $S$ already have $w(S)$ wins and have $g(S)$ games left against each other. Each of those games adds exactly one win to the group, whatever happens. So the group finishes with at least $w(S) + g(S)$ wins in total, and at least one team in the group finishes with at least the average

$$\frac{w(S) + g(S)}{|S|}.$$

If this average is more than $W$, then $x$ is out.

For Detroit, the cut names all four rivals: $75 + 71 + 69 + 63 = 278$ wins, plus 27 games among themselves, makes 305, and 305 divided by 4 is 76.25. Detroit can reach only 76. That is a proof that fits on a napkin. It does not require any understanding of flow, or a computer, and anyone can verify it from the league table in a few seconds. Philadelphia’s cut, in the smaller example, is the pair Atlanta and New York: $83 + 78 + 6 = 167$, with an average of 83.5 against a best of 83.

The theorem, due to Alan Hoffman and Theodore Rivlin in 1970 and implicit in Schwartz, says that a team is out if and only if some set of rivals has such an average above its best total. It is the max-flow min-cut theorem in baseball clothes. That is the valuable part of it, in the same way that the deficiency in Hall’s theorem is a certificate of the absence of a matching. Nothing can be simpler than a search that fails and hands over a reason, and a reader does not have to trust any claim about 2 to the power 27 results.

One striking feature is that the certificate has no reason to name teams near the top. In the small example, the set is two teams, while in Detroit’s it is all four, and Toronto with 63 wins is one of them. Toronto is not close to Detroit’s total, but its games have to be played against the others. A team fifteen games ahead may be irrelevant, and a team far behind can be what closes the door, through the games it must lose to the others.

The same condition, on a table of scores #

The average has an older relative. A tournament in which every pair of players meets once and every game has a winner produces a list of scores, and H. G. Landau asked in 1953 which lists can occur. His answer is that a sorted list of scores is achievable exactly when the $k$ lowest scores add up to at least $\binom{k}{2}$ for each $k$, with equality at the end. Those $k$ players have played $\binom{k}{2}$ games among themselves, each of which added a win to the group, so their total cannot be smaller. It is the certificate above, read in the other direction. There the games within a set force a large average against a ceiling, and here they force a large sum against a floor.

Both statements have the same one-line reason, and both are consequences of the same theorem. In each case a global possibility, that a whole season’s results exist, has reduced to a local count on subsets, with no need to construct anything. This is what a min-max theorem does whenever it applies, and it is why flow keeps turning up in problems that do not sound like transport.

Testing it against every result #

Schwartz’s reduction is a short argument, and it is easy to get a detail wrong in an implementation, such as forgetting that a rival might already have passed $W$, in which case the capacity would be negative. So it was tested against the definition. In each of 500 random leagues of six teams, every team was tested in two ways, by one maximum flow, and by a complete recursive search through every split of the games among the others.

They agree on all 3,000 teams. So do the four teams of the small table. Of those 3,000, 1,924 are alive, 985 are out at a glance, and the remaining 91 are out only by flow. Every one of those 91 was also confirmed by the certificate’s average, computed from the cut. That means the “games behind” column is wrong for 3.0% of the teams in such a league, or for 4.5% of those it calls alive. These are the teams that will be told by a newspaper that they still have a chance when they do not. Random leagues are not real leagues, and the figure is about the size of the discrepancy in one simple model.

When it shows in a season #

The effect can also be seen over the course of a season, in simulated leagues.

For most of a season, the two are the same. Nobody is out for the first twenty rounds or so. Then the true share climbs a little before the plain one. The widest gap in these seasons is 3.5 percentage points, at round 29 of 40, and half the teams are out by round 34 by flow against 35 at a glance. So the gain is about one round, and it is largest in the last quarter of a season. As schedules are often arranged so that division rivals play each other at the end, real leagues could show a larger difference than this. The simulation’s schedule is uniform and carries no such structure, so it is a modest estimate.

A surprise appears if the question is turned round. Kevin Wayne showed in 2001 that there is a single threshold: there is a number $W^*$ such that a team is eliminated exactly when its best possible total is less than $W^*$. So eliminations happen in order of best possible total, with no exceptions. That is not obvious from the definition, since one could have imagined that a team with a higher best total might still be undone by an unfortunate schedule among its rivals. Wayne’s theorem also makes the whole league’s computation much faster, because a binary search over one number replaces a separate flow for each team.

Three points for a win #

Everything so far relies on each game producing exactly one win. That is why a game can be a node with one unit to send to either of two teams. What if the rule is different? In football, a win earns three points, and a draw earns one for each side. So a match yields either 3 points to one team, or 2 points split evenly.

This small change has a large consequence. Thomas Kern and Daniël Paulusma, and independently Bernholt, Gülich, Hofmeister and Schmitt, showed that with the rule of 3 and 1 the elimination question is NP-complete. It is a problem that no known algorithm solves efficiently, at the same level of difficulty as the satisfiability problem, once more than a very few teams are in the league. The older rule of 2 points for a win and 1 for a draw is easy, since there every game adds exactly 2 points, and that is the essential property: each game contributes a fixed total. With 3 and 1, a game can add either 2 or 3, and the total points in the league are no longer fixed by the schedule. The flow breaks because the amount of commodity depends on decisions made along the way. Football moved to 3 points for a win in the 1980s and 1990s in order to encourage attacking play, and it moved the question of whether a team is out from easy to intractable. Nobody had that in mind. Fortunately a real league is small enough for an exact search with integer programming, and websites do this.

That shows how much the elegant reduction depends on something easy to overlook. The relevant algebra is not about teams at all: it is the fact that the flow network has integer capacities, with each game being a fixed quantity to route. Changing the sum into a choice breaks it. It is one of the cleanest examples of a sharp boundary between easy and hard, in the sense that a very slight change of rules takes it across.

What a season’s flow leaves out #

The flow says who is mathematically out. It says nothing about who is likely to win, and a team alive by a single unlikely sequence of results is, for practical purposes, out too. The network assumes that every remaining game will be played and has exactly one winner, which rules out cancelled games and ties. The certificate’s average requires a set of teams, and for a very large league the set need not be small or easy to spot by eye. In addition, the figures show the flow at one moment of the season. Whether the schedule’s order could be changed to delay the moment of elimination is a different and more delicate question, and it is something league planners really do care about.

The simulated seasons are only a model. Strength differences were assigned by simple random draws, and each match was independent. Real schedules have divisions, and the larger effects of those were not modelled.

What was computed and what was quoted #

Flows were computed exactly, by shortest augmenting paths with integer capacities, and their results were tested against exhaustive search on the small table and on 3,000 random-league teams. The certificates were computed from the residual graph, and the average was verified to exceed each team’s best total in every deep case. Season results are from 60 seeded simulations, so the percentage figures carry sampling noise of perhaps half a point at their widest.

The theorems of Schwartz, Hoffman and Rivlin, and Wayne, and the NP-completeness results, are quoted. The examples of Detroit and Atlanta are widely used teaching examples, due in this form to Wayne, and they are not offered as records of actual seasons. Wayne’s threshold was not separately computed here, although the flow test’s outcomes never contradicted it on the table’s teams.

Still open: the hard version in practice #

Which fixtures make the three-point question hard? The NP-completeness proofs use artificially built leagues. Bernholt and others showed it is already hard with few teams in contention, under suitable schedule conditions, and Kern and Paulusma found classes of leagues that can be solved in polynomial time. Exactly what a real round-robin schedule does to the difficulty is only partly mapped: a complete round-robin with a few rounds left may behave quite differently from a worst-case instance. Practical exact solvers do cope with all real leagues, and no theorem says why.

Similar questions arise for tournaments with knockout rounds, in which the question of which player can possibly win under a suitable seeding is the tournament fixing problem. Whether a given player can win a knockout under some bracket, given all pairwise results, is NP-complete in general, as Aziz and others proved, and its parameterised complexity has been an active area of study. These all ask how much of the future is forced by the structure of what remains. Only for the simple one-win-per-game league does an elegant single flow answer it, and that is something to be noticed rather than taken for granted.

A commodity with a fixed total #

A game is one unit of a commodity that must be delivered to one of two teams, and each team has limited room; a team is out exactly when the rivals do not have enough room between them. That turns a search through two to the power 27 results into one flow, and the cut hands over a set of teams and an average that anyone can check.

It depended on one piece of luck in the rules. Every game must add the same total, and then a league’s wins form a fixed quantity to be routed. With the modern football rule that is no longer so, and the question stops being easy. The same table, with one column changed from wins to points, moves from microseconds to NP-complete.