Cumulative search-evasion games (CSEGs)

Abstract

Cumulative search-evasion games (CSEGs) are two-person zero-sum search-evasion games where play proceeds throughout some specified period without interim feedback to either of the two players. Each player moves according to a preselected plan. If (Xt,Yt) are the positions of the two players at time t, then the game's payoff is the sum over t from 1 to T of A(Xt,Yt,t). Additionally, all paths must be connected. That is, the finite set of positions available for a player in any time period depends on the position selected by that player in the previous time period. One player attempts to select a mixed strategy over the feasible T-time period paths to maximize the expected payoff. The other minimizes. Two solution procedures are given. One uses the Brown- Robinson method of fictitious play and the other linear programming. An example problem is solved using both procedures. Keywords: Search strategies; Prohibiting; Mathematical models. (kt)