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