Gladiator Game

The Gladiator Game appears to be known under other names and have several variants, see, for example A Colonel Blotto Gladiator Game for history and variations. My source is Haim Shapira's popular book on Game Theory. This is not so much a game as a problem of finding an optimal strategy for a team to win in a series of one-on-one meets.

So there are two teams of gladiators, each of whom has been assigned a strength attribute (a positive number). When two gladiators from different teams meet, their chances to win the duel are proportional to their strengths. A fellow that loses a duel, dies and takes no part in further combats. The winner - who returns to the bench and is immediately ready for another fight - has his strength augmented by that of the loser. The last team standing wins.

Let's there be two teams with individual strengths (in, say, non-decreasing order) $\{a_{1}, a_{2},\ldots,a_{m}\}$ and $\{b_{1}, b_{2},\ldots,b_{n}\}.$ Find an optimal strategy for a team, i.e., the order of sending team members to duel opponents from the other team, to maximize its chances of winning the competition.

Solution

References

Haim Shapira, Gladiators, Pirates and Games of Trust: How Game Theory, Strategy and Probability Rule Our Lives, Watkins Publishing, 2017

There is no optimal strategy. No strategy effects the chances of a team to win the competition. Let $\displaystyle A=\sum_{i=1}^{m}a_{i}$ and $\displaystyle B=\sum_{i=1}^{n}b_{i}.$ Then the chances of a team to win are proportional to its total strength, i.e., for the first team, it is $\displaystyle\frac{A}{A+B};$ for the second, it is $\displaystyle\frac{B}{A+B}.$

The proof is by induction on $n+m,$ assuming both $n$ and $m$ are greater than zero.

The claim is certainly true for $m=n=1.$ Assume it is true for $m+n=N,$ and let now that one team still has $m$ members, the other membership of the other grew to $n+1.$ So now $\displaystyle A=\sum_{i=1}^{m}a_{i}$ and $\displaystyle B=\sum_{i=1}^{n+1}b_{i}.$

For the first duel, the first team sends a gladiator of strength $a,$ the second a gladiator of strength $b.$ The first wins with the probability of $\displaystyle\frac{a}{a+b},$ the second with the probability of $\displaystyle\frac{b}{a+b}.$

Depending on who wins that duel, there will be two possible distributions of strength:

$a$ wins: $\{a_{1},\ldots,a+b,\ldots,a_{m}\}$ and $\{b_{1},\ldots,\overline{b}\ldots,b_{n+1}\},$
$b$ wins: $\{a_{1},\ldots,\overline{a},\ldots,a_{m}\}$ and $\{b_{1},\ldots,b+a\ldots,b_{n+1}\},$

where overline means the absence of the fighter.

According to the induction assumption, in the first case, the chances of the first team to win equal $\displaystyle\frac{A+b}{A+B},$ in the second case they are equal to $\displaystyle\frac{A-a}{A+B},$ making the overall probability to be

$\begin{align}\displaystyle P_{a}&=\frac{a}{a+b}\cdot\frac{A+b}{A+B}+\frac{b}{a+b}\cdot\frac{A-a}{A+B}\\ &=\frac{aA+bA}{(a+b)(A+B)}\\ &=\frac{A}{A+B}, \end{align}$

as claimed.

72395948