Information Technology Reference
In-Depth Information
Let
F
n
,
m
denote the set of all the functions from
{
1
,
2
,...,
n
}
to
{
1
,
2
,...,
m
}
,that
is
F
n
,
m
consists of all subsets of
L
which have a single point in each column, and let
0
F
n
,
m
denote the subset of
F
n
,
m
containing the functions such that
f
(
i
+
1
)
equals
one of the three values
f
. The lattice games presented by
Ruckle in [
5
] are the Lattice Ambush Game (LAG), the Lattice Search Game (LSG),
the Lattice Penetration Game (LPG), and those obtained from these on laying out the
lattice on a cylinder, the Cylindrical Ambush Game (CAG), the Cylindrical Search
Game (CSG) and the Cylindrical Penetration Game (CPG).
In the LAG the set of strategies for player I is
(
i
)
,
f
(
i
+
1
)
,or
f
(
i
−
1
)
n
F
m
, the set of strategies for
,
player II is
F
n
,
m
and the payoff to player I is 1 if both players do not meet, and zero
otherwise. In the LSG the sets of strategies for both players are the same as in the
LAG and the payoff to player I is equal to 0 if they do not meet and 1 if they meet. In
the third game, the LPG, player I receives a payoff equal to his degree of penetration
in the lattice if he is not intercepted, and 0 otherwise. The set of strategies of player
Iis
0
0
n
F
n
,
m
.The
CAG, CSG and CPG are games that have the same set of strategies for player II
and the payoff functions are equal to those of the LAG, LSG and LPG respectively,
but player I is allowed to pass from one edge of the lattice to another. For all these
games Ruckle obtains results for some special cases, but the general solutions are
not obtained.
Although there has been activity in the study of games on the lattice [
1
,
6
-
8
],
there are few results on lattice games. The CAG is studied in [
7
] where it is called
ambush game over time on a cyclic set; it is solved for the cases
n
F
1
,
m
∪F
2
,
m
∪···∪F
m
and the set of strategies for player II is
,
=
2,
n
=
3,
m
. Bounds for the value of the
game are also obtained, but the general solution is not obtained. Patrolling games on
different graphs are studied in [
1
], the games studied when the graph is a line graph
are similar to the LSG and the CSG, but in these games the attacker attack just one
node along a period of time of length
k
. Properties for the optimal strategies for the
players and the solution for some particular cases are obtained. Ruckle remarks that,
among the games on the lattice, the hardest to handle are the lattice games, because
of the combinatorial difficulties involved. In an attempt to shed some light on lattice
games we have studied the sets of strategies of the players and we have obtained the
cardinalities of all the sets involved in these games.
>
3
(
n
−
1
)
and for some cases when
m
=
3
(
n
−
1
)
A two-person zero-sum game will be expressed by
G
=(
X
,
Y
,
M
)
where
X
,
Y
are
the sets of pure strategies for players I and II, respectively, and
M
:
X
×
Y
→
R
(7.1)
is the payoff function which represents the winnings of player I and the losses of
player II. Player I chooses a strategy
A
∈
X
, player II chooses a strategy
B
∈
Y
and
these choices determine the payoff
M
to player II.
Throughout this chapter
X
and
Y
are finite sets, therefore a probability distribu-
tion on
X
, that is to say, a mixed strategy for player I, can be written as a function
(
A
,
B
)
to player I and
−
M
(
A
,
B
)
x
:
X
→
R
Search WWH ::
Custom Search