Rock, paper, scissors, lizard, Spock: counting on chance

I was never a fan of probability theory, but after I came to know the probabilistic method, I got to truly appreciate probability and all the amazing stuff we can do with it.

A friend of mine collects RPG dice, and I gifted her one of those on her last birthday. But with a twist: I told her that there was a $5$% probability that the outcome of rolling it would be not a number, but the word “beagle”. Ok, if you’re as confused as were my friend, it’s rightly so, as this episode didn’t actually happen and as far as I know there are no on-sale RPG dice with the word “beagle” in it. But there’s a weird mathematical consequence of what I said to my friend, and weirdly enough, this has something to do with one of the most fascinating existence proof methods in math. And if you want to add to the weirdness, we can apply the method to a rock, paper, scissors related mathematical problem.

Tournaments and its representations

The Big Bang Theory fans probably remember the one-of-a-kind “rock, paper, scissors, lizard, Spock” as an extended example of “rock, paper, scissors” with five contestants, instead of the usual three. We can go further and add even more contestants, although it surely makes the game schemes harder to memorize. Around the internet, these games are graphically represented by points (or pictures), which correspond to contestants, and arrows between the points indicating who wins over who.

Figure 1. Graphic representations of RPS and RPSLS.

RPS and RPSLS are examples of what mathematicians call tournaments: every pair of contestants is related by win-loss (note: sometimes we’ll also call them $n$-tournaments, where $n$ is the number of contestants). More than that, they are fair tournaments, given that every contestant defeats and loses to the same amount as other contestants do. We can build different tournaments with the same group of contestants by changing the win-loss relationships between each pair, and these games can get pretty unfair, as in the RPSLS, for example, we can make it so that Spock wins over everyone and the lizard loses for everyone (Figure 2). If we think about it, every match of this unfair version of RPSLS would end in a tie, since the players would always show the win-it-all Spock.

Figure 2. Unfair version of RPSLS in which Spock defeats everyone and Lizard loses to everyone.

There are many versions of RPSLS obtainable by inverting win-loss relationships; $2^{10} = 1024$ of them, to be precise (this number comes from the $10$ win-loss relationships between pairs, each of which with $2$ possible directions). With that many possibilities, we might be interested in finding one with specific properties.

We can twist larger versions of RPS a little bit to create new rules with new interesting attributes. Instead of two players going against each other, imagine a $2$ vs. $1$ match. An apparently reasonable rule is to give the win to the solo only if they individually win over both of the duo contestants (Figure 3). For instance, in the RPSLS Spock defeats the rock-scissors combination, but loses against paper-scissors, since Spock defeats only scissors. Alright, but is this a fair rule? (for now, let’s treat the concept of fairness very vaguely to make our analysis easier)

Figure 3. Two different matches of the 2 vs. 1 RPSLS: on the left, Spock defeats rock-scissors; on the right, Spock loses to paper-scissors.

The first thing to observe is that the answer would depend on how we determined the win-loss relationships between pairs of contestants, but assuming that we can freely manipulate those relationships to achieve a desirable level of fairness, we can instead ask ourselves: among all the $1024$ possible instances of RPSLS, is there a fair one to the $2$ vs. $1$ version of the game?

Now we can go one step further and define what we mean by fair. We’ll take one of the most trivial aspects of any fair game: everyone must have a chance of winning. In the original version of RPSLS, every contestant loses to exactly two other contestants, ensuring that the duo always has a winning chance. Now take the paper-scissors pair: no other contestant defeats them both simultaneously, making the paper-scissors combination invincible. As a result of that, if the duo shows it, the solo player can’t ever win. So from our definition of fairness, the $2$ vs. $1$ RPSLS in its traditional form isn’t fair, but can we still try to change win-loss relationships to make it fair?

The answer is no, no five contestants tournament have this fairness property (not going into details, but think about why!). It would be fair to ask if this property is only violated by $5$-tournaments or by different sized tournaments as well. Good news (I guess?)! The great Paul Erdös proved that the property is actually satisfied for tournaments of size at least $32$ [4].

Counting on chance

Now we go back to the weird RPG dice I gave to my imaginary friend. What can we actually get from what I said to her? Rewind: I told her that there was a $5$% probability that the outcome of rolling the die would be “beagle”. If this affirmation is true, then do you agree that there must be a face with “beagle” in it? Because if there wasn’t, then the chance of getting it would be zero, and not five percent. Isn’t this a fascinating piece of information? We know nothing about the dice: how many faces does it have? How does it look? What are the possible outcomes? But we know a probability, and that automatically gives us what one of the faces is.

What we’ve just described is an illustration of the probabilistic method, that comes from the principle that if an event has a positive probability of happening, then there exists an instance of this event (since if it didn’t exist, its probability would be zero). In this method relies the heart of Erdös theorem about tournaments:

Theorem (Erdös). If $n\geq32$, then there exists a $n$-tournament with the following property: every pair of contestants is defeated by a third contestant.

We’re not gonna dive into why this statement is true for it requires a lot of boring algebra, but the overall idea is the following: fixing $n$, we put all $n$-tournaments inside a box and estimate the probability of drawing one with the desired property, then, if this probability is greater than zero, the probabilistic method guarantees the existence of this tournament. But the estimation only works for $n\geq32$, and that’s where the theorem’s condition comes from. And it’s important to add that the probability calculation is only possible because tournaments are very structured objects, and we can take advantage of that to extract general information about the substructure we want to know about - in this case, tournaments with the fairness property.

To catch a glimpse of how strong the method is, we had already observed that the amount of different $5$-tournaments is quite expressive. But with $32$ contestants, this number is the exorbitant $2^{496}$ (something about $2$ followed by $149$ zeros). Finding one tournament with the fairness property may not be trivial, but among the $2^{496}$, we know that at least one of them satisfies it. Explicitly showing an object is a common way of proving it exists, but that may not be easy. The strength of the probabilistic method is relying on an (possibly) easier procedure, such as calculating probabilities using the object’s structure. This method is recognized as one of the most important in modern Combinatorics [3], one of the study fields that Erdös is famous for. The probabilistic method is so remarkable in elegance that some of its applications got a place in The Book [1], the place where according to Erdös, God keeps the most beautiful solutions to mathematical problems. And not by chance: it is crazy that we can use the randomness laws to prove the existence of something we can’t see.

All the cool stuff (extra)

For all the curious minds out there, here's an Wikipedia page listing probabilistic proofs to non-probabilistic theorems, which is a great sample of the cool theoretical applications probability has in different areas of Mathematics. Have fun!

Bibliography

[1] Aigner, Martin; Ziegler, Günter M., Proofs from THE BOOK, 6th ed. Berlin: Springer, 2018.

[2] Boaventura, Netto; Jurkiewicz, Samuel, Grafos: Introdução e prática. Blucher: São Paulo, 2009.

[3] Habib, M. et al. (Eds.), Probabilistic Methods for Algorithmic Discrete Mathematics, Springer-Verlag: New York, 1998.

[4] Jukna, Stasys, Extremal Combinatorics [s. n. t.].

[5] Morris, Rob.; Imbuzeiro, Roberto; Extremal and Probabilistic Combinatorics, lecture notes. Rio de Janeiro, 2011.