Tools to Manage Search Games on Lattices - Search Theory: A Game Theoretic Perspective - page 27

not linear but cyclic, then we may take , considering point 1 as next

to point m . Therefore, if the situation is carried out in a finite set of points placed
on a perimeter, the strategies for the players can also be represented by subsets of
L . Figure 3.1 shows how the moving of a point on a linear set over time can be
represented on the lattice. Games where the search is developed on a star graph, as

{ 1 , 2 ,..., m }

Fig. 3.1 Representation, on the lattice L = { 1 , 2 ,..., 8 }×{ 1 , 2 ,..., 7 } , of the moving of a point on

the linear set { 1 , 2 ,..., 7 } over eight consecutive periods of time

considered by Gal in Chap. 1 , Sect. 1.3 of the topic, can also be modeled on L by
imposing appropriate constraints on the strategies for the players. The nice topic by
Ruckle, Geometric games and their applications , which is discussed in Chap. 6 of
the topic, also includes a number of games on the lattice L . Most of the problems on
lattice games that can be found in that topic remain open. More games on the lattice
L can be found in [ 2 , 3 , 8 , 9 , 11 ].
Here we are going to deal with two-person search games on the lattice L ;they
are win-loose games, and, therefore, zero-sum games. One interesting problem is
to obtain results or to develop methods to attack the resolution of games with com-
mon characteristics. In the following section we present a method to simplify the
resolution of games on a finite set that satisfy some general properties. Section 3.3
shows how this method can be applied when the finite set is a lattice L .Twogames
of this kind are solved in Sect. 3.4 . These games are interesting in themselves, but
their resolution is also useful to illustrate the proposed method.
Let us consider the following situation. A hacker gets information from 20
computers, C 1 , C 2 , ..., C 20 , of an enterprise. Each day he picks information
from each of the computers, but for the information obtained for one computer
to prove trustworthy, he has to verify it at least k times. The company performs
one inspection each day of all the computers. If a leak is detected, a protection
system is set in motion which invalidates the information that can be obtained dur-
ing that day. The hacker must select, every day, the computers and the hours at
which he will make the incursions. He has to do this bearing in mind, first, that
the importance of the data depends on the responsibility of the person who uses
the computer and, secondly, that he cannot make more than s contacts during a
day. This problem can be modelled as a two-person zero-sum game on the lattice