Max-flow Min-cut and Baseball End-of-Season Elimination

Introduction

In the baseball end-of-season elimination problem, we focus on a league of n teams and the goal is to determine which of these teams are mathematically eliminated. When there does not exist any possible scenarios in which a given team can come in first place, or tie for first place, they are said to be eliminated. In this report, we assume all matches happen and none will end in a draw. In some cases, determining if a team is eliminated is trivial. Such as if Team i has less wins and matches remaining than Team j has wins already. In this case, even if Team i wins all of their remaining matches, they will still have less wins than Team j, regardless of outcomes for the remaining matches for Team j. However, not all cases are this simple. Sometimes there exists a scenario where Team i can win more matches than Team j, but this requires Team j to lose all, or most, of their remaining matches, forcing Team k to win enough matches to surpass Team i in the rankings.

Example 1 of a division standing for a baseball league. Each row indicates a specific team in the division along with the number of matches that team has won, lost, remaining in total in the season, and remaining against each team in the division.

Background

Directed Graphs

Maximum Flow Problem

The flow of an s-t graph can be defined as the difference in information leaving and entering s, or equivalently, the difference in information entering and leaving t. All other nodes must conserve this flow of information, hence the condition specified in our definition of s-t graphs. The goal of the maximum flow problem (MF) is to maximize the flow of an s-t graph by modifying the weights xₑ for each eA. When for some, or all, eA, there exists an upper bound, or capacity, denoted uₑ, on each xₑ. We say an edge is saturated if xₑ = uₑ. Combining this objective and these constraints, we can formulate (MF) as

Minimum Cut Problem

The Max-flow Min-cut Theorem

The max-flow min-cut theorem states that given an s-t graph, the optimal values to (MF) and (mC) are equivalent. The optimal solution to (mC) gives us the minimal set of edges, in terms of capacity, in which removing would disconnect s and t. In other words, this is the minimal set of edges such that all information travelling from s to t must move across, therefore any solution to (MF) will saturate these edges. If a solution to (MF) does not saturate these edges, then there either exists a more minimal cut that creates a tighter bottleneck for the flow, which is a contradiction as we have an optimal solution to (mC), or there exists a more maximal flow as the removal of these edges disconnects s and t, which is also a contradiction as we have an optimal solution to (MF).

Methods

In order to relate the previous optimization problems to the original baseball end-of-season elimination problem, we must first define the graphs that will be used. For Team i we define a source node s, a node for each possible match-up between any two teams in the division excluding Team i, which we will call match nodes, a node for each team in the division excluding Team i, which we will call team nodes, and finally a terminal node t. For a division of n teams, this gives us a total of (n² - n + 4) / 2 nodes. Note that we assume n ≥ 3. If n = 2 then determining if a team is eliminated is trivial and does not require this method. Next for each j, ki we create edges going from s to the match node corresponding to Team j versus Team k with a capacity of the remaining matches between Team j and Team k. Next we create two edges going from the match node corresponding to Team j versus Team k, one to the team node corresponding to Team j and the other to the team node corresponding to Team k with infinite capacity. In this implementation we simply use a constant capacity of 1000 for each of these edges. Lastly we create an edge going from the team node corresponding to Team j to t with a capacity of wᵢ + rᵢ - wⱼ for each team node, where wᵢ is the number of wins Team i has, rᵢ is the number of remaining matches Team i has, and wⱼ is the number of wins Team j has. Note that if this capacity is negative, Team i cannot obtain more wins than Team j currently has and therefore should be eliminated without any further explanation so we need not consider this scenario here. This capacity represents the number of games Team j can win without surpassing Team i in the rankings.

# Initialize the DiGraph using LightGraphs
# Source + all possible matches + each team + sink = # of nodes
# Source = node 1, terminal = node (n^2 - n + 4) / 2
flow_graph = LightGraphs.DiGraph((n^2 - n + 4) / 2)
#Initialize nxn capacity matrix
capacity_matrix = spzeros(Int, (n^2 - n + 4) / 2, (n^2 - n + 4) / 2)
for k in match_nodes
# Connect the source node to each match node
# with capacity equal to the number of those matches left.
LightGraphs.add_edge!(flow_graph, 1, k)
capacity_matrix[1, k] = matches_left[k]
for j in teams_in_match
# Connect the match nodes to the teams in each match
# with large enough capacity.
LightGraphs.add_edge!(flow_graph, k, j)
capacity_matrix[k, j] = 1000
LightGraphs.add_edge!(flow_graph, j, (n^2 - n + 4) / 2)
capacity_matrix[j, (n^2 - n + 4) / 2] = wins[i] + left[i] - wins[j]
end
end
part1, part2, v = LightGraphsFlows.mincut(flow_graph, 1, n_nodes, capacity_matrix, BoykovKolmogorovAlgorithm())
cut_teams = []
# Check which teams are in part 1 (the source side).
for nodes in part1
if node == team_node
cut_teams = [cut_teams; node]
end
end

Computational Experiments

(Left) The graph for Philadelphia with the edges are labelled with the maximal flow results, where edges with zero flow have been removed for simplicity. (Right) The graph for Philadelphia, where the red dashed line represents cutting the graph into two partitions based on the results of the minimum cut.
Example 2 of a division standing for a baseball league.

Quidditch League Example

https://www.hp-lexicon.org/thing/ministry-of-magic/department-of-games/british-and-irish-quidditch-league/

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Chris Beeler

Chris Beeler

I am a PhD student in Mathematics and Statistics at the University of Ottawa. My research interests are reinforcement learning, dynamic programming, and POMDPs.