Optimal Strategy for a Combinatorial Game with Asymmetric Information: Warrior Selection Tournament

Question

Game Setup

Bob and Alice are managing a team of warriors. Alice's team consists of warriors with strengths $3, 4, 6, 7$, and Bob has $4$ warriors with strengths $9, 8, 4, 2$ respectively.

If a warrior with strength x fights another warrior with strength y, warrior with strength x wins with probability $\frac{x}{x+y}$ and there is no draw (i.e. the other one dies), and the victorious gains confidence and after the match his strength becomes $x+y$

In this tournament, warriors fight one-on-one, with Alice picking a warrior first for each fight (she picks randomly), and the winner gaining confidence and increasing their strength to the sum of their original strength and the strength of the defeated warrior. There are no draws, i.e., one of the warriors always wins the battle.

The winner of the tournament is the person who has at least one warrior left at the end.

Problem:

What is the optimal strategy for Bob to maximize his probability of winning the game, given that Alice chooses warriors randomly?

My Attempt

I have a gut feeling that there is no optimal strategy, and all strategies lead to the same probability, which is $\frac{\sum \text{Bob's Warriors}}{\sum \text{Bob's Warriors} + \sum \text{Alice's Warriors}}$. I tried simulating the game with a Monte Carlo simulation on Jupiter Notebook and the results seem to agree with my gut feeling However, I am struggling to prove it formally.

Answer 1

Here is a rigorous proof that every strategy has the same probability of success.

For any $a,b,n\in\mathbb N$, let $p_n(a,b)$ be the probability of Alice winning when her army total is $a$, when Bob's army total is $b$, and when there are $n$ soldiers left between Alice and Bob combined. We will prove that $$ p_n(a,b)=\frac{a}{a+b}, $$ by induction on $n$. We can take $n=1$ as a base case, which is easy to verify.

Suppose that Alice sends a soldier with strength $x$, and Bob one with strength $y$. Then $$ \begin{align} p_n(a,b) &=P(\text{Alice wins war}\mid\text{Alice wins battle})\cdot \frac{x}{x+y} \\&\quad+P(\text{Alice wins war}\mid\text{Alice loses battle})\cdot \frac{y}{x+y} \\&=\frac{(a+y)}{(a+y)+(b-y)}\cdot \frac{x}{x+y}+\frac{(a-x)}{(a-x)+(b+x)} \cdot \frac{y}{x+y}=\frac{a}{a+b}. \end{align} $$ This completes the proof by induction.

Answer 2

You’re right; it doesn’t matter which warriors fight which in what order. A battle doesn’t change the expectations of the sums of strengths of each player’s warriors, since the warrior who enters the battle with strength $x$ has expected strength $\frac x{x+y}(x+y)+\frac y{x+y}\cdot0=x$ after the battle, and likewise $\frac x{x+y}\cdot0+\frac y{x+y}(x+y)=y$ for the warrior who enters with strength $y$. Since the total expectations aren’t changed by any of the battles, they’re the same at the end of the game as at the beginning of the game, and that implies the winning probability that you conjectured.