Checking whether the win-loss standings of a league are possible

Question

You're hosting a 1 v 1 basketball league with a game schedule. At the end of the league you have each player report their supposed win-loss record (there are no ties), but you want to check whether the proposed standings were actually possible given the schedule.

For example: you have four players (Alice+Bob+Carol+Dave) and your schedule is a simple round robin. The reported standings [A: 3-0 B: 1-2 C: 1-2 D: 1-2] and [A: 2-1 B: 1-2 C: 1-2 D: 2-1] would be possible, but the standing [A: 3-0 B: 0-3 C: 0-3 D: 3-0] would not be.

Now suppose the schedule is instead a 3 game head to head between Alice+Bob and Carol+Dave. The reported standing [A: 3-0 B: 0-3 C: 0-3 D: 3-0] is now possible, but [A: 3-0 B: 1-2 C: 1-2 D: 1-2] would no longer be.

(The schedule does not need to be symmetric in any way. You could have Alice only play against Bob 10 times, then make Bob+Carol+Dave play 58 round robins against each other.)

Problem: Given a schedule with k participants and n total games, efficiently check whether a proposed win-loss standings could actually occur from that schedule.

---

The O($2^n$) brute force method is obvious, enumerate all possible game outcomes and see if any match the proposed standings. And if k is small increasing n doesn't add much complexity - it's very easy to check a two person league's standings regardless of whether they play ten games or ten billion games. Beyond that I haven't made much headway in finding a better method, and was curious if anyone had seen a similar problem before.

Answer 1

This can be modelled as a Max-Flow problem.

As a preprocessing step, make sure that the number of games is equal to the sum of the number of wins (if not, you know something is wrong).

Let $G$ be a set of vertices corresponding to the games played, and $P$ a set of vertices corresponding to the players. Let $s$ and $t$ denote two additional vertices (source and sink).

Now for every game $g\in G$ played between $p1\in P$ and $p2\in P$, add an edge from $s$ to $g$ with capacity $1$ and edges from $g$ to $p1$ and $g$ to $p2$ also with capacity $1$. This models the fact that the game can give one point to either player.

Then for every player $p\in P$ add an edge from $p$ to $t$ with capacity equal to the reported number of wins for player $p$. This models the fact that this player should win at most this number of games.

It is easy to see from here that if the reported scores are possible, there will be a saturating flow from $s$ to $t$ and reciprocally. So all you need to check is if the maximum $s,t$-flow in this graph is equal to the number of games played.

Alternatively, you could also have a graph with one vertex per game and a number of vertices for each player corresponding to the number of wins, connect them the same way as before, and look if the number of edges in a maximum matching is equal to the number of games (but this is almost the same thing really).