Bob Wins?

People still read my blog, right? Whatever, I'm sure history will look back and thank me for all this, or something like that. Anyway, the gladiator battle problem has been up for long enough, lets take a look at the solution. First, lets consider the a simple case, where Alice has one gladiator of strength A, and Bob has two gladiators of strength B₁ and B₂. Bob needs only decide which of the two gladiators to send first and the whole match is set. If Bob sends gladiator 1 first, he wins with chance B₁/(A+B₁) and loses with chance A/(A+B₁). If he loses the first game, he then has a B₂/(A+B₁+B₂) chance to win the second game. In total, the chance Bob has to win is given by:

B₁/(A+B₁)+AB₂/(A+B₁)(A+B₁+B₂)
=(B₁(A+B₁+B₂)+AB₂)/(A+B₁)(A+B₁+B₂)
=(A+B₁)(B₁+B₂)/(A+B₁)(A+B₁+B₂)
=(B₁+B₂)/(A+B₁+B₂)

Symmetric under exchanging B₁ and B₂, meaning that it does not matter who Bob chooses first. Actually, it is also equivalent to what Bob's chance of winning would be if he could merge his two gladiators into a single one of strength B₁+B₂ and just have that one fight. This suggests that the whole "gladiator battle" this is just a complication of a much simpler problem. Lets replace the gladiators strengths with amounts of money. Now Alice and Bob each have total sums of money A and B, and each round they each place some money on the table, Alice placing x and Bob placing y. Alice is then given an x/(x+y) chance to win and Bob has a y/(x+y) chance to win. The winner of the round takes the money sitting on the table and then a new round begins. The game ends when one person has all the money. Now, in the "gladiator battle" version of the game, the players have restrictions on what amounts they are allowed to bet, but if we can prove that all betting strategies are equally good then we will have proven that the gladiator game restrictions do not matter. Alright, when Alice places x, and Bob is choosing y, what y maximizes his potential gain? Bobs expected gain is x with probability y/(x+y) and -y with probability x/(x+y), so Bobs expected gain is:

x*y/(x+y)+(-y)*x/(x+y)

Clearly zero. This means that all strategies for Bob are equally good, Bob can play the gladiator battle randomly and his probability of winning is just given by

Σ b_i/(Σ a_j+ Σ b_i)

Where a_j are the strengths of Alice's gladiators and b_i are the strengths of Bob's gladiators.
There is another, slightly more elegant, proof of this result. I like it a bit more because the first one felt very unsatisfactory, but this other one is very cool though rather weird. Consider each gladiator to have an integer strength (this can be accomplished by approximating irrational strengths with rational ones, and then multiplying by denominators until everything is an integer). Each gladiator will have k beads assigned to them, where k is their strength. The beads are then all shuffled and placed on a string (you can imagine this as a bunch of coloured beads and each gladiator has their own colour). When two gladiators fight, whichever one has the furthest right bead wins the fight and then gets to claim all the beads owned by the defeated gladiator. It is not hard to see that this gives the correct probabilities of the battles and is a suitable representation of the entire tournament. In the end, only the rightmost bead matters, and the strategies are irrelevant. Human intuition on this problem is a bit funny. Most anybody will tell you that it is obvious that you must always send your strongest first, and the occasional person will actually be convinced that you must use your weakest first, but the idea that it is irrelevant which you do is very hard for people to grasp intuitively.