Due to reasons, I found myself thinking about the following problem:

We have a two-player game with players \(1, \ldots, n\). Player \(i\) beats player \(j\) with probability \(A_{ij}\) ( so \(A_{ij} = 1 – A_{ji}\)).

We wish to run a tournament with these players. The tournament is played as a sequence of games between pairs. The loser of the two drops out, and we choose another pair from the remainder until there is only one left (assume that a player winning any game they participate in is not affected by previous games they’ve played).

My question is this: How much can we influence the result of the tournament by changing which pairs play against eachother?

The short answer is “a lot”. There are clear upper and lower bounds on a given player winning (the upper bound on player \(i\) winning is \(\max\limits_{j} A_{ij}\) – they don’t play until the very end and then play against the player they are most likely to beat – while the lower bound is \(\prod\limits_{j} A_{ij}\) – they play against every other player\), but there’s a lot of variation in there and these bounds won’t be achievable for all tournaments.

So how to resolve this question? Well, I wrote some code. Have ye a nice little python module for calculating how to rig tournaments.

(Well, it doesn’t actually tell you how to rig tournaments, though it could easily be modified to do so. Instead it tells you the probability of victory under various strategies. Some of those strategies are “recursively maximize this function”).

I’m going to explore this more later, but if I write any more on this right now I’ll be late to work, so in the meantime this is just a “Here’s some code! If you’re interested in this question, feel free to play around with it”.