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.
Best Answer
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.