# Determining the strength of an abstract army

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?

-
Not an answer to this, but you may be interested by Lanchester model of battle – Jean-Claude Arbaut Mar 15 '13 at 21:11
You don't define "strength" in the problem setting, and then propose a solution for the incompletely posed problem in which you define "strength" -- that doesn't make any sense. – joriki Mar 15 '13 at 21:11
Thanks, I've edited to clarify. – Curious Programmer Mar 15 '13 at 21:19

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

-

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?

-
I tried to prove it by finding ways in which a group of units could be said to be equivalent in strength to one - or ways in which one unit was equivalent to an infinite number of units with infinitessimal hp and attack - and do a proof by induction by reducing the armies to equivalent armies of two units and do a proof by induction sort of thing, but I got stumped. Your guess is as good as mine. – Curious Programmer Mar 28 '13 at 20:03
Can it be done for an army of n units versus 1 in the first instance. We have here th case for n=2, if you can prove that if it is true for n it is true for n=n+1 then you have a proof by induction for this. Get that far and we can think about the other side. – Dale M Mar 28 '13 at 23:01
Looking at my answer it needs to be expanded to cover S(A)\gtS(B) and `S(A)=S(B). And then for the induction part, you start with these and add either a weakest unit or a strongest unit - I think either will work since the analysis of any army can be started from either end. Go for the one with the easier maths! – Dale M Mar 28 '13 at 23:09