8
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Very nice! And rather than have a node for each of the m separate games between P1 and P2, could you consolidate all of them into one node (a "series" node) with edge capacities m instead of 1? $\endgroup$ – ManyCookies Aug 3 at 4:48
  • $\begingroup$ In the preprocessing, you should also check that the number of wins + losses reported by each player equals the total number of games that player has played. $\endgroup$ – Ilmari Karonen Aug 3 at 13:49
  • $\begingroup$ Also, while your answer seems technically correct, note that in practice solving the max-flow problem is neither necessary to catch simple cheating (where players only cheat by claiming extra wins and/or fewer losses; the preprocessing alone will catch that) nor sufficient to catch more subtle cheating (where e.g. Alice loses a match to Bob, but they both agree afterwards to report it as Alice's win anyway; there's no way to detect that using only the data given). But that's an issue with @ManyCookies's problem as stated, not with your solution. $\endgroup$ – Ilmari Karonen Aug 3 at 13:55
  • $\begingroup$ @ManyCookies : Sure, that should also work :) $\endgroup$ – Tassle Aug 3 at 16:25
  • $\begingroup$ @IlmariKaronen : Yeah you can add any number of preprocessing steps you want to make things go faster in practice but these are not strictly necessary, while the preprocessing step I proposed was mainly to make the checking of the max-flow condition easier (without it you would need to check that the flow is saturating at both ends, which would boil down to that preprocessing step). $\endgroup$ – Tassle Aug 3 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.