Search Games: A Review - Search Theory: A Game Theoretic Perspective - page 11

Gal [ 22 ] used a normalized cost function to find the minimax trajectory. The two
approaches lead to equivalent results (see [ 24 ]). This type of normalization was new
at that time but is now called the competitive ratio in the computer science litera-
ture, and has become a standard tool in analyzing online algorithms (see, e.g. [ 15 ]).
The online solution with a turn cost, d

is given by Demaine et al. [ 19 ]. The com-
petitive ratio remains 9 and but an additive constant of 2 d is added to the minimax
cost. It also turns out that optimal randomized strategies for searching the line in the
presence of turn cost have the same competitive ratio of about 4

,

. .

6

1.3.2 On the Optimality of Geometric Trajectories

It was shown by Gal and Chazan [ 28 ] that a minimax search trajectory for search
problem in unbounded domains, satisfying a unimodality condition, is always a geo-
metric sequence (or exponential functions for continuous problems). This result has
been developed in [ 24 ] as a general tool which just requires optimizing a function
with one variable (the generator of the sequence) instead of minimizing the com-
petitive ratio functional in the space of possible trajectories. This tool has been used
for the linear search problem and also in searching a set of rays (star search) and
searching in the plane using exponential spirals. It has also been used for minimax
search on the boundary of a region consisting of two rays in the plane. That problem
has been presented by Baeza-Yates [ 8 ], and solved by Gal using the general tool (see
[ 4 ], pp. 154-157).
Geometric trajectories are useful in other areas to produce effective algorithms,
as shown by Chrobak and others (see [ 17 ]). Competitiveness via doubling means
designing online and offline approximation algorithms by using geometrically in-
creasing estimates on the optimal solution to produce fragments of the algorithm's
solution. This method is illustrated by discussing several applications where dou-
bling is used. These areas, in addition to searching, include bidding, minimum la-
tency tours, scheduling, and clustering. It seems to have a promising potential for
other applications as well.

1.3.3 Searching on M Rays (Star Search)

The natural extension of the linear search problem to M 2 concurrent rays, has

been presented and solved by Gal [ 22 ]. It was later rediscovered in the computer
science literature, [ 8 , 32 ] as the 'cow path search'. Several applications in search
and other areas were presented. Gal showed that the optimal trajectory is periodic
(visiting each ray every M -th time) with monotone increasing step size. Thus, the
general tool, discussed on the previous section, takes the following form for the star
search:

>