Determining the strength of an abstract army

Question

Lets imagine we have two armies, represented by lists of pairs of positive numbers, like this: [($attack1$,$defence1$),($a2$,$d2$)...($an$,$dn$)] face each other in combat. The rules of combat are the following: each unit (pair of attack $a$ and defence $d$) may at any time choose a target; it then does damage continously to its target at a rate of $a$ per second until it either chooses another target or "dies" (i.e. its defence becomes 0). Units may switch targets at any time. Each army plays optimally to either maximise its strength at the time all enemy units are dead (if it will win) or to minimise the strength of the enemy army (if it will be routed). An army wins by killing every unit on the opposing side. An army $A$ is of greater strength than the army $B$ if it can defeat $B$ and any army $B$ can defeat or ties with.

I conjecture that the function $strength(A) = d1*(a1+a2...an) + d2*(a2+a3...an)...dn*an$ , where $(a1,d1)...(an,dn)$ are the units of $A$ ordered by $(attack /defence)$ in descending order is a measure of an army's strength such that:

If $A1$ faces $A2$ and $strength(A1) > strength(A2)$ then A1 will emerge victorious with a remaining strength $strength(A1) - strength(A2)$

If $strength(A1) = strength(A2)$ then they draw, either through both being routed or the battle never ending. I can't prove it. Can you?

Answer 1

Warning : I am not claiming this is a complete and rigorous answer !

I think your conjecture is not true. Let's have a look at the situation of an army of 2 vs an army of 1 (the first non-trivial case). Denote by $u_1$ and $u_2$ the units of the first army and $u_3$ the unit of the second army, and let $u_i = (a_i, d_i)$.

In this case the optimal strategy for army one is obvious (attack unit 3 until it dies) and the strategy of army 2 must be to focus on either unit 1 or unit 2, and then attack the other if it manages to kill the first. Let's say army 2 will focus on unit 1 first. Note : choosing which unit to engage depending on all variables seems non-trivial and interesting, but I don't need it for the purpose of this post.

Let's call $t_i$ the times of death of unit $i$ : more precisely, let's call $t_1$ the time required for army 2 to kill unit 1 (provided it lives long enough), $t_2$ the time required for army 2 to kill the second unit of army 1 and thus winning the battle (still provided it lives long enough) and then $t_3$ the time it will take to army one to kill unit 3.

It is pretty straightforward that $t_1 = d_1/a_3$. It's also easy to see that $t_2=t_1 +d_2/a_3$. Finally $t_3$ is a little bit more complicated : $t_3$ must verify $$d_3 - t_1 (a_1 + a_2) + (t_3 - t_1) a_2=0$$ (since until $t_1$ both units of army one will attack, and then after $t_1$ only unit 2 will remain).

So army 2 will win if only if $t_3 > t_2$. With basic arithmetic, we come up with : $$t_3 - t_2 = \frac{d_3}{a_2} - \frac{d_2}{a_3} - d_1 \frac{a_2 + a_1}{a_3 a_2}.$$

Now this is where my laziness shows up : I didn't look for specific values of the parameters which conflict with your own formula, but the two expression seem sufficiently different that I am confident there should be. In particular I have a term that is not linear in the $a_i$ so I am almost sure we do not give always the same predictions.

Note that to be perfectly rigorous we cannot choose the parameters completely arbitrarily since the assumption that the optimal strategy for army 2 to attack unit 1 first probably imposes constraints on the parameters.

ADDENDUM : I think your conjecture is more or less based on the assumption that the best strategy is to focus on the weakest units first (or the strongest, depending on how you order your pairs $(a_i, d_i)$). I think it is more complicated than that : it might be best to take care of a heavy hitter first, or if you are sure to die, to take lesser opponents with you to the grave...

Answer 2

This is also not an answer but I think @Glougloubarbaki is on the wrong track.

For the case of two armies

$S(A) = d_1(a_1+a_2) + d_2a_2$

$S(B) = d_3a_3$

the conjecture is that if $S(B)>S(A)$ then Army B will win with a residual strength of $S(B)-S(A)$ and vice versa. That is

$$d_3a_3 - d_1(a_1+a_2) - d_2a_2$$

If we assume $S(B)>S(A)$ and it attacks $U_1$ first it will destroy $U_1$ after $d_1\over a_3$ seconds and $U_2$ after a further $d_2\over a_3$ seconds. During this period Army A will do damage $(a_1+a_2){d_1\over a_3} + a_2 {d_2\over a_3}$. Therefore its residual strength will be

$$a_3{(d_3-(a_1+a_2){d_1\over a_3} - a_2 {d_2\over a_3})}$$

expanding gives

$$a_3 d_3-(a_1+a_2)d_1 - a_2 d_2$$

which is the same as the conjecture.

If it attacks $U_2$ first then the damage it suffers is $(a_1+a_2){d_1\over a_3} + a_1 {d_1\over a_3}$ and its residual strength is

$$a_3 d_3-(a_1+a_2)d_1 - a_1 d_1$$

From the ordering defined we know

$${a_1\over d_1} \ge {a_2\over d_2}$$

so

$${a_1d_2}\ge{a_2d_1}$$

so the 2nd strategy is demonstrably worse for Army B.

I have no idea how to expand this to more complex cases. Is this susceptible to proof by induction?