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

Chapter 3
Tools to Manage Search Games on Lattices

Noemí Zoroa, María-José Fernández-Sáez, and Procopio Zoroa

Abstract Search games on a network or a graph have been widely studied in the
literature. In some of these situations, the search space can be represented by the
lattice

L = { 1 , 2 ,..., n }×{ 1 , 2 ,..., m }

and the strategies for the players are subsets of this lattice. We develop a method
to simplify the resolution of games of this kind when they satisfy some general
conditions. Some games are solved, these are interesting in themselves, and their
resolution illustrates the usefulness of the obtained results.

3.1 Introduction

In this chapter we suggest a general approach to solve games on a lattice. Search
games where the search space can be thought as a network or graph have been
widely studied in the literature, [ 2 , 4 - 6 ]. In some of these situations, the search
space can be represented by the lattice

= { , ,..., }×{ , ,..., }.

L 1 2 n 1 2 m

It is clear that the lattice L can be applied to discretize a game in which the search
space is a rectangular region. The lattice can also be applied to search games that
are played over time. Consider, for example, a game like the patrolling game in [ 3 ]
in which the search space is the linear set and players move over n

consecutive periods of time. The lattice L represents the space-time network, by
depicting the nodes of the linear set vertically and time horizontally. If the set is

{ 1 , 2 ,..., m }