Search

We study the classical problem introduced by R. Isaacs and S. Gal of minimizing the time to find a hidden point H on a network Q moving from a known starting point. Rather than adopting the traditional continuous unit speed path paradigm, we use the dynamic "expanding search" paradigm recently introduced by the authors. Here the regions S(t) that have been searched by time t are increasing from the starting point and have total length t. Roughly speaking the search follows a sequence of arcs ai such that each one starts at some point of an earlier one. This type of search is often carried out by real life search teams in the hunt for missing persons, escaped convicts, terrorists or lost airplanes. The paper which introduced this type of search solved the adversarial problem (where H is hidden to maximize the time to be found) for the cases where Q is a tree or is 2-arc-connected. This paper's main contribution is to give two strategy classes which can be used on any network and have expected search times which are within a factor close to 1 of the value of the game (minimax search time). These strategies classes are respectively optimal for trees and 2-arc-connected networks. We also solve the game for circle-and-spike networks, which can be considered as the simplest class of networks for which a solution was previously unknown. [ABSTRACT FROM AUTHOR]

We consider a 'manhunting' game in which one player, the Hider, chooses one of several cells to hide and a second player, the Seeker, distributes his resources among the several cells. The cells differ in their characteristics: it may be easier to hide in some cells, or there may be a lower probability of betrayal in others, etc. The Hider's survival probability depends on the characteristics of the cell chosen, as well as on the amount of resources which the Seeker expends in that cell. The Hider may need to carry out some activity while in his cell. If so, the activity creates a signal which can help the Seeker to locate the Hider. The Seeker must of course try to distinguish between the noise due to the activity and random "white" noise. We obtain a complete analytic solution for the case without signals. Simulation is used to develop good strategies for the case with signals. [ABSTRACT FROM AUTHOR]

In this paper, we study a multistage search game. The general situation is described as a predator-prey problem as follows: in a certain region there is a predator and a group of prey. The prey have h different places to go to eat, and every day the group goes to one of these places, but all the days, the herd is forced to go to a certain place, W, say to drink. Simultaneously, the predator has to select a strategy to meet the herd of prey and catch one of them, it can use its ambush strategy, which consists of going to place W, and wait there for the herd, or select a search strategy and go to one of the h different places where the herd goes to eat and search for a prey there. When predator and prey meet each other in one place, predator can catch a prey with a probability depending on the place and on the movement of the predators. Since animals require a minimum consumption of energy over time to survive, we suppose that the predator has to catch a minimum number of prey, K, over a number of days, M. We model this problem as a two-person zero-sum multistage game, which we solve in some situations by giving optimal strategies for prey and for predator and the value of the game. [ABSTRACT FROM AUTHOR]

Directed path-width was defined by Reed, Thomas and Seymour around 1995. The author and P. Hajnal defined a cops-and-robber game on digraphs in 2000. We prove that the two notions are closely related and for any digraph D, the corresponding graph parameters differ by at most one. The result is achieved using the mixed-search technique developed by Bienstock and Seymour. A search is called monotone, in which the robber's territory never increases. We show that there is a mixed-search of D with k cops if and only if there is a monotone mixed-search with k cops. For our cops-and-robber game we get a slightly weaker result: the monotonicity can be guaranteed by using at most one extra cop. [ABSTRACT FROM AUTHOR]

Search games with capacities are bipersonal zero-sum games where a player has to hide a number of objects or an amount of material in a fixed number of containers and his opponent attempts to locate them. In this article, we deal with games on a discrete structureless set and on a discrete set with linear order. In both cases, the capacities under consideration are continuous. Some of the games studied generalize previously studied games. [ABSTRACT FROM AUTHOR]

In a continuous accumulation game on a continuous region, a Hider distributes material over a continuous region at each instant of discrete time, and a Seeker examines the region. If the Seeker locates any of the material hidden, the Seeker confiscates it. The goal of the Hider is to accumulate a certain amount of material before a given time, and the goal of the Seeker is to prevent this. In previous works, we have studied accumulation games involving discrete objects and continuous material over discrete locations. The issues raised when the region is continuous are substantially different. In this paper, we study accumulation of continuous material over two types of continuous regions: the interval and the circle. [ABSTRACT FROM AUTHOR]

In this paper, we study a discrete search game on an array of N ordered cells, with two players having opposite goals: player I (searcher) and player II (hider). Player II has to hide q objects at consecutive cells and player I can search p consecutive cells. The payoff to player I is the number of objects found by him. In some situations, the players need to adopt sophisticated strategies if they are to act optimally. [ABSTRACT FROM AUTHOR]

In an accumulation game, a hider places objects at locations, and a seeker examines these locations. If the seeker discovers an object, the seeker confiscates it. The goal of the hider is to accumulate a certain number of objects before a given time, and the goal of the seeker is to prevent this. In this paper, we first classify various possible variations on the accumulation game. Next, we discuss the so-called noisy accumulation game in which the hider can observe each action of the seeker. We present the solution of this game for all but some marginal cases and illustrate it with computational examples. [ABSTRACT FROM AUTHOR]