SEARCH AND EVASION GAMES.
Abstract
The author develops some two-person zero-sum formulations of search and evasion problems. By employing a game theoretic approach, he allows the hider, as well as the searcher, to choose a strategy. This is in contrast to most search models which assume a stationary or passive hider. Both non-sequential and sequential search games are investigated. Some interesting aspects of the non-sequential game and an example of an antisubmarine search problem are given. The sequential games consist of a sequence of moves. When the players move, they not only determine a payoff but also the probability that the game terminates before the next move. When at most a finite number of moves is allowed, he proves that a solution may be found by solving a recursive sequence of matrix games. When the number of moves is not bounded, the game is characterized by a special type of non-linear program. The solution to this program can be approximated by successive perturbations of a related linear program. He obtains the result that a pair of strategies minimaxes the expected duration of the game if and only if these strategies also maximin the probability of termination in one step. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1966
- Accession Number
- AD0639921
Entities
People
- Roger G. Schroeder
Organizations
- Naval Postgraduate School