Search

We consider a classic rendezvous game in which two players try to meet each other on a set of n locations. In each round, every player visits one of the locations, and the game finishes when the players meet at the same location. The goal is to devise strategies for both players that minimize the expected waiting time till the rendezvous. In the asymmetric case, when the strategies of the players may differ, it is known that the optimum expected waiting time of (n + 1) / 2 is achieved by the wait-for-mommy pair of strategies, in which one of the players stays at one location for n rounds, while the other player searches through all the n locations in a random order. However, if we insist that the players are symmetric—they are expected to follow the same strategy—then the best known strategy, proposed by Anderson and Weber [Anderson EJ, Weber RR (1990) The rendezvous problem on discrete locations. J. Appl. Probab. 27(4):839–851], achieves an asymptotic expected waiting time of 0.829 n. We show that the symmetry requirement indeed implies that the expected waiting time needs to be asymptotically larger than in the asymmetric case. Precisely, we prove that for every n ⩾ 2 , if the players need to employ the same strategy, then the expected waiting time is at least (n + 1) / 2 + ε n , where ε = 2 − 36 . We propose in addition a different proof for one our key lemmas, which relies on a result by Ahlswede and Katona [Ahlswede R, Katona GOH (1978) Graphs with maximal number of adjacent pairs of edges. Acta Mathematica Academiae Scientiarum Hungaricae 32(1–2):97–120]: the argument is slightly shorter and provides a constant larger than 2 − 36 , namely, 1 / 3600 . However, it requires that n be at least 16. Both approaches seem conceptually interesting to us. Funding: This work is a part of project TOTAL (Mi. Pilipczuk) that has received funding from the European Research Council under the European Union's Horizon 2020 research and innovation program [Grant 677651]. It is also partially funded by French ANR projects [Grant ANR-16-CE40-0023] (DESCARTES) and [Grant ANR-17-CE40-0015] (DISTANCIA). [ABSTRACT FROM AUTHOR]

Consider a two-person zero-sum search game between a hider and a searcher. The hider hides among n discrete locations, and the searcher successively visits individual locations until finding the hider. Known to both players, a search at location i takes ti time units and detects the hider—if hidden there—independently with probability α i for i = 1 , ... , n. The hider aims to maximize the expected time until detection, whereas the searcher aims to minimize it. We prove the existence of an optimal strategy for each player. In particular, any optimal mixed hiding strategy hides in each location with a nonzero probability, and there exists an optimal mixed search strategy that can be constructed with up to n simple search sequences. Funding: This work was supported by the Engineering and Physical Sciences Research Council [Grant EP/L015692/1] STOR-i Centre for Doctoral Training. [ABSTRACT FROM AUTHOR]

Suppose that some objects are hidden in a finite set S of hiding places that must be examined one by one. The cost of searching subsets of S is given by a submodular function, and the probability that all objects are contained in a subset is given by a supermodular function. We seek an ordering of S that finds all the objects with minimal expected cost. This problem is NP-hard, and we give an efficient combinatorial 2-approximation algorithm, generalizing analogous results in scheduling theory. We also give a new scheduling application where a set of jobs must be ordered subject to precedence constraints to minimize the weighted sum of some concave function of the completion times of subsets of jobs. We go on to give better approximations for submodular functions with low total curvature, and we give a full solution when the problem is what we call series-parallel decomposable. Next, we consider a zero-sum game between a cost-maximizing hider and a cost-minimizing searcher. We prove that the equilibrium mixed strategies for the hider are in the base polyhedron of the cost function, suitably scaled, and we solve the game in the series-parallel decomposable case, giving approximately optimal strategies in other cases. [ABSTRACT FROM AUTHOR]

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]

This paper addresses the high-level search planning that is necessary to find hidden objects in difficult undersea environments where sensor performance varies geographically and the susceptibility to false alarms is high. We develop a game-theoretic approach for maximizing the information that is collected as a multiagent collaborative search is conducted over a region of interest. To accomplish this, we apply 1) a search channel formalism to the discrete search modeling paradigm to develop information measures as a function of searcher regional visitation; and 2) a receiver operator characteristic analysis to map sensor detection characteristics to search events. We formulate an area search game where player action directs where and how information is collected under a fixed cost constraint on search effort. We discuss the properties of the information measure developed for a repeated look over the area search channel and examine the impact of setting ROC operating points to their game equilibrium values. We describe a new algorithmic capability for solving the search allocation problem where searchers can collaborate in their efforts to resolve false alarm outcomes. Results are presented to show the dominance of this approach over alternative strategies allotted to the game and to demonstrate the capability of exploiting the known nonhomogeneity in the search environment. [ABSTRACT FROM AUTHOR]

ABSTRACT In the rendezvous problem, two parties with different labelings of the vertices of a complete graph are trying to meet at some vertex at the same time. It is well-known that if the parties have predetermined roles, then the strategy where one of them waits at one vertex, while the other visits all n vertices in random order is optimal, taking at most n steps and averaging about [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]

Howard [Howard, J. V. 2006. Unsolved symmetric rendezvous search problems: Some old and some new. Presentation, Sixth International Workshop in Search Games and Rendezvous, July 26, London School of Economics, London] has described a simply but nontrivial symmetric rendezvous search game in which two players are initially placed in two distinct locations. The game is played in discrete steps, at each of which each player can either stay where she is or move to the other location. When the players are in the same location for the first time they do not see one another, but when they are in the same location for a second time, then they meet. We wish to find a strategy such that, if both players follow it independently, then the expected number of steps at which this second meeting occurs is minimized. Howard conjectured that the optimal strategy is 3-Markovian, such that in each successive block of three steps the players should, with equal probability, do SSS, SMS, MSM, MMM, where "M" means move and "S" means stay. We prove that this strategy is optimal. [ABSTRACT FROM AUTHOR]

In the symmetric rendezvous search game played on n locations two players are initially placed at two distinct locations. The game is played in discrete steps, at each of which each player can either stay where he is or move to a different location. The players share no common labelling of the locations. We wish to find a strategy such that, if both players follow it independently, then the expected number of steps until they are in the same location is minimized. Informal versions of the rendezvous problem have received considerable attention in the popular press. The problem was proposed by Alpern in 1976 [Alpern, S. 1976. Hide and seek games. Seminar at the Institut für Höhere Studien, Vienna], and it has proved notoriously difficult to analyse. In this paper we prove a 20-year-old conjecture that the following strategy is optimal for the game on three locations: in each block of two steps, stay where you are, or search the other two locations in random order, doing these with probabilities 1=3 and 2=3, respectively. This is now the first nontrivial symmetric rendezvous game of any type to be fully solved. [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]

We introduce a new zero-sum matrix game for modeling search in structured domains. In this game, one player tries to find a "bug" while the other tries to hide it. Both players exploit the structure of the "search" domain. Intuitively, this search game is a mathematical generalization of the well known binary search. The generalization is from searching over totally ordered sets to searching over more complex search domains such as trees, partial orders and general set systems. As there must be one row for every search strategy, and there are exponentially many ways to search even in very simple search domains, the game's matrix has exponential size ("space"). In this work we present two ways to reduce the space required to compute the Nash value (in pure strategies) of this game: • First we show that a Nash equilibrium in pure strategies can be computed by using a backward induction on the matrices of each "part" or sub structure of the search domain. This can significantly reduce the space required to represent the game. • Next, we show when general search domains can be represented as DAGs (Directed Acycliqe Graphs). As a result, the Nash equilibrium can be directly computed using the DAG. Consequently the space needed to compute the desired search strategy is reduced to O(n2) where n is the size of the search domain. [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]

This paper presents research combining an agent-based modeling and simulation paradigm with game theory for an in silico historical analysis of the Bay of Biscay submarine war during WWII. The U-boat threat was of great concern to the Allies, prompting initial operational research efforts to devise counterstrategies. Focusing search efforts in the Bay of Biscay enabled an effective Allied response. Using the historical record as a means to create a reasonably accurate model of the U-boat campaign, we allow the resulting agents within the model to adapt their strategies to counter-opposition strategies. Model output data are examined with respect to the historical record and game theory. The results hold promise for extending the agent-based modeling paradigm into more complex military-based domains. [ABSTRACT FROM PUBLISHER]

This paper presents research combining an agent-based modeling and simulation paradigm with game theory for an in silico historical analysis of the Bay of Biscay submarine war during WWII. The U-boat threat was of great concern to the Allies, prompting initial operational research efforts to devise counterstrategies. Focusing search efforts in the Bay of Biscay enabled an effective Allied response. Using the historical record as a means to create a reasonably accurate model of the U-boat campaign, we allow the resulting agents within the model to adapt their strategies to counter-opposition strategies. Model output data are examined with respect to the historical record and game theory. The results hold promise for extending the agent-based modeling paradigm into more complex military-based domains. [ABSTRACT FROM PUBLISHER]

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]

Thanks to the advent of new technologies and higher real-time computational capabilities, the use of unmanned vehicles in the marine domain has received a significant boost in the last decade. Ocean and seabed sampling, missions in dangerous areas, and civilian security are only a few of the large number of applications which currently benefit from unmanned vehicles. One of the most actively studied topic is their full autonomy; i.e., the design of marine vehicles capable of pursuing a task while reacting to the changes of the environment without the intervention of humans, not even remotely. Environmental dynamicity may consist of variations of currents, the presence of unknown obstacles, and attacks from adversaries (e.g., pirates). To achieve autonomy in such highly dynamic uncertain conditions, many types of autonomous path planning problems need to be solved. There has thus been a commensurate number of approaches and methods to optimize this kind of path planning. This work focuses on game-theoretic approaches and provides a wide overview of the current state of the art, along with future directions. [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]