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.
This
appendix derives the optimal defense of a set of targets against an optimal
attack in the case of imperfect interceptors. It is assumed that the defender
has a total number, Y, of interceptors, and that the attacker has a total
number, X, of weapons. 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 .
We
assume that the exponential damage function adequately describes the expected
damage at each target; that is, the expected damage is
Di(zi) = Pi(1
- exp(-βizi))
where
zi is the number of weapons reaching the i-th target, Pi
denotes the value of the i-th target, and βi is the damage function
parameter for the i-th target.
We
assume that the attacker "moves last," i.e., he chooses 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) represents the expected damage corresponding to the
strategies x and y. The defender, then, should choose his
strategy y* such that
H(x*(y*),y*) = min(y)
max(x) H(x,y) = U .
The
value U is the upper pure value of the game in which the attacker and defender
move simultaneously. Since x* and y* are pure strategies, there
is no reason why U should equal the lower pure value of such a game, defined by
L = max(x) min(y) H(x,y)
.
Both
the attacker and defender are assumed to know each other's force size and κ.
We
assume that the interceptor kill probability, κ, is the same for all targets.
The
expected damage on the i-th target if u weapons get through is given by
Di(u) = Pi(1 - exp(-βiu))
.
The
probability that u weapons get through, given that there are xi
weapons and yi interceptors, both integers, is
A if 0 < u < xi
and xi < yi
Pxiyi(u) = 0 if 0 <
u < xi-yi and xi > yi
B if xi-yi < u <
xi and xi > yi
where
A = C(xi,u)(1 - κ)u κxi
- u
and
B = C(yi,(u - (xi - yi)))
(1-κ)u - (xi - yi) κxi - u ,
and
C(n,e) denotes the combination function (i.e., the number of combinations of n
things taken e at a time). (Note: The word processing program used to display
this article cannot place subscripts or superscripts on subscripts or
superscripts; the exponents xi and yi in the preceding expressions (and in
similar expressions that follow) should be xi and yi,
respectively.)
The
expected damage on the i-th target is hence
Hi(xi,yi) =
Σ(u:0,xi) (Expected damage given that u weapons
get through) (Probability that u weapons get
through)
= Σ(u:0,xi) Pi(1 - exp(-βiu))Pxiyi(u)
= PiΣ(u:0,xi) (1 - exp(-βiu))Pxiyi(u)
= PiQi ,
where
A, xi < yi
Qi =
B, xi > yi
where
A = 1 - ((1-κ)exp(-βi)+κ)xi
and
B = 1 - exp(-βi(xi - yi))
((1 - κ)exp(-βi) + κ)yi .
We
shall use this expression for all xi, yi, not just for
integral values. We shall simplify the expression for Qi by
defining
exp(-αi) = (1 - κ)exp(-βi)
+ κ
where
αi < βi since κ < 1. Hence we have
1 - exp(-αixi)
, xi < yi
Qi =
1 - exp(-βi(xi - yi))
exp(-αiyi) , xi > yi .
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. Since the function
H(x,y) is not concave, the Kuhn-Tucker theorem is of no
assistance in computing the solution. The function H(x,y) is additively
separable over the targets, however, and 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 to the least damage. We shall for convenience drop the subscript
i; that is, the problem is to find x, y corresponding to
min(y) max(x) (PQ - λx + μy) .
The
values of the Lagrange multipliers are adjusted so that the resource
constraints are met.
The
significant feature of the generalized Lagrange multiplier (GLM) method is
that, because the damage function is additively separable (i.e., the total
damage is the sum of the damage on each target), the solution of the global
optimization problem may be found by simply solving, independently, an
unconstrained optimization problem for each target (and then adjusting the
multipliers so that the constraints are obeyed. Another reason (apart from
additive separability) why the GLM method is used in this problem is that the
damage function is not convex (so that the Kuhn-Tucker and other standard
optimization methods cannot be applied). (In addition to not requiring
convexity of the objective function, the GLM method also does not require
differentiability or continuity or linearity of the objective function.)
The
only complexity that arises in the present problem is that the two-sided GLM
procedure may produce a multiplicity of solutions for specified values of the
Lagrange multipliers, some of which may not correspond to optimal solutions.
It is hence necessary to prove that the optimal solution is contained within
the solution set, and to select it from the non-optimal solutions. (This
difficulty does not occur with the one-sided GLM method.)
The
damage function H(x,y) = PQ may be illustrated as in Figure A-1.
Let
us denote
g(x) = P(1 - exp(-αx))
and
f(Δ,y) = P(1 - exp(-βΔ - αy))
where
Δ = x - y > 0. Then we may write
g(x) , x < y
PQ = H(x,y) =
f(Δ,y) , x > y .
We
distinguish three cases:
Case 1: g'(0) < λ, f'(0,0) > λ
Case 2: g'(0) > λ (which implies f'(0,0)
> λ since α < β)
and
Case 3: f'(0,0) < λ (which implies
g'(0) < λ since α < β) ,
where
the derivative of f(Δ,y) is with respect to Δ.
These
cases are depicted in Figures A-2, A-3, and A-4.
(The
parenthetic remarks follow since:
g(x)
= P(1 - exp(-αx)
g'(x)
= Pα exp(-αx)
g'(0)
= Pα
f(Δ,y) = P(1 - exp (-βΔ - αy)
f'(Δ,y) = Pβ exp(-βΔ - αy)
f'(0,0)
= Pβ
α < β therefore Pα < Pβ, and hence g'(0) <
f'(0,0).)
Now
Case 1 is a straightforward generalization of the problem solved by Goodrich
(pp. 12 - 19 of Reference 4). Goodrich solved this problem in the case of
perfect interceptors (κ = 1), as depicted in Figure A-5.
The
solution in Case 1 is as follows. For specified y, consider the line passing
through the origin and tangent to the damage curve (see Figure A-6). (Note:
The Figure A-6 does not clearly show that the damage curve has slope lower than
the tangent line at the origin.)
Let
us denote the slope of this line by λ'(y), the value of x at the point of tangency
by x', and denote Δ'(y) = Δ' = x' - y. Let us denote the value of x
corresponding to slope λ by xλ, and denote Δλ(y) = Δy
= xλ - y. It is easy to show (see Goodrich) that the value of x
that maximizes the Lagrangian function
L(x,y) = H(x,y) - λx + μy
is
0 if λ > λ'(y) =
λ'
x* =
xλ if λ < λ'(y) = λ'
(either
value, 0 or xλ, may be chosen if λ = λ'). Denoting Δ'(y) = Δ' = x'
- y, we have that
f'(Δ',y) == λ' = f(Δ',y)/(Δ' + y) ,
(where
the differentiation is with respect to Δ and the double equal sign, ==, denotes
"is identically equal to") and we may rewrite the optimal x-solution
as
0 if λ > f(Δ',y)/(Δ'
+ y)
x* =
xλ = Δλ + y if λ <
f(Δ',y)/(Δ' + y) .
Note
that if f'(0,0) < λ (Case 3), then x* = 0, for then (since f'(Δ,y) <
f'(0,0) < λ) there is no point x such that f'(Δ,y) = λ, regardless of the
value of y). (This follows by the following:
f'(Δ,y) = Pβ exp(-βΔ - αy)
f'(0,0)
=-Pβ
f'(Δ,y) = Pβ exp(-βΔ - αy) < f'(0,0) (since
exp(-βΔ - αy) < 1)
so
if f'(0,0) < λ then f'(Δ,y) < λ for all x,y, so that
there are no roots if f'(0,0) < λ.)
Substituting
the above solution x* into L(x,y), we obtain
μy if λ
> f(Δ',y)/(Δ'+y)
L(x*,y) =
f(Δλ,y) - λ(Δλ+y) + μy if
λ < f(Δ',y)/(Δ'+y) .
Note
that we have substituted Δλ + y for xλ in the above,
because we wish to represent y explicitly. We wish to choose y to minimize
L(x*,y).
It
is interesting, but not necessary for the solution, to note that f(Δλ,y)
depends only on λ, in the case of the exponential damage function. We will now
demonstrate this. Now Δλ is defined by the equation
f'(Δλ,y) = λ
where
the differentiation of f(Δ,y) is with respect to Δ. Note that Δλ
depends on y. Since
f(Δ,y) = P(1 - exp(-βΔ - αy)) ,
we
have
f'(Δ,y) = Pβexp(-βΔ - αy) ,
so
that
Pβexp(-βΔλ - αy) = λ ,
so
that
f(Δλ,y) = P(1 - λ/Pβ) ,
which
depends only on λ. Hence we could write
f(Δλ,y) = f(λ)
in
the case of the exponential damage function.
This
result is interesting, since if implies that the damage is the attacker's
(heavier) optimal attack corresponding to the value λ is the same (for the
exponential damage function), whether the defender chooses to defend the target
or not (since the height of the damage function is the same (f(Δλ,0)
= f(Δλ,y)) in either case). (If, in the optimal attack against a
defended target, the attacker has two attack options (e.g., 0 and xλ),
the no-defense damage (optimal attack) is the same as the damage at the heavier
optimal attack level against the defended target.) We observe from the
expression for f(λ) that the fraction surviving the optimal attack is λ/Pβ.)
Continuing
with the (general) solution, we observe that we can write the Lagrangian
function as
μy
if λ > f(Δ',y)/(Δ' + y)
L(x*,y) =
f(λ) - λ(Δλ + y) + μy if λ <
f(Δ',y)/(Δ' + y)
μy if y > f(Δ',y)/λ - Δ'
=
f(λ) - λ(Δλ + y) + μy if y <
f(Δ',y)/λ - Δ' .
Now
the set
S = {y │ y > f(Δ'(y),y)/λ - Δ'(y)}
= {y │ λ > f(x'+y,y)/x'}
= {y │ λ > λ'(y)} .
Now
λ'(y) = f(x'+y,y)/x' is
a monotonic increasing function of y, and so
S = {y │ y > y'}
where
y' is the unique solution to the equation
y = f(Δ'(y),y)/λ - Δ'(y) .
Hence
the Lagrangian becomes
μy if y > y'
L(x*,y) =
f(Δλ,y) - λ(Δλ+Y) + μy
if y < y' .
(For
the exponential damage function, f(Δλ(y),y) = f(λ), and y' is that y
such that
f(Δ'λ(y),y)/(y + Δ'λ(y)) = λ
i.e.,
f(λ)/(y' + Δ'λ(y')) = λ
f(λ)/ λ = y' + Δ'λ (y')
y'
= f(λ)/λ - Δ'λ(y') .)
Since
L(x*,y) is hence a piecewise linear function of y, the value of y that
minimizes L(x*,y) occurs either as y = 0 or at the solution y = y' to the
equation
y = f(Δ'(y),y)/λ - Δ'(y) .
Substituting
these values into L(x*,y), we obtain
L(x*,0) = f(Δλ(0),0) - λΔλ(0)
and
L(x*,y') = μy'
= (μ/λ)(f(Δ'(y'),y') - λΔ'(y')) .
To
minimize L(x*,y), we hence choose
0 if μ > λc
Y =
y' if μ < λc
where
c = (f(λ) - λΔλ(0))/(f(λ) - λΔλ(y'))
,
and
either value if μ = λc. This corresponds to the solution obtained by Goodrich
(where c = 1 in the case of perfect interceptors). (The solution represents a
"balanced defense", since the per-weapon payoff to the attacker is
the same for all targets.)
We
now consider Case 2, in which g'(0) > λ. (This implies f'(0,0) > λ.
Observe also that f'(0,x) > g'(x).) For specified y, consider the line
tangent to the damage function in two places, as shown in Figure A-7.
We
denote the slope of this line by λ', and the values of x at the two points of
tangency by x1' and x2'. We define x1, x2,
Δ1, Δ2, Δ1', Δ2' similarly, as
shown in Figure A-7. Since f'(0,x) > g'(x), we have x1' < y
< x2'. Since we are assuming that g'(0) > λ, the value of x
that maximizes the Lagrangian function
L(x,y) = H(x,y) - λx + μy
cannot
occur at x = 0. Rather, the optimal solution is
x1 if λ
> λ'
x* =
x2 if λ
< λ'
(either
value if λ = λ'). That this is the optimal solution follows from the
generalizated theory of Lagrange multipliers (Reference 1). Defining Δ1'
= x1' and Δ2' - x2' - y, we have
λ' == f'(Δ2',y) = (f(Δ2',y)
- g(Δ1'))/(Δ2' + y - Δ1')
(where
the differentiation is with respect to Δ2') so that we may write
x1 = Δ1
if λ > (f(Δ2',y) - g(Δ1'))/(Δ2' + y - Δ1')
x* =
x2 = Δ2 + y if λ <
(f(Δ2',y) - g(Δ1'))/(Δ2' + y - Δ1')
.
As
in Case 1, we observe that f(Δ2,y) depends only on λ in the case of
the exponential damage function. The Lagrangian function hence becomes
g(Δ1) - λΔ1 + μy
if λ > (f(λ') - g(Δ1'))/(Δ2' + y - Δ1')
L(x*,y)
=
f(λ)-λ(Δ2 + y)+μy if λ < (f(λ') -
g(Δ1'))/(Δ2' + y - Δ1')
g(Δ1) - λΔ1 + μy if
y > y'
=
f(λ) - λ(Δ2 + y) + μy if y < y'
where,
as in Case 1, we substituted Δ2 + y for x2 and where y'
is the solution to the equation
y = (f(λ) - g(Δ1λ))/λ - (Δ2λ(y)
- Δ1λ) .
Note
that L(x*,y) is continuous at y = y'. Since L(x*,y) is piecewise linear in y,
the minimum occurs either at y = 0 or at the solution y = y' to
y = (f(λ) - g(Δ1λ))/λ - (Δ2λ(y)
- Δ1λ) .
(It
is easy to show that the function L(x*,y) is always positive for y positive.)
Calculating
the value of L(x*,y) for these two values, we have
L(x*,0) = f(λ) - λΔ2(0)
and
L(x*,y) = g(Δ1) - λΔ1 +
μy'
= g(Δ1)
- λΔ1 + μ((f(λ) - g(Δ1))/λ - (Δ2(y') - Δ1)).
To
minimize L(x*,y) we hence choose y to be
0 if μ > λc
y* =
y' if μ < λc
where
c = [(f(λ) - g(Δ1))/λ - (Δ2(0)
- Δ1)] / [(f(λ) - g(Δ1))/λ - (Δ2(y') - Δ1)],
and
either value if μ = λc.
Let
us denote the attacker's optimal solution corresponding to y* by
x* = x*(y*)
0 or x' if y* = y'
=
x" if y* = 0
for
Case 1 targets, and
x1' or x2' if
y* = y'
=
x" if y* = 0
for
Case 2 targets.
Both
x* and y* are zero for Case 3 targets; that is, the only targets worth
attacking are those worth defending. Note that, since f'(x,0) > g'(x) for
small x, x" > x1' for small x1'. Further, since
f'(x - y,y) < f'(x - y,0), we have x" > x2' - y'.
An
unfortunate aspect of the solutions obtained by the double Lagrange multiplier
method is that, for specified resource levels (X and Y), there may be several
solutions, corresponding to different values of the Lagrange multipliers (μ and
λ). While all such solutions are optimal for the attacker, only one of them is
also optimal for the defender. We shall refer to this latter solution as the
"correct" optimal solution. (The others are referred to as
"spurious".) The next three sections well describe the Lagrangian
solutions in further detail, and which of them are optimal for both the
attacker and the defender simultaneously (i.e., which combinations
correspond to "correct" optimal solutions.)
We
shall now observe some properties of the attacker's optimal solutions. The
salient characteristic of the solution is that the attacker attacks each target
at a level for which the slope of damage curve is the same (λ). It is noted
that the defender either allocates no interceptors to a target, or y'
interceptors to a target, where y' is the level such that the line of slope λ
tangent to the damage curve at the attack level x > y' either passes through
the origin (in Case (1) in which g'(0) < λ), or is also tangent to the
damage curve at the attack level x < y' (in Case (2) in which g'(0) > λ).
This situation is illustrated in Figures A-8, A-9, and A-10.
(Concerning
Figure A-9: Since f'(0,x) > g'(x), there must exist Δ > 0 and y > 0
such that f'(Δ,y) = λ in this case. Note that x" > x1'
holds only if x1' is small.)
(Concerning
Figure A-10: Since f'(0,0) > g'(x), there is no x such that g'(x) = λ.)
Note
that the attacker chooses his solution after observing at each target whether
the defender defends at level 0 or y'. For reasons that will be explained
later, the attacker can attack some targets at the low level (0 for Case 1
targets and x1' for Case 2 targets) only if the defender is
defending all Case 1 and Case 2 targets at the higher level (y').
In
summary, the optimal solution for the attacker has the following properties:
1. The marginal
payoff to the attacker on all targets attacked is λ.
2. On all defended "Case 1" targets,
the ratio of damage to number of weapons is λ; on all defended
"Case 2" targets, the ratio of damage to number of weapons is greater
than λ, and this ratio is greater for the solution x1' than the
solution x2'; on all undefended Case 1 or Case 2 targets, the ratio
is greater than λ.
If
all Case 1 or Case 2 targets are defended, the total number,
Ymax(λ) == Σ yi'
where
the symbol Σ denotes summation; if all Case 1 and Case 2 targets are defended,
and attacked at the highest optimal level, the total number of weapons used is
Xmax(Ymax(λ)) == Xmax(λ)
= Σ x2i' ;
if
all Case 1 and Case 2 targets are defended, and attacked at the lowest optimal
level, the total number of weapons used is
Xmin(Ymax(λ)) == Xmin(λ)
= Σ x1i' ;
if
all Case 1 and Case 2 targets are not defended, but are attacked at the optimal
level, the total number of weapons used is
X(Y,λ)│Y=0 = X(0,λ) == Σ x3i' ;
where
we define
0 on Case 1 targets
x1i' = x1' on Case 2
targets
0
on Case 3 targets
(corresponding
to minimal attack, maximal defense);
x' on Case 1 targets
x2i' = x2' on Case 2
targets
0 on Case 3 targets
(corresponding
to maximal attack, maximal defense); and
x" on Case 1 or
Case 2 targets
x3i' =
0 on Case 3 targets
(corresponding
to an attack against no defense).
The
following characteristics of the defender's solution are noted:
1. For the complete defense, Y = Ymax(λ),
the attacker can choose not to attack any (or all) of the Case 1 targets or to
attack any of the Case 2 targets at the lower level, x1', and the
resulting deployments (attack and defense) are optimal at the new level x,
Xmin(λ) <
X < Xmax(λ) .
This characteristic results from the defender's
having chosen the defense so that the tangent at slope λ passes through the
origin (Case 1) or through both points of tangency (Case 2). The attacker is
thus indifferent to attacking at the level 0 or the level x' (Case 1), or to
attacking at the level x1' or x2' (Case 2). The damage
increases linearly (with slope λ) for all X, Xmin(λ) < X <
Xmax(λ) (this will be proved later).
2. If the defender chooses not to defend some
Case 1 or Case 2 targets, and the attacker also chooses not to attack
some defended Case 1 targets or to attack some defended Case 2 targets at the
lower level, then the resulting deployment is not optimal for the given
resource levels, X and Y, even though the deployment would be the optimal one
for the given values of λ and μ, if λ and μ represented true marginal costs of
weapons and interceptors. This paradoxical situation arises since, using the
double Lagrange multiplier method, there may be many different values of λ and
μ that correspond to the same resource levels. (See Reference 3 for a
discussion of this point). In the preceding situation, there would be a larger
value of λ that would correspond to the same total numbers of weapons and
interceptors deployed.
The
defense would prefer this latter deployment since it results in lower payoff to
the attacker. This follows since, for Xmin(λ) < X <
Xmax(λ), the payoff to the attacker is the same per weapon (beyond
the payoff of the "Xmin(λ) weapons"):
Payoff = λ(X - X0) .
For
λ1 < λ2, the payoff λ1X01 of the
"Xmin(λ1) weapons" is greater than the payoff λ2X02
of the "Xmin(λ2) weapons." Also, λ1X
< λ2X. Hence
Payoff for λ1 = λ1(X - X01)
< λ2(X - X02) = Payoff for λ2.
Hence
the defender would choose the deployment corresponding to λ2. Thus
we see that the attacker can attack on the range Xmin(λ) <
X < Xmax(λ) only if the defense is "complete"
(i.e., the defender defends at level y' in all Case 1 and Case 2 targets).
We
shall now determine which solutions are simultaneously optimal for both
the attacker and the defender.
In
the preceding section, we showed that the pair (μ,λ) corresponding to the
correct solution cannot correspond to a partial defense and a partial attack.
Rather, the correct (μ,λ) must correspond either to a complete attack, partial
defense, or to a complete defense, partial attack. We also provide that in the
complete defense case, in which Xmin(λ) < X < Xmax(λ),
if two different choices for (μ,λ) correspond to the same resource levels, the
"better" solution corresponds to the larger value of λ. In view of
the possibility of there being many different choices (μ,λ) that correspond to
the same resource levels, it is necessary to answer the following question:
How is it possible to find (μ,λ) corresponding to the solution optimal for the
specified resource levels? Our objective is twofold: (1) to make certain that
the correct (μ,λ) pair is included among all (μ,λ) pairs identified as
corresponding to the specified resource levels; (2) to test each such (μ,λ)
solution to determine if it is optimal.
In
view of the results of the preceding section, if the correct solution is
included in the set of (μ,λ) pairs identified as meeting the constraint levels,
then we will be able to select it in the complete defense case. Hence our
problem is solved for the complete defense case if we can prove that the
correct solution is among those identified.
We
can prove the correct solution is in fact included, by the following argument.
We will show that there is only one permissible choice of λ corresponding to
the complete defense case. Since the correct solution must correspond to the
complete defense case. Since the correct solution must correspond to some choice
of (μ,λ) that meets the resource constraints, and this choice is the only
permissible one, it must then be the correct solution. (There may indeed be
other values of λ which satisfy the resource constraints, but they will
correspond to partial defenses and attacks, and hence to spurious solutions.)
Note
that for values of λ greater than max(i) (Pi,βi), no
weapons and no interceptors are allocated to any target. Furthermore, as λ is
decreased to zero, the maximal number of weapons that are allocated increased monotonically
(but discontinuously) from zero. For μ > λ, no interceptors are allocated,
and for all μ < λ, the allocation is the same (all Ymax(λ)
interceptors). The upper interceptor limit increases monotonically (and
continously) as λ decreases. Hence, if we are allocating for a complete
defense, partial attack, there is only one value of λ which will meet
the defense level constraint. Hence we have the correct solution (i.e., the
solution which is simultaneously optimal for both attacker and defender) in the
complete defense case (Xmin(λ) < X < Xmax(λ)).
Note
that there may be no choice of (μ,λ) corresponding to the specified
defense and attack levels. For example, in the complete defense, minimal attack
situation, the minimal attack resource level may exceed the specified attack
resource level. In this case, we have no solution to the problem for the
specified resource levels, by the Everett-Pugh double Lagrange
multiplier technique. It is nevertheless possible to determine an optimal
solution in this case using the single Lagrange multiplier technique, by
the following reasoning. Consider the complete defense, minimal attack
situation, in which the defender defends all Case 1 and Case 2 targets, and the
attacker attacks all such targets at the minimal level (x1'). The
attacker deploys Xmin(λ) weapons in this case. If the attacker
wishes to use fewer than Xmin(λ) weapons, he must allocate his
weapons so that the marginal payoff per weapon is the same for all targets.
That is, he chooses a new value of λ, greater than λ', and chooses x' so that
g'(x') = λ'. Clearly, he will attack all targets with a number of weapons that
is less than x1', and hence less than the number of interceptors.
Since this is the case, the defender has no need to adjust his defense. He can
maintain the same defense no matter how many weapons (less than Xmin(λ))
the attacker allocates, since in every case there are fewer weapons than
defenders. Additional interceptors have absolutely no effect on the payoff.
The problem hence reduces to one of simply allocating the attacker's weapons,
using g(x) for the payoff function. Since the total number X(λ) of attackers
allocated, given λ, is a monotone decreasing function of λ. this is easily
accomplished. Note that the defense can rearrange his allocation any way he
pleases, so long as y > x on every target, and the resulting
allocation is still optimal. Only X(λ) of the interceptors are actually
needed.
Thus
we have the correct solution in the case in which X < Xmin(λ).
The
final case to consider is the complete attack case in which X > Xmax(λ).
For a specified number of defended targets, both Y(λ) and X(Y(λ),λ) increase as
λ decreases. However, there may be several different numbers of defended
targets for which λ = λ' can be chosen so that X(Y(λ'),λ') = X and Y(λ') is
close to Y. (Owing to the discrete nature of targets, it in general will not
be possible to meet the interceptor constraint exactly.) In the unlikely event
that Y(λ') is the same for two different values of λ', the better solution
corresponds to the allocation resulting in least damage. In general, however,
we will have several possible solutions, each using a different number of
interceptors and resulting in a different level of damage. The correct optimal
solution is the solution with Y(λ') < Y which has least damage. The
situation is illustrated in Figure A-11.
For
both Case 1 and Case 2 targets, the damage in the optimal attack (complete
attack case) is a function of λ only, i.e.,
Damage = f(x - y,y) = f(λ) = P(1 - λ/Pβ).
We
observe that the damage is a decreasing function of λ. Therefore, if there are
several different λ's for which the weapon constraint is met and for which the
interceptor constraint is not exceeded, then the defender will choose the
defense corresponding to the largest λ. Referring to Figure A-11, the optimal
solution is hence the rightmost one (corresponding to total resource levels X,
Y2), in which the maximum number of targets is defended.
A
useful way to summarize the several preceding observations is to plot the
payoff for optimal solutions corresponding to varying attack levels for a fixed
defense level. Such a plot is shown in Figure A-12.
Before
summarizing the nature of the solutions corresponding to the different sections
of this curve, we recall the nature of the Lagrangian solutions on the three
types of targets.
For
Case 1 targets, the defender chooses a number, y, of interceptors and the
attacker chooses a number, x, of weapons, such that the tangent line to the
damage curve at x is of slope λ, and the tangent line passes through the
origin. (See Figure A-8.) For Case 2 targets, the defender chooses y, and the
attacker chooses x2 > y, so that the tangent line to the curve at
x2 is also tangent at a point x1 < y; furthermore,
this tangent line is of slope λ. (See Figure A-9.) Case 3 targets are neither
defended nor attacked. (See Figure A-10.)
Not
all of the points described above correspond to optimal solutions. Depending
on the circumstances (to be described) the attacker may be required to attack
only at the higher level, or the defender may be required to defend only at the
higher level. We shall now describe the situation using Figure A-12, which
depicts total damage, H(X,Y) as a function of X, for fixed Y.
In
the first section of the curve, all Case 1 and Case 2 targets are defended, and
all are attacked. The defense is greater than necessary in this region, for
there are more interceptors than weapons on each target. The defense is
somewhat arbitrary here; it can be rearranged in any fashion so long as there
are always more interceptors than weapons on each target. The attack
corresponding to a specified X is unique. Both the interceptor and weapon
constraints are met exactly.
In
the second section of the curve, all Case 1 and Case 2 targets are defended,
and the defense is unique (or "stable"). The attacker may attack
each target at either the low level or the high level, and he does so in any
fashion which enables him to meet his weapon constraint, X. The interceptor
constraint, Y, is met exactly, but the weapon constraint may only be
approximated, owing to the discrete nature of weapons and interceptors. (We
refer to this error as the "small change" effect.) Thus there are
actually only a finite number of Lagrangian solutions along the linear portion
of the curve corresponding to all possible combinations of attacks at the high
or low attack levels on each target. Payoffs corresponding to total attack
levels lying between these points lie slightly below the line defined by the
payoffs of the Lagrangian solutions.
The
first two sections of the curve represent what is called a "defense
dominant" situation.
In
the third section of the curve, all Case 1 and Case 2 targets are attacked at
the higher level, but only a subset of the Case 2 targets are defended. The
defended targets have the following property. Let λ denote the value of the
(attacker's) Lagrange multiplier in the optimal attack. Suppose, now, that no
targets were defended, and that this same value of λ were used to determine the
number of weapons to be allocated to each target. Let us denote the damage to
the i-th target in such an attack by Di, and the number of weapons
by Ni. Consider the ratio Ri = Di/Ni.
If all Case 1 and Case 2 targets are arranged in decreasing order of Ri,
then the defended targets of the optimal attack are at the beginning of this
list. In other words, the defender defends targets in decreasing order of
their undefended damage per weapon.
Both
the defense and the attack are unique in this section of the curve. The weapon
constraint is met exactly, but the interceptor constraint may only be
approximated. This section of the curve represents the "attack
dominant" situation.
In
the third section of the curve, there may be several different values of λ,
corresponding to different numbers of defended targets, which enable us to meet
the weapon and interceptor constraints. The defender naturally chooses the
defense allocation which corresponds to the least damage. In the present
problem, this happens to the solution corresponding to the largest value of λ,
since in the attack dominant case the damage on the i-th target is given by
Pi(1 - λ/Piβi)
.
It
is of some interest to describe the nature of the solution as a function of the
Lagrange multiplier λ. We summarize the situation in Figure A-13 through A-17
(ignoring the "small-change" effect caused by discrete weapons and
interceptors).
Figures
A-14 and A-15 illustrate the ranges of total defense and attack levels corresponding
to optimal attacks for different values of λ.
Note
that it is not possible to obtain an optimal solution for every choice of X and
Y, by the method of double Lagrange multipliers. If Y is very large and X is
very small, there may be no value of λ for which Xmin(λ) < X and
Y < Ymax(λ). (This region is called a "gap". Regions
such as this, which are inaccessible by the Everett-Pugh procedure of
min-maxing the Lagrangian function (as opposed to zeroing its derivative, in
the case of continuously differentiable functions), represent
"inefficient" solutions. (See Reference 2 for a discussion of
gaps.) As discussed previously, however, we were able in the present problem
to find an optimal solution over this gap. (Another type of gap occurs since
the discrete nature of targets prohibits meeting both resource levels exactly.
This "small change" effect is generally small, however, for problems
involving several targets and large numbers of weapons and interceptors.)
Figure
A-16 is a plot of the payoff (denoted by H(X,Ymax(λ))) corresponding
to all possible optimal attack levels, for constant λ and Y = Ymax(λ).
(This plot is simply the middle section of Figure A-12.)
Figure
A-17 is a plot of the payoff (denoted by H(X(Y,λ),Y)) corresponding to all
possible optimal defense levels, for fixed λ.
The
plot of Figure A-17 is a level line since f(Δλ,y) = (Δλ,0), as discussed previously.
In
view of the preceding characteristics of the optimal solution, a reasonable
procedure for finding the optimal solution (corresponding to Σ xi =
X, Σ yi = Y) is the following:
1. Determine the largest value of λ such that
Ymax(λ) = Y. Compute Xmin(λ) and Xmax(λ).
2. Complete defense, partial attack case. If
Xmin(λ) < X < Xmax(λ), then the
optimal solution is obtained by attacking a sufficient number of the (Case 1 or
Case 2) targets at the higher level (x2i') to satisfy the weapon
constraint, X. (Any such collection of targets is satisfactory. This is the
case since the additional damage caused in going from x1i' to x2i'
weapons on the i-th target is λ(x2i' - x1i'). Thus the
additional damage caused by the x2i' - x1i' weapons,
above the damage caused by the x1i' weapons, is the same linear
function of the additional weapons allocated, for all targets.) Since weapons
are allocated to targets in groups, it will in general not be possible to meet
the weapon constraint exactly.
3. Complete attack, partial defense case. If
X > Xmax(λ), then decrease λ to the largest value of λ such that
Xmax(λ) = X. An optimal solution is obtained by defending a
sufficient number of the (Case 1 or Case 2) targets to satisfy the interceptor
constraint, Y. The targets to be defended must be selected in order of
decreasing ratio in the no-defense case, of damage to weapons, until Y
interceptors are used. Unfortunately, however, if some defendable targets are
not defended, then fewer weapons are allocated (see Figure A-11). Hence our
weapon constraint is not met. We must hence decrease the value of λ (giving us
new values of Ymax(λ) > Y and Xmax(λ) > X), and
choose a new set of targets to be defended. As before, we select targets to be
defended in the (new) order of decreasing ratio, in the no-defense case, of
damage to weapons, until Y interceptors are used. We compute, for this defense
allocation, the corresponding number, X(Y), of weapons. We decrease λ until
X(Y) = X. Since interceptors are allocated to targets in groups, it will in
general not be possible to meet the interceptor constraint exactly. There may,
however, be a number of different solutions (corresponding to different numbers
of defended targets) using fewer than Y interceptors, and we should choose the
one resulting in least damage (largest λ).
4. Complete attack, unnecessarily large
defense. If X < Xmin(λ), no solution can be found by the method
of double Lagrange multipliers. Either fewer than Y interceptors must be used,
or more than X weapons must be used, to obtain an optimal solution by this
method. To find the optimal solution for the specified Y, we instead use the
single Lagrange multiplier method, and proceed as follows. Accept the defense
allocation corresponding to Xmin(λ), Ymax(λ) = Y. Then,
increase the value of λ, and compute the corresponding attack allocation.
Denoting the number of weapons deployed by X(λ), adjust λ so that X = X(λ).
This allocation is the optimal attack allocation. Denoting the number of
weapons deployed by X(λ), adjust λ so that X = X(λ). This allocation is the
optimal attack allocation. Any defense allocation for which the number of
interceptors on each target exceeds the number of weapons is optimal. Hence,
in particular, the defense allocation corresponding to X = Xmin(λ),
Y = Ymax(λ), is optimal.
A
computer program has been written to perform the above computations.
The
derivation presented above of the optimal solution includes a number of
implicit relationships. The solution will now be explicitly derived.
If
f'(0,0) < λ, no weapons or interceptors are allocated to the target.
We
have
f(Δ,y) = P(1 - exp(-βΔ - αy))
so
that
f'(Δ,y) = Pβexp(-βΔ - αy)
and
f'(0,0) = Pβ .
Thus
if Pβ < λ, no weapons or interceptors are allocated to the target.
In
this case, Pβ > λ and g'(0) < λ. We have
g(x) = P(1 - exp(-αx))
so
that
g'(x) = Pαexp(-αx)
and
g'(0) = Pα .
Thus
if Pα < λ, the situation is that of Case 1. In this case, we wish
first to determine x,y > 0 such that the tangent line at the point x is of
slope λ and passes through the origin. That is, find x,y such that
f'(x - y, y) = λ
and
f(x - y,y)/x = λ .
The
first relation implies
Pβexp(-β(x - y) - αy) = λ
or
exp(-β(x - y) - αy) = λ/Pβ .
Substituting
this into the second relation, we have
P(1 - λ/Pβ)/x = λ
or
x = P(1 - λ/Pβ)/λ .
The
first relation then yields
y = (ln(λ/Pβ) + βx)/(β - α).
If
y = 0, then x must satisfy
f'(x,0) = λ
i.e.,
Pβexp(-βx) = λ
or
x = (-1/β) ln(λ/Pβ) .
Case
2 corresponds to Pα > λ (Pβ > holds since α < β). In this case, we
wish first to determine x1, x2, and y, where x1
< y < x2, such that the tangent line at the point x2
is of slope λ, the tangent line at the point x1 is of slope λ, and
these tangent lines are in fact the same line. That is, we want x1,
x2, y such that
g'(x1) = λ
f'(x2 - y,y) = λ
(f(x2 - y,y) - g(x1))/(x2
- x1) = λ.
The
first relation yields
exp(-αx1) = λ/Pα
or
x1 = -(1/α)(ln(λ/Pα)) .
The
second relation yields
exp(-β(x2 - y))exp(-αy) = λ/Pβ .
Substituting
the first two relations into the third hence yields
(P(1 - λ/Pβ) - P(1 - λ/Pα))/(x2 - x1)
= λ
or
x2 = x1 + 1/α - 1/β .
The
second relation yields
y = (ln(λ/Pβ) + βx2)/(β - α) .
In
the case in which y = 0, we wish to find x such that
f'(x,0) = λ .
As
is Case 1, we obtain
x = -(1/β)(ln(λ/Pβ)) .
1.
Hugh Everett, III, Defense Models XI: Exhaustion of Interceptor Supplies,
Lambda Paper 17, Lamdba Corporation, Arlington, Virginia, 1968. (Lambda
Corporation later became a subsidiary of General Research Corporation, McLean,
Virginia.)
2.
Hugh Everett, III, "Generalized Lagrange Multiplier Method for Solving
Problems of Optimum Allocation of Resources," Operations Research,
11:399-411, 1963.
3.
George E. Pugh, "Lagrange Multipliers and the Optimal Allocation of
Defense Resources," Operations Research, 12:543-567, 1964.
4.
Robert L. Goodrich, Defense Models V: Ivan II, A Detailed Model for Preferential
Defense, Lambda Paper 7, Lambda Corporation, Arlington, Virginia, 1968.
FndID(168)
FndTitle(Optimal
Attack and Defense for a Number of Targets in the Case of Imperfect
Interceptors)
FndDescription(This
article determines the optimal allocation of attacking missiles and defending
interceptors to targets, in the case of imperfect interceptors.)
FndKeywords(ballistic
missile warfare; ballistic missile defense; resource-constrained game; min-max
solution; generalized lagrange multipliers)