Optimal Attack and
Defense for a Number of Targets
in the Case of
Imperfect Interceptors
Joseph George Caldwell
July 31, 2001
Copyright
© 1989, 2001 Vista Research Corporation and Joseph George Caldwell. All rights
reserved.
Table of Contents
A. Mathematical Description of the
Problem
2. An Expression for the Expected
Damage
3. Procedure for Finding the
Solution
B. Description of the Solution
1. Low Attack Level (X < Xmin(Y))
2. Intermediate Attack Level (Xmin(Y)
< X < Xmax(Y))
3. High Attack Level (X > Xmax(Y))
4. Qualification Concerning the
Lagrangian Solution
C. Comparison of Solution in the
Case of Imperfect Interceptors to That for Perfect Interceptors
II. An Expression for the Expected Damage
III. Procedure for Finding the Solution
IV. Derivation of the Solution
A. Solutions for Case 1 and Case 3
C. Summary of Lagrangian Solutions
V. Characteristics of the
Attacker's Optimal Solutions
VI. Characteristics of the Defender's Optimal Solutions
VII. Determination of Solutions
Which Are Simultaneously Optimal for Both Attacker and Defender
A.
Correct Solution When Xmin(λ) < X < Xmax(λ)
B. Correct Solution When X < Xmin(λ).
C. Correct Solution When X > Xmax(λ)
D. Summary of Correct Solutions
VIII. Nature of the Solution as a
Function of the Attacker's Lagrange Multiplier
IX. Computer Program for Computing
the Optimal Solution
This
article is an extraction, with some amplification and minor notational changes,
of portions of the report: Caldwell, J. G., T. S. Schreiber, and S. S. Dick, Some
Problems in Ballistic Missile Defense Involving Radar Attacks and Imperfect Interceptors,
Report ACDA/ST-145 SR-4, Special Report 4, prepared for the US Arms Control and
Disarmament Agency by the Lambda Corporation (subsidiary of General Research
Corporation), McLean, Virginia, May 1969.
The results presented here were derived by Dr. J. G. Caldwell. These results are presented here because
they were never published in the open literature (refereed journals).
These
results were also published as Appendix F of the report, Caldwell, J. G., Theater
Tactical Air Warfare Methodologies: Automated Scenario Generation, Final
Report Contract No. F33657-88-C-2156 prepared for the USAF Air Force Systems
Command, Aeronautical System Division by Vista Research Corporation, July 1989.
Optimal Attack
and Defense for a Number of Targets in the Case of Imperfect Interceptors
This
article describes the optimal defense of a set of targets against an optimal
attack, in the case of imperfect interceptors.
This solution is obtained from a mathematical representation of
strategic nuclear warfare as a two-sided resource-constrained optimization
problem. The attacker and defender are
assumed to know each other's total force sizes, and it is assumed that the
attacker "moves last," i.e., the attacker allocates his weapons to
targets after observing the defender's allocation of interceptors to
targets. A one-on-one (or fixed
salvo-to-one) firing doctrine is assumed.
The attacker's goal is to maximize the total damage to the targets, and
the defender's goal is to minimize this damage. It is assumed that damage on any single target can be adequately
described by the "exponential" damage function defined below.
Let
us denote the total number of weapons by X and the total number of interceptors
by Y. Further, let us denote the number of targets by t, and the number of
weapons and interceptors allocated to the i-th target by xi and yi,
respectively. The attacker's and
defender's strategies are hence specified by vectors
x' = (x1,
x2,..., xt)
and
y' = (y1,
y2,..., yt)
where
each xi > 0, yi > 0, and
Σ(i:1,t) xi = X
and
Σ(i:1,t) yi = Y
where
the notation Σ(i:1,t) denotes the summation operator over the index i,
ranging from 1 to t.
Using
the exponential damage function, the expected damage at the i-th target is
Di(zi) = Pi(1 - exp(-βizi))
where
zi is the number of weapons reaching the i-th target, Pi
is the value of the i-th target, and βi is the damage function
parameter for the i-th target.
The
interceptor kill probability, κ, is assumed to be the same for all
targets.
The
attacker is assumed to choose his strategy x after observing the
strategy y selected by the defender.
He will choose a strategy x*(y) such that
H(x*(y*),y) = max(x) H(x,y),
where
H(x,y) denotes the total expected damage corresponding to the
strategies x and y, and max(x) denotes maximization with
respect to x (of the following function of x, in this case H(x,y)). The defender hence must choose his strategy y*
such that
H(x*(y*),y*) = min(y) max(x)
H(x,y) ,
and
min(y) denotes minimization with respect to y.
Using
the exponential damage function, the expected damage on the i-th target is
shown in Appendix A to be PiQi where
1 - exp(-αixi) , xi <
yi
Qi =
1 - exp(-βi(xi-yi))
exp(-αiyi) ,
xi > yi ,
and
αi < βi is defined by the equation
exp(-αi) = (1 - κ)exp(-βi)
+ κ .
The
total expected damage is
H(x,y) = Σ(i:1,t) Hi(xi,yi)
= Σ(i:1,t) PiQi
.
We
shall denote the expected damage corresponding to the optimal solutions x*,
y* as H(X,Y).
Our
problem, thus, is to determine x*,y* such that
H(x*,y*) = min(y) max(x) H(x,y)
where
H(x,y) = Σ(i:1,t) PiQi
subject
to the constraints
Σ(i:1,t) xi = X
Σ(i:1,t) yi = Y
and
xi > 0, yi > 0. The function H(x,y) is
additively separable over the targets so the Everett-Pugh double Lagrange
multiplier technique (References 2 and 3) can be used to find a solution. The problem becomes one of finding xi,
yi corresponding to
min(yi) max(xi) (PiQi
- λxi + μyi)
where
λ, μ are adjusted so that the constraints
Σ(i:1,t) xi = X
and
Σ(i:1,t) yi = Y
are
satisfied. If there are several choices
of (μ,λ) for which the constraints can be met (i.e., there are
several solutions to the double Lagrange multiplier problem), the correct
optimal solution to the problem is the solution corresponding the least damage.
For
convenience we drop the subscript i, so that the problem is to find x, y
corresponding to
min(y) max(x) (PQ - λx + μy) .
The
solution is derived in Appendix A (Technical Details). The next section will describe the results.
The
solution to the above two-sided optimization problem is complicated to describe
analytically, and can be described best in geometrical terms. Appendix A contains such a description. In this section we shall present only a
qualitative description of the optimal attack and defense allocations.
Note
that the mathematical approach used to solve the present problem assumes that
the xi's and yi's are continuous variables, rather than
integers. This approximation introduces
a negligible error whenever the number of interceptors and weapons allocated to
targets are zero or large enough that the fractional parts are insignificant.
The
optimal solution can conveniently be described by observing how the weapon and
interceptor allocations to targets change for a fixed total defense level, Y,
as we very the total offense level, X, from zero to a very large number. In all situations, weapons are allocated to
targets so that the marginal payoff per weapon is the same on all targets. Note that for a specified X, there may be
some targets that, even if undefended, yield so little payoff to the attacker
that they are not attacked. Such
targets are not defended, either. For a
specified total defense level, Y, there are two total attack levels, Xmin(Y)
and Xmax(Y), that are of special significance. We shall describe the nature of the solution
in terms of these levels.
When
the attack level is less than the value Xmin(Y), every attacked
target is defended by a number of interceptors that exceeds the number of
weapons assigned to it. Thus damage to
targets can occur only through "leakage", i.e., failure of the interceptors
to kill all incoming weapons. The
defense allocation is arbitrary, so long as there are more interceptors than
weapons on each attacked target. The
attack allocation for specified X is unique.
The total payoff to the attacker is an increasing concave
("diminishing returns") function of the total attack level, X.
For
all attack levels lying between the values Xmin(Y) and Xmax(Y),
the defense is unique. Such a defense
is called "stable." In this
region of attack levels, the attacker can choose between two different attack
levels on each target. The lower level
may be zero on some targets. The
attacker must attack each target at either the lower level or the higher level,
and can choose to attack at any combination of these permissible levels that
meets his total attack level, X. The
payoff is a linear function of the total attack level in this region.
The
situation in the case of the low and intermediate attack levels is referred to
as "defense dominant".
As
the total number of weapons is increased above the level Xmax(Y),
the defender must change his allocation.
He does so by defending fewer targets, but defending the defended
targets at a higher level. As the
attack size increases, eventually only one target would be attacked. Also, for a sufficiently large attack size
all targets would be attacked. Since
the defense allocation changes as the attack size changes in this region, the
defense is called "unstable".
Both the attack and defense allocations corresponding to specified X are
unique.
The
situation in the case of a high attack level is called "attack
dominant".
The
solutions to the present problem are derived by the method of generalized
Lagrange multipliers. Using this
technique, we can find a solution for every total attack level X < Xmin(Y). Over the range Xmin(Y) <
X < Xmax(Y), however, there are only a finite number of
Lagrangian solutions, corresponding to all possible combinations of low level
or high level attacks on each attacked target.
For a large number of weapons, interceptors, and targets, there is a
very large number of such solutions, and there would be a Lagrangian solution
corresponding to a total attack size quite close to any specified total attack
level. Hence in practice we need only
concern ourselves with the Lagrangian solutions. (Solutions corresponding to other total attack levels differ very
little from Lagrangian solutions corresponding to nearby total attack
levels. These other solutions are less
"efficient" than the Lagrangian solutions, since the payoff function
for them lies below the marginal payoff for the additional weapons used (beyond
those required by the closest Lagrangian solution using fewer weapons) is less
than the total marginal payoff achieved by going to the next higher Lagrangian
solution. This latter marginal payoff
is defined by the slope of linear payoff function defined by the Lagrangian solutions.)
Over
the range X > Xmax(Y), there can be found a Lagrangian solution
for any specified total attack level, X, but not for every specified total
defense level, Y. The reason for this
difficulty lies with the fact that, in the Lagrangian solution, a target can be
defended at only two levels, one of which is zero (no defense). (The situation is analogous to the
intermediate attack situation in which targets could be attacked at only two
levels.) As before, this problem is not
of practical significance, since we can always find a Lagrangian solution
corresponding to a total defense level close to the specified total defense
level.
It
is of interest to compare how the nature of the solution to the allocation
problem in the case of imperfect interceptors differs from the solution in the
case of perfect interceptors. Two
questions of interest are:
1. For what range of the kill probability, κ, are the allocations
and total damage essentially the same as for the perfect interceptor case,
κ = 1?
2. For specified interceptor kill probability, κ, and
total defense level, Y, is the solution to the problem "similar" (in
allocations and total damage) to the perfect interceptor problem with total
defense level κY? (Note that
κY is the expected number of interceptors that do not fail, and represents
a possible "effective" number of perfect interceptors.)
The
questions were answered by examining the nature of the solution for a
"reasonable" set of hypothetical targets, described in Table 1.
Table
1. Hypothetical Target Set
Target Value Exponential Damage
Target Number (Population
in millions) Function Parameter
(β)
1 10 .03
2 6 .04
3 4 .05
4 3 .06
5 2 .08
6 1.5 .10
7 1.0 .20
8 1.0 .30
9 1.0 .40
10 .5 .50
The
total expected damage, H(X,Y), corresponding to the optimal attack and defense
allocations is plotted in Figures 1 and 2 as a function of total attack level,
X, for fixed total defense level, Y.

Figure
1 corresponds to Y1 = 400, and Figure 2 corresponds to Y2
= 800. On each figure are three curves:
1. H(X,Yi) for κ = 1
2. H(X,Yi) for κ = .75
3. H(X,.75Yi) for κ = 1.

The
figures indicate first that there are substantial differences in total damage
between the κ = 1 and κ = .75 cases, and that the imperfect
interceptor case is not always closely approximated by the perfect interceptor
case for total defense level κY.
However, the difference between these latter two cases is not so great
as to preclude using the "equivalent perfect interceptor" approximation
for some purposes.