Sports Elimination and Maximum Flow

Status
Live
Title
Sports Elimination and Maximum Flow
Date
28 Sep, 2021 ⸱
Excerpt
Published
Sep 28, 2021
Tags
exportober
exposition
lecturenotes
Feature on homepage
With IPL going on, I figure this one is on-topic.
I believe IPL is overall a double round-robin tournament, which is to say that every team plays off every other team two times; hence with eight teams playing there are 14 matches per team and 56 matches total, not counting the playoffs.
Let's say we are at some intermediate stage of the tournament, and we ask the eternal question (at least this was the only question I had in mind when I was following the tournament years ago):
Does RCB stand a chance to at least tie* for top place at the end of the league matches?
*We assume a simple points system — there are no ties in any individual games, and the number of points a team has is simply the number of matches it wins. At-least-a-tie for the top place after the league games simply means that we would like that no other team wins strictly more matches than RCB when we are done.
And then come the twisty calculations and endless decision trees:
...so yeah, if KKR lose to CSK in the match on Friday, and DD lose to MI next Monday, and it rains on Tuesday, and uhh, of course, RCB wins all its remaining matches, of course, and further if...
So yeah, this is the problem we want to solve. Either determine whom to bribe hypothetical fates for all remaining matches so that RCB emerges at the top (possibly among others), or provide evidence that even divine intervention won't save the team this time no matter which combination of outcomes plays out, there is always a team that has more wins than RCB.
So we're going set this up as an instance of network flow! To begin with, let's get some routine things out of the way: since we are allowed to work up any imagined fate for the remaining matches with no particular obligation to be realistic about it, we are going to begin by assuming† that RCB wins all remaining matches. Let be RCB's most optimistic score — this is the sum of RCB's current score in the tournament so far and the number of matches it has remaining. For any other pair of teams and , let denote the number of matches that are yet to be played between said teams.
†This is what you might recognize as a greedy choice from an algorithms point of view, and this is one of those rare occasions where greed is good. It's fine.
Here's the — once you think about it — fairly natural construction:
  • Introduce a vertex representing every team (other than RCB)
  • For every pair of teams and (other than RCB), introduce a vertex .
  • Add a source and an edge from the source to every vertex with a capacity of .
  • Add the edges and — these edges have infinite capacity.
  • Add a sink and an edge from every to the sink with capacity _____.
The last capacities.
If the team has won matches so far, then this capacity should be .

It is not hard to see that if we have games remaining altogether (not counting the ones involving RCB), then RCB has a winning chance if and only if the flow network above admits a flow of value .
The crux of the matter is to look at how the incoming flow of into gets split across the two edges to and : the flow on the edge determines the number of the matches that must win, and the rest go to . All the incoming flow into is representative of the number of matches team wins under this prediction, and if that can be pushed out of the edge , then the number of wins from future matches for is at most , making the total number of wins and keeping RCB's fate safe.
By an argument in a similar spirit you can see how a set of predictions that keep RCB on top translates to a flow of value as well. To be clear, this rambling is far from an actual proof*, but hopefully it conveys the main ideas to anyone who'd like to cobble one together.
*For a more formal exposition, although in the entirely different setting of baseball, you might want to look at Section 11.6 of Erickson's Algorithms (PDF).

What if the maximum possible flow is less than — we know RCB is not going to make it to the very top, but how do you convince your non-network-flow-loving-RCB-fans of this news? The first option, of course, is to not tell them. But the second — if you want some company in sadness — is to see if the flow network can be now used to produce concrete and understandable evidence for why RCB won't be making it.
Hint: use the maxflow-mincut duality.
More food for thought:
  • Can you adapt this system to account for draws?
  • If RCB is going to make it, what is the smallest number of matches whose fate you should try to fix imagine going the other way so as to prevent this outcome?