Information Technology Reference
In-Depth Information
The situation can then be considered as a two person zero-sum game
by
choosing an appropriate payoff function to Infiltrator; the one favoured is 1 if Infil-
trator's point is not in either of the intervals chosen by Defender and 0 otherwise.
More formally
Γ (
a
,
b
)
Γ (
a
,
b
)
can be regarded as the two person zero-sum game with strat-
egy spaces
[
0
,
1
]
and
[
0
,
1
] × [
0
,
1
]
with payoff function f to Infiltrator given by
0 f x
[
y
,
y
+
a
] [
z
,
z
+
b
] ,
f
(
x
, (
y
,
z
)) =
1oth rw e
.
This formulation makes use of the fact that the position of an interval is determined
by describing where its left-hand endpoint is located.
Ruckle [ 11 ] found a complete solution for
Γ (
,
)
=
a
b
when a
b andalsoforsome
particular numerical values of a and b
.
Baston and Bostock [ 2 ] solved the game for
the case b
1
/
2andLee[ 8 ] extended their results to cover all cases for which a
b
and 1
2 as well as producing some bounds for other cases. Further, less
easy to describe, results have been obtained by Zoroa, Zoroa and Fernández-Sáez
[ 15 ]. On a slightly different tack, Garnaev [ 6 ] considered a discrete version of the
game in which play takes place over an integer interval
/
3
b
<
1
/
[
1
,
n
]
; further details of this
and similar games can be found in Garnaev [ 7 ].
In the chapter mentioned above, the approach was to nominate explicit strate-
gies for the players and show that they were optimal. However Woodward [ 13 , 14 ]
has adopted a different approach by investigating the structure of the more gen-
eral continuous game in which Defender has n barriers. He demonstrated that it is
equivalent to a finite game in the sense that the games have the same value and
that optimal strategies in the finite game remain optimal when transferred to the
continuous game. This enabled him to use linear programming for the continuous
game and, in [ 14 ], he solved the three barrier game for lengths a 1
a 2
a 3
1
/
4
and some additional cases where a 3
Woodward has also shown that his fi-
nite game is equivalent to Garnaev's discrete game generalized to n barriers. On a
slightly different tack, Baston and Kikuta have considered two variations of the n
barrier continuous game. In [ 3 ] Infiltrator may send more than one agent down the
channel and the players have limited information available to them whereas, in [ 4 ],
Infiltrator has a positive width and a proportion of the width needs to be detected for
a positive identification.
In this paper we develop the approach used by Woodward [ 14 ], concentrating on
the structure of the game
1
/
5
.
Γ (
,
)
and, in particular, on the structure of its optimal
Defender strategies in the finite game which Woodward showed is equivalent to
Γ (
a
b
The
result was first obtained by the second author in his Ph.D. thesis [ 14 ] but the methods
of proof here are radically different and much shorter than those in the thesis. An
interesting aspect of the proofs is that, unlike previous work on the game, we do
not at any stage nominate explicit strategies for the players and show that they are
optimal. The value of
a
,
b
) .
This enables us to find the value of
Γ (
a
,
b
)
for all values of a and b
.
is given in terms of the minimum of a finite number
of terms; loosely speaking the number of terms increase as the length of the longer
interval decreases. Applying our result to the case a
Γ (
a
,
b
)
b and 1
/
3
b
1
/
2
,
we
provide a much simpler expression for the value of
Γ (
a
,
b
)
than that of Lee [ 8 ].
Search WWH ::




Custom Search