Mathematics of Operations Research November 1990 [antikvár]

MATHLMATICS OF OPERATIONS RESEARCH Vol. 15, No. 4. November I'WO Primed in U.S.A. ON THE COOKIE-CUTTER GAME: SEARCH AND EVASION ON A DISC* JOHN M. DANSKIN In the cookie-cutter game, there is a trapping circle, of radius 1, in which an evader hides. A searcher has a "cookie-cutter", a disk of radius < 1. If, when he places the cookie-cutter on the trapping circle, the evader is within it, the evader is caught and the searcher wins. Otherwise the evader wins. If r = t/2/2, the problem is trivial. The evader should choose a point from the uniform distribution on the outer circumference of the trapping circle, and the searcher a point from the uniform distribution on the circle of radius /-*-(! - concentric to that circle; this choice gives him maximum coverage of the outer circumference. For the case r ^ 1/2, an easy and elegant solution was given by Gale and Glassey in 1974. Both players should go to the center with probability 1/7. The minimizer should go to the outer circumference, and the maximizer to /¦* = ]/3 /2, both with probability 6/7. For other r the problem is difficult. This paper proves that there are no solutions based on finitely many radii if r < l a = 0.476, where r,, solves a cubic equation, finds two-point solutions on [/'o, /'J, where r, = 0.515 solves a trigonometric equation, and proves qualitative facts for e (r,,v^/2). 1. Introduction. An evader must choose a point within a "trapping circle" of radius 1. A searcher centers a circular "cookie-cutter", of radius r < 1, at some point of the trapping circle. If it then turns out that the evader is within the searcher's cookie-cutter, he is caught; otherwise he escapes. Since the problem is rotationally symmetric, it reduces in a trivial way to a game over the unit square, the choices x and y for the maximizer (searcher) and minimizer (evader) being the radii from the center of the trapping circle. The payoff for this game is given by the function io (1.1) F(x,y) = { 1 x^ + y^ - r^ Ixy if \x - y\ > /•, if \x — y \ < r andx + y > r, if x+y The derivation of this formula is an easy exercise in trigonometry. The function Fix, y) is discontinuous, with "essential singularities" at the points (0, r) and (r, 0); it assumes in the neighborhoods of these points every value from 0 to 1. Also, it has infinite derivatives with respect to both variables all along the interiors of the lines x+y = r,y=x — r, and y = x + r. The game is thus far from any of those treated in Karlin's treatise [4], which summarized the considerable body of work done at The RAND Corporation in the early '50s on continuous games. Discontinuous games have in fact been very little •Received July 16, 1984; revised July 8, 1986. AMS 1980 subject classification. Primary; 90B40. Secondary: 90D05. lAOR 1973 subject classification. Main: Search. Cro.ss Reference: Games. OR/MS Index J978 subject classification. Primary; 751 Search and Surveillance. Secondary: 238 Games/Group Decisions/Non-Cooperative. Key words. Discontinuous games, cookie-cutter game, search and evasion. 573