Effective Search for a Naval Mine with Application to Distributed Failure Detection - Search Theory: A Game Theoretic Perspective - page 115

an unmanned reconnaissance boat. If the boat finds a naval mine, a crew on the
ships can remove it by remote control. On the shipping route, there are n ports
( n 1), 1 where the crew on the ships makes a decision whether or not it dispatches

the reconnaissance boat. Notice that the ships cannot move while the boat circulates
a ring if it is dispatched once.
It is assumed to be very rare that a terrorist lays the naval mine. Therefore, it is too
costly to dispatch the boat every arrival time to each port. So we have two choices,
to dispatch the boat and not to dispatch the boat. The actual decision of the dispatch
is modeled by the mixed strategy in a two-person zero-sum game. An interval while
the transport ships move one port to another is called a stage , which may contain
a circulation of the reconnaissance boat or not. We consider different multistage
games

>

α
be the reward that the reconnaissance boat finds and handles the naval mine, and let
β

Γ ( k ) , where the maximum number of stages is assumed to be k = m .Let

be the loss that the transport ships suffer damage without dispatching the boat.
Let 1bethecost n of circulating the boat plus the reward 1 of moving the

ships to the next port. The ships safely proceed to the next port without circulating
the boat with reward 1. We assume 1

− n +

because the removal of risk does not
make money, while the crash of a ship incurs high cost. Since the crews' purpose is
to proceed the ships, we do not consider the successful ship moving as a cost but as
areward.
Furthermore, we make the following assumptions.
1. The mine laid by a terrorist is surely removed by a reconnaissance boat if it
is dispatched. The ship without dispatching a boat surely suffers damage if the
mine is laid.
2. The mine may be laid on the route at each beginning of a stage. So, we assume
that the mine is not laid immediately after the boat has passed.
3. The number of stages m is sufficiently larger than the interval during which
failures occur.
4. Any distance between neighboring ports is almost the same for simplicity. So,
it takes n units time for a boat to circulate the ring.
Notice that the assumption 2 is used only in the games in Sect. 8.3 . It is replaced
by another assumption in Sect. 8.4 .

< α < β

8.3 Two-Person Zero-Sum Game

In this section, we first consider a game with m 1, and then consider two multi-

stage games containing mine preparation. The transport ships, player A, use a mixed
strategy a

=

such that he dispatches the reconnaissance boat with prob-
ability p and does not dispatch it with probability 1

=( p , 1 − p )

− p . On the other hand, the

terrorist, player B, uses a mixed strategy b such that he lays a naval

mine with probability q and does not lay it with probability 1

=( q , 1 − q )

− q .

1

In Sect. 8.4 , we assume n > 2