A Martingale Argument for Optimal Gladiator Fight Probabilities

# Colosseum Fight - A probability problem


# Colosseum Fight - A probability problem












Problem Statement : Alice and Bob are in Roman times and have 4 gladiators each. The strengths of each of Alice's gladiators are 1−4, while Bob's gladiators have strengths 4,5,9, and 12. The tournament is going to consist of Alice and Bob picking gladiators to fight against one another one-at-a-time. Then, the two gladiators fight to the death with no ties. If the two gladiators are of strengths 𝑥 and 𝑦, respectively, then the probability that the gladiator with strength 𝑥 wins is $\frac{x}{x+y}$. The winning gladiator also inherits the strength of its opponent. This means that if a gladiator of strength 𝑥 wins against a gladiator of strength 𝑦, the winner now has strength 𝑥+𝑦. Alice is going to pick first for each fight among her remaining gladiators. Afterwards, Bob can select his gladiator (assuming he has one) to go against the one Alice selected. The winner of the tournament is the person who has at least one gladiator left at the end. Assuming Bob plays optimally, what is his probability of winning the tournament?

This question is taken from quantguide, original link - https://www.quantguide.io/questions/colosseum-fight

Any insights into how to solve this ? I am completely lost, whenever I dig deep to think about the problem, the number of cases just explodes, there must be some elegant way to figure out its answer

I recently saw a link on stackexchage, maybe here or maybe MathOverflow, to a writeup titled something like "Games no people play" by John Conway that had this but I can't find it now. The key is to realize that they are betting strength in each match and the bet is fair

Thanks

## Answer by justtryingtolearn (score 4, accepted)

https://quant.stackexchange.com/a/77962

I believe the answer is 4+5+9+12 / (4+5+9+12+1+2+3+4).

Starting with a simple problem of 2 gladiators (strengths A, B) vs 1 gladiator (strength Z). Regardless of the order, the probability of winning is (A+B)/(A+B+Z). This also applies to N vs 1.

Probability of Z winning both rounds:





For any N vs 1 situation, order does not matter so the strategies do not matter. After the first round of a 2 vs 2 situation, it becomes a N vs 1 where strategies do not matter. The choice of the first match in a 2 vs 2 does not matter.

Two players 1 (A, B) and 2 (Y, Z). The probabilities of player 2 winning for each combo of first match:



- By swapping labels, the other cases are identical.

This shows that in the 2 vs 2 case the order doesn't matter and the strategies don't matter.

For a 3 vs 2 case, I believe we can show that order of the first match doesn't matter. It shouldn't be too tedious because it will turn into a 3 vs 1 or 2 vs 2 case. Continuing this logic for 3 vs 3 and so on, I think we can show that strategy doesn't matter for 4 vs 4 and so we get the ratio of the sum of individual strengths.

## Answer by Samarth Singla (score 2)

https://quant.stackexchange.com/a/80547

The answer should indeed be $\frac{4+5+9+12}{4+5+9+12+1+2+3+4} = \frac{3}{4}$. In fact, we can show that all strategies are equivalent.

Let $a_1, a_2, ..$ and $b_1, b_2,...$ be the initial strengths of the gladiators of Player A and B respectively, and define $a = \sum a_i, b = \sum b_i$.

The main step is showing that the expected gain in total strength of a player is $0$ (in other words, it is a Martingale Process). Suppose the match is between A's gladiator with strength $x$ and B's gladiator with strength $y$. The expected strength of A's gladiator after the match is $$ \frac{x}{x+y} \cdot (x+y) + \frac{y}{x+y} \cdot 0 = x $$ So the expected gain in the gladiatior's strength is $0$. Since no other gladiator's strength changes, we can say that expected change in total strength of player A is also $0$ after a match. Same goes for B.

By linearity of expectation, we can show that this is true after any number of games. Hence the expected total strength at the end of the game is same as the total strength initially.

Define the probability of A winning as $P_A$, and the total strength of A as $S_A$ after the game ends. It is easy to see that $S_A$ would be $a+b$ on winning and $0$ on losing.

$$ E(S_A) = P_A\cdot(a+b) + (1-P_A)\cdot 0 = a$$ This gives $P_A = \frac{a}{a+b}$ and $P_B = \frac{b}{a+b}$, regardless of any set of strategies being played.