Less Gladiators

Time for the solution to the second gladiator problem. As before, I guess the thing to do is start with a simpler case.

Suppose Alice has a single gladiator of strength A, and Bob has two gladiators of strengths B₁ and B₂. Again, 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₂) chance to win the second game.

This gives Bob's chance of winning as:

B₁/(A+B₁)+AB₂/(A+B₁)(A+B₂)
=1-A²/(A+B₁)(A+B₂)

unsurprising, its one minus Alices chance of winning both matches. This is symmetric in B₁ and B₂ again, so it is independent of Bobs strategy. Its true that the full game is also strategy-independent, but it is actually a bit weirder to prove this one. I was not able to come up with a proof myself, this was in the paper where I found this problem.

Let us consider to replace the gladiators with lightbulbs that have a fixed burn out time. The burn out time of one of these idealized lightbulbs is memoryless, and if the lightbulbs expected lifetime is x, then the probability that it is still burning after time t is given by e^-t/x.

If we have a lightbulb with lifetime x and a lightbulb with lifetime y both burning at the same time, the chance that y burns out first is given by x/(x+y). So two gladiators fighting can be appropriately replaced by a "lightbulb match" where both Alice and Bob must turn on one of their bulbs and whichever goes out first is defeated. Since the burnout time is memoryless, the chance that a given lightbulb will burn out in the next five minutes is the same as the chance it had to burn out in the past five minutes, so it is enough that the winner simply leave their light on and the loser must turn on a new bulb. In the end whoever runs out of lightbulbs is the loser of the match.

We can see this game could just be replaced by Alice and Bob showing up on separate days, Alice turns on one of her bulbs until it burns out, then she turns on another one and so on until she runs out of bulbs, when she is out of bulbs she records the total lifetime of her team. Bob then comes by and doe the same thing. Whoever has more total lifetime wins the gladiator match. Its pretty clear there is no strategy in this game, but it is the same as this gladiator match game.

This game is a bit less fun than the other one, since human intuition arrives at the "all strategies are the same" result much faster than the other game. I guess thats because in the simpler case its very obvious. If our opponent has only one gladiator, then it does not matter what order we send ours in, our opponent must defeat them all anyway. In spite of the result being more obvious though, the proof is actually trickier to think of, because the setup does not have as much of an obvious "zero expectation value" minigame.

More Gladiators

Alright, this one is the final problem from "Games People Don't Play":

Alice and Bob are competing team managers in a gladiator competition. Alice's gladiators have strength a₁, a₂, a₃...a_n and Bob's have strength b₁, b₂, b₃...b_m. Each round, Alice will select a gladiator from her team and then Bob will select one from his team and the chosen gladiators will fight.

If a gladiator of strength x fights a gladiator of strength y, the chance the one with strength x wins is given by x/(x+y). The losing gladiator is eliminated and then a new round begins with Alice and Bob selecting gladiators to fight. The competition ends when one of the teams has run out of gladiators.

What is the optimal play? In particular, suppose Alice always chooses to send in her strongest gladiator, how should Bob respond?

Its the exact same as last time, but this time the gladiators strengths are constant, rather than gaining confidence from the fights.

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.

Gladiator Battle

Been some time since I had a new puzzle, and there are still two left in the paper "Games People Don't Play", though they are basically the same with a slight variation. Here is the first one:

Alice and Bob are competing team managers in a gladiator competition. Alice's gladiators have strength a₁, a₂, a₃...a_n and Bob's have strength b₁, b₂, b₃...b_m. Each round, Alice will select a gladiator from her team and then Bob will select one from his team and the chosen gladiators will fight.

If a gladiator of strength x fights a gladiator of strength y, the chance the one with strength x wins is given by x/(x+y). The losing gladiator is eliminated and the winning gladiator gains confidence from the fight, increasing the winning gladiator's total strength to x+y. Then a new round begins with Alice and Bob selecting gladiators to fight. The competition ends when one of the teams has run out of gladiators.

What is the optimal play? In particular, suppose Alice always chooses to send in her strongest gladiator, how should Bob respond?

It seems needlessly elaborate, especially given that in theory you have to solve for all possible values of a₁ through a_n and b₁ through b_m. It actually has a fairly elegant solution, but requires something of a mathematical transformation of the puzzle to reduce it to an easier setup.