Information Technology Reference
In-Depth Information
contains w so must A λ i (
By definition, B i
starts to the left of A λ i (
j
) .
(
j 1 )
j 1 )
and
A λ i (
starts to the left of B i
As A λ i (
and B i
j
)
(
j
) .
j
)
(
j
)
are in the same covering, as
are A λ i (
and B i
cannot be of the form A λ i (
or B i
)
(
) ,
(
)
)
(
)
∈{
,
}
j 1
j 1
I C
w
j 1
j
for i
q
s
and we have a contradiction. Thus there are at least 2
(
s
λ s + λ q
q
)
pure strategies
in S which have intervals containing w and the theorem follows.
From Theorems 1 and 3 we have
<
/
,
Theorem 4. Fo r a
b
1
2
s
λ s + λ q
q
v
(
a
,
b
)=
1
max
.
s
λ q
q
λ s
Λ + ,
Λ
s
q
Note that when q
= λ q , (
s
λ s + λ q
q
) / (
s
λ q
q
λ s )=
1
/
q
.
9.7 Comments on Our Results
Although we have obtained its value, we have not produced explicit optimal strate-
gies for either player in the general game. Evidence suggests that Infiltrator optimal
strategies are more difficult to find than optimal Defender strategies and Woodward
[ 14 ] has produced explicit Defender strategies for all values of a and b
Indeed find-
ing an optimal Defender strategy is fairly straightforward using arguments similar
to those employed for the special example in Sect. 9.5 . Once the value of the game
is obtained, one can find s
.
Λ + and q
Λ such that v
(
a
,
b
)=
1
G
(
s
,
q
)
so that
the family
in Sect. 9.6 can be constructed. Algorithms exist for finding systems
of distinct representatives (see, for instance, Marshall Hall [ 9 ])andthenastrategy
can be obtained as in the proof of Theorem 3 .
Of course Woodward's result [ 13 ]that
B
is equivalent to a finite game
means that optimal strategies for any particular values of a and b can be obtained
by using linear programming. In practice matters are not that straightforward be-
cause the strategy spaces in Woodward's finite game can be comparatively large;
for instance, in the example in Sect. 9.5 , the Defender has 81 and the Infiltrator
9 pure strategies. Furthermore, as mentioned in Chap. 6 , linear programming can
give very different optimal strategies for two games with slightly different values
of a and b even though they have the same value. By contrast, our approach not
only enabled the example to be solved easily but tells us that games with val-
ues of a and b
Γ (
a
,
b
)
Λ + and
Λ as a
=
/
a which give rise to the same
6
21 and
=
/
(
,
)
b
7
21 also have the value 5/12. Thus games with
a
b
in the triangle with
vertices
(
1
/
4
,
1
/
3
) , (
1
/
3
,
1
/
3
)
and
(
1
/
4
,
3
/
8
)
and its interior with the closed line
segment joining
removed all have value 5/12. Defender
optimal strategies for these games are easily derived from Fig. 9.2 . Although optimal
Infiltrator strategies for the games are not quite so immediate, they follow a simi-
lar pattern to the particular example. Noting that the values of a and b in the given
region satisfy 1
(
1
/
3
,
1
/
3
)
to
(
1
/
4
,
3
/
8
)
a
2 b
<
0
,
intervals of length a and b can contain at most two
Search WWH ::




Custom Search