10
$\begingroup$

Alice and Bob both have N warriors under their command, numbered 1~N, and $1$ point of fighting power at their disposal. Before the game, they privately distribute the power between their warriors. When the game begins, both send their warrior #1 to a 1v1 fight. If a warrior with power x fights one with power y, the former wins with probability $\frac{x}{x+y}$, and the latter with probability $\frac{y}{x+y}$. If #1 is defeated, #2 is sent to continue the next round of fight, so on and so forth until one party has all of their warriors defeated and loses the game. The more battles a warrior wins, the stronger he becomes: after a warrior defeats an $x$ power opponent, his power will increase by $\frac{x}{2}$. Both players want to maximize their winning probabilities.

How should Alice distribute her fighting power?

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ The game is symmetric with respect to the two players. This is like asking what is the best strategy for playing rock-paper-scissors. $\endgroup$
    – WhatsUp
    Jul 9, 2021 at 5:55
  • $\begingroup$ @WhatsUp I guess in this case it would still be interesting to prove that "whatever strategy Alice chooses, the probabiilty of winning is still the same, which is 0.5" and not that some strategy is losing. I agree that the best strategy will have 0.5 probability of winning, due to symmetry. EDIT: Jaap put it better than me. $\endgroup$
    – justhalf
    Jul 9, 2021 at 6:10
  • 6
    $\begingroup$ @WhatsUp From the symmetry you only know that their probabilities of winning are both 50% if they play optimally. That does not mean that the optimal strategy is obvious. It is likely that the optimal Nash equilibrium is a mixed strategy, involving randomly choosing between various scenarios, just like rock-paper-scissors, but finding the worthwhile scenarios and their probabilities can be complicated. $\endgroup$
    – Jaap Scherphuis
    Jul 9, 2021 at 6:11
  • $\begingroup$ @JaapScherphuis, yeah, I tried calculating the optimal strategy for N=2, but I must have mistake somewhere since the best strategy does not have 0.5 probability. So it's not that simple indeed (or I did it in a too complicated way) $\endgroup$
    – justhalf
    Jul 9, 2021 at 6:23
  • $\begingroup$ @WhatsUp wolframalpha.com/input/… here is the probability space for N=2. X is the probability Alice put in her first warrior, Y is for Bob. We see that there is some choice that leads to sub-optimal result. $\endgroup$
    – justhalf
    Jul 9, 2021 at 10:09

2 Answers 2

Reset to default
3
$\begingroup$

Some semi-stochastic simulations with sample size 100 and N = 2, 3, and 4 tell me that the optimal strategy consists of

starting with weaker units in front, with power gradually (and roughly linearly) increasing towards the rear.

Some strong contenders:

[.421,.578], as in justhalf's comment.
[.25,.33,.42] and [.3,.3,.4]
[.11,.26,.26,.37], [.175, .2, .275, .35], and [.1,.2,.3,.4]

You can play around online here - further runs at higher sample sizes with teams of all kinds shows that it's actually pretty easy to get above even against [uniformly] random teams, but hard to get a winrate of .52 or above.

Just don't let any one warrior be too weak.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Do you find it plausible that there's a single best distribution of power, in the sense that it will guarantee you no less than 50% winning probability for every possible team of your opponent? $\endgroup$
    – Eric
    Jul 17, 2021 at 2:11
  • $\begingroup$ I find it yes for 2 warriors. Are you trying to imply that that's not the case? $\endgroup$
    – justhalf
    Jul 17, 2021 at 6:21
  • $\begingroup$ I believe Eric's question is a general statement about all N. "Fitness" seems simple enough that it should have a single global maximum, but I wouldn't be so bold as to say it will be winning against every other team. $\endgroup$
    – AxiomaticSystem
    Jul 18, 2021 at 3:02
0
$\begingroup$

I don't have a proof, but a gut feeling that the optimal strategy is to

Put all power to the first warrior

Because

Concerning resources, you only have 1 + win bonuses. Earlier wins = earlier resources. If Bob does not follow the same tactic, RNG aside, he will be practically be "feeding" Alice's monster.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ I thought of this too, but surprisingly, even for 2 warriors, this is false. If both put all power in the first warrior, Alice wins with probability 0.5, this is clear. But if Bob puts all power in the first warrior and Alice puts 0.8 power on the first warrior, Bob wins only if he won both, which has the probability 1/1.8 * 1.4/1.6 = 5/9 * 7/8 = 35/72 = 0.49. So Alice has better chance to win. I guess the intuition is that putting all on the first warrior means you lose immediately once you lose that warrior, while Alice has 2 chances. $\endgroup$
    – justhalf
    Jul 9, 2021 at 7:50
  • $\begingroup$ Or maybe it doesn't prove that it's false, since perhaps over all possible Alice's choice, the expectation of winning is still 0.5 with any strategy. But my point is that it's not that simple to prove. $\endgroup$
    – justhalf
    Jul 9, 2021 at 8:00
  • 1
    $\begingroup$ @justhalf Interesting, the total opposite tactic of equal spreading point makes bob win 0.0001% times $\endgroup$
    – George Menoutis
    Jul 9, 2021 at 8:15
  • $\begingroup$ wolframalpha.com/input/… That's the whole probability space for N=2. Seems like the optimal strategy is to spread it evenly. $\endgroup$
    – justhalf
    Jul 9, 2021 at 8:22
  • $\begingroup$ @justhalf There's even a better strategy than to spread evenly. $\endgroup$
    – Eric
    Jul 10, 2021 at 3:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.