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

strategies of the ship as those of the token can be discussed. Kiniwa and Kikuta [ 11 ]
improved the superstabilizing protocol by taking a mixed strategy into consideration
in two-person zero-sum game. In their chapter, the process holding a token issues
a sub-token with some probability. However, their model is so simple and ignores
empirical probability of failures. It follows that the adversary always aims to bring
about a failure. Thus, an unlikely failure may frequently occur against our intuition.
In this chapter, we incorporate an empirical failure probability into our model,
and adapt our idea to a practical case. We consider that the terrorist cannot make
a decision until the naval mine is prepared, where the mine-preparing probability
is empirical. We interpret an interval between failures as a state that a mine is not
prepared and is followed by a state that a mine has been prepared but not laid yet.
By adjusting the mine-preparing probability, we can use our idea in practice.
Our topic is related to a well-studied problem, called a sequential inspection
game, consisting of an inspector and an inspectee, or customs and a smuggler, re-
spectively [ 1 , 5 - 7 , 9 , 12 , 15 ]. It was originally started by Dresher[ 4 ] as arms control
and disarmament. That is, the customs patrols in order to stop the smuggler attempt-
ing to ship a cargo of perishable contraband across a strait. The customs has limited
resources, i.e., the number of boats, and can patrol only during k of n nights. The
smuggler ships the cargo of contraband during l of n nights, where l 1 in its orig-

inal work. When the smuggling coincides with the patrol, the smuggler is captured
with probability q , where originally q

=

= 1. The modeling and the technique of this

chapter is due to the inspection game.
The difference between our problem and the inspection game is as follows. First,
in the inspection game, the inspectee may be captured, while in our problem not.
On the contrary, the inspector in our problem may suffer severe damage. Second,
the inspection game plans the number of the inspectee's illegal actions in advance,
while our problem does not and the number of mine-laying is very rare. Third, the
inspection game has the upper bound of the number of patrols, while our problem
considers it as a cost.
The rest of this chapter is organized as follows. Section 8.2 states our model.
Section 8.3 includes one stage case which presents our fundamental idea and an idea
of mine-preparing probability. Then, for the iterated circulation of a ship, we have
several interpretations. First, Sect. 8.3.1 considers that player A corresponds to a
fleet of ships and our game continues after a ship suffers damage. Second, Sect. 8.3.2
considers that player A corresponds to only one ship and our game terminates when
the ship suffers damage. Third, Sect. 8.4 changes the assumption adopted in previous
sections and compares two boats case with one boat case. Fourth, Sect. 8.5 shows our
application to distributed failure detection. Then, Sect. 8.6 concludes the chapter.
Finally, Appendix refers to our distributed failure detection protocol.

8.2 Model

A fleet of ships transport (or a ship transports) goods/materials on a circular route,
a ring , again and again. Since there is a risk that a terrorist may lay a naval mine
on the route, it is sometimes necessary to take a scout along the route by using