A non-transitive tournament

I have a reason for thinking about this, but don’t want to get in to the philosophy behind it, so let this post stand on its own as just a neat thing.

Consider the following game: You have a tournament of players. Each player is a rock, a paper or a scissors. Victory is determined in the usual way, with a coin flip or some other arbitrary decision between players of the same type (we’re only going to consider tallies of the number of players of each type, so it doesn’t matter who wins).

A tournament is played as follows: Pick two players at random. They fight. The loser drops out. The tournament is one when only one player is left.

Now, consider a tournament with one scissor and many papers but no rocks. The scissors is a guaranteed winner. Now add a rock. What happens? The scissors still probably wins – the paper is likely to kill the rock before the rock kills the scissors. But what happens as you keep adding rocks?

When you add the first rock, obviously it introduces the possibility that paper can win: The rock can kill the scissors, at which point the remaining paper obliterates the rock. As you add more rocks this becomes more likely to happen and scissor’s chance of winning drops.

There turns out to be a nice formula for the probability of scissors winning in this case. If we write \(S(r,p,s)\) as the probability of scissors winning with r rocks, papers and s scissors then \[S(r, p, 1) = \frac{p(p+1)}{(p + r)(p + r + 1)}\]

(Unfortunately I don’t have a nice proof of this. I arrived at it empirically with the aid of wolfram alpha, then proved it inductively using the recurrence on the probabilities)

So as you can see, the probability of victory for scissors monotonically decreases towards zero as \(O(\frac{1}{r^2})\).

So scissors is likely to lose after a few rocks have been added (the probability drops to half or less when \(r \geq \frac{1}{2}\left(\sqrt{8 p^2 + 8p + 1} – 2p – 1\right)\). Now you know), but what is the probability of a rock victory?

Not so good it turns out. As far as I can tell there’s no nice general formula for rock and paper victory probabilities, but I’ve done some calculations for simple cases and I have some code for solving the general case and I’m sorry to report that the chances of success for rock are looking pretty grim.

The problem intuitively is that with a lot of rocks you’re likely to kill off the scissors before it manages to kill off all the paper. Empirically, the best number of rocks appears to be \(\lfloor p / 2 \rfloor + 1\), but even then the probability is pretty low.

Here are some graphs of the probabilities of rock victories:

With 1 paper:

With 2 paper:

With 10 paper:

Empirically it seems to be the case that the single paper scenario is the only one where rock is ever tied for victory probability, let alone winning, and is also the only case where it ever is more likely to win than scissors.

That’s about it in terms of what I can prove or demonstrate about this problem. I’m interested in it, but it seems harder to get a handle on than I’d expect (or I’m worse at this sort of maths than I think I should be. Probably both). As a parting shot, I’ll leave you with some python code to calculate the probabilities:

class ProbabilityTable:
  def __init__(self):
    self.table = {}
  def S(self, rock, paper, scissors):
    if scissors == 0: return 0.0
    if rock == 0:     return 1.0
    if paper == 0:    return 0.0
    key = (rock, paper, scissors)
    if key in self.table:
      return self.table[key]
    total = rock + paper + scissors
    result = (self.S(rock - 1, paper, scissors) * rock * (rock + 2 * paper - 1) + 
              self.S(rock, paper - 1, scissors) * paper * (paper + 2 * scissors - 1) + 
              self.S(rock, paper, scissors - 1) * scissors * (scissors + 2 * rock- 1)) / (total * (total - 1))
    self.table[key] = result
    return result
  def P(self, rock, paper, scissors):
    return self.S(scissors, rock, paper)
  def R(self, rock, paper, scissors):
    return self.S(paper, scissors, rock)

Note: The dynamic programming is Important here. It takes the run time from \(O(3^{r + p + s})\) to \(O(r + p + s)\).

Let me know if you figure out anything about this problem that I haven’t spotted or didn’t prove.

This entry was posted in Numbers are hard on by .