Search

The article of record as published may be found at https://doi.org/10.1016/j.tcs.2020.03.011 A set of n boxes, located on the vertices of a hypergraph G, contain known but different rewards. A Searcher opens all the boxes in some hyperedge of G with the objective of collecting the maximum possible total reward. Some of the boxes, however, are booby trapped. If the Searcher opens a booby trapped box, the search ends and she loses all her collected rewards. We assume the number k of booby traps is known, and we model the problem as a zero-sum game between the maximizing Searcher and a minimizing Hider, where the Hider chooses k boxes to booby trap and the Searcher opens all the boxes in some hyperedge. The payoff is the total reward collected by the Searcher. This model could reflect a military operation in which a drone gathers intelligence from guarded locations, and a booby trapped box being opened corresponds to the drone being destroyed or incapacitated. It could also model a machine scheduling problem, in which rewards are obtained from successfully processing jobs but the machine may crash. We solve the game when G is a 1-uniform hypergraph (the hyperedges are all singletons), so the Searcher can open just 1 box. When G is the complete hypergraph (containing all possible hyperedges), we solve the game in a few cases: (1) same reward in each box, (2) k=1, and (3) n=4 and k = 2. The solutions to these few cases indicate that a general simple, closed form solution to the game appears unlikely. This material is based upon work supported by the National Science Foundation under Grant No. IIS-1909446. This material is based upon work supported by the National Science Foundation under Grant No. IIS-1909446.

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.

This Habilitation thesis explores aspects of computation in a status of uncertainty. First, we study online problems, in which the input is not known in advance, and the algorithm must make decisions for each input item without knowledge of future input items. Second, we consider search games, in which a mobile searcher must locate an immobile hider that lies in some unknown point of the search domain. Last, we study the design and analysis of interruptible systems, in which the system must be able to produce a reasonably efficient output even if interrupted at some arbitrary point in time. A unifying theme in the study of the above topics is the power and limitations of well-known, worst-case measures such as the competitive ratio and the acceleration ratio. We argue that in certain cases, more nuanced performance measures are required, and to this end we introduce new models and techniques of analysis. We also demonstrate and exploit connections between these measures and approaches, even though they apply to seemingly unrelated domains.

We study the classic problem in which a Searcher must locate a hidden point, also called the Hider in a network, starting from a root point. The network may be either bounded or unbounded, thus generalizing well-known settings such as linear and star search. We distinguish between pathwise search, in which the Searcher follows a continuous unit-speed path until the Hider is reached, and expanding search, in which, at any point in time, the Searcher may restart from any previously reached point. The former has been the usual paradigm for studying search games, whereas the latter is a more recent paradigm that can model real-life settings such as hunting for a fugitive, demining a field, or search-and-rescue operations. We seek both deterministic and randomized search strategies that minimize the competitive ratio, namely the worst-case ratio of the Hider’s discovery time, divided by the length of the shortest path to it from the root. Concerning expanding search, we show that a simple search strategy that applies a “waterfilling” principle has optimal deterministic competitive ratio; in contrast, we show that the optimal randomized competitive ratio is attained by fairly complex strategies even in a very simple network of three arcs. Motivated by this observation, we present and analyze an expanding search strategy that is a 5 4 -approximation of the randomized competitive ratio. Our approach is also applicable to pathwise search, for which we give a strategy that is a 5-approximation of the randomized competitive ratio, and which improves upon strategies derived from previous work.

We consider a classic rendezvous game where 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, where 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, achieves an asymptotic expected waiting time of 0.829n. 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}.

The article of record as published may be found at http://dx.doi.org/10.1016/j.cor.2006.09.020 We develop and analyze a “manhunting” game involving a mobile hider, who wishes to maximize his time to capture, and a mobile searcher, who wishes to minimize this same time. The game takes place within a variegated environment that offers better and worse locations to evade capture. The hider is able to move from one hide site to another at will. In choosing a hide site, he must consider the risk of discovery, the risk that he will be betrayed, and the risk that he will be captured while moving from one site to another. The searcher can select any cell to search within the fugitive’s feasible hiding set. We examine the strategic behavior of both players and provide examples. Published by Elsevier Ltd.

We consider the problem of searching for an object on a line at an unknown distance OPT from the original position of the searcher, in the presence of a cost of d for each time the searcher changes direction. This is a generalization of the well-studied linear-search problem. We describe a strategy that is guaranteed to find the object at a cost of at most 9*OPT + 2d, which has the optimal competitive ratio 9 with respect to OPT plus the minimum corresponding additive term. Our argument for upper and lower bound uses an infinite linear program, which we solve by experimental solution of an infinite series of approximating finite linear programs, estimating the limits, and solving the resulting recurrences. We feel that this technique is interesting in its own right and should help solve other searching problems. In particular, we consider the star search or cow-path problem with turn cost, where the hidden object is placed on one of m rays emanating from the original position of the searcher. For this problem we give a tight bound of (1+(2(m^m)/((m-1)^(m-1))) OPT + m ((m/(m-1))^(m-1) - 1) d. We also discuss tradeoff between the corresponding coefficients, and briefly consider randomized strategies on the line., 15 pages, 2 figures, 1 table; to appear in Theoretical Computer Science. Did some minor editorial changes, fixed some typos, etc

The main motivation behind this thesis is a certain type of win-lose games that are played on hypergraphs and can be translated into the following puzzle. Suppose there are two persons, say Alice and Bob. There are n biscuits, where n is a positive integer, and Alice chooses s of them uniformly at random. Bob possesses h grams of poison, where h is greater than or equal to 1, and the lethal dose is 1 gram. How should Bob distribute the poison over the biscuits in order to maximize the probability of poisoning Alice? This problem is due to Ken Kikuta and William Ruckle who, driven by less devious motives, formulated it in terms of accumulation games between two players. They conjectured that the optimal distribution of poison uses dosages of 1/j grams in as many biscuits as possible, where j is a positive integer that depends on h,n,s. In Chapter 1 we introduce the poisoning problem and discuss its relation to known results from the literature. The conjecture of Kikuta and Ruckle is related to two other conjectures, one from extremal combinatorics and one from the theory of probability. The combinatorial flavor of the Kikuta-Ruckle conjecture is its relation to the matching conjecture of Paul Erdos and its fractional analogue. Its probabilistic flavor is its relation to a conjecture of Stephen Samuels on a tail probability problem. We also consider a poisoning problem on more general ground spaces. This leads to a geometric problem that generalizes the isodiametric one. In Chapter 2 we settle the Kikuta-Ruckle conjecture in case n=2s-1. This case corresponds to the, so called, Odd graph. We also settle the conjecture for a few more cases using elementary combinatorial and game-theoretic arguments. In Chapter 3 we consider the poisoning game on the cyclic graph. In this game the n biscuits are arranged cyclically and Alice chooses s consecutive of them uniformly at random. We find the value of this game along with the optimal strategies of both players. In addition, we give a characterization of the fractional covering number of uniform hypergraphs obtained from the cyclic graph. Chapter 4 deals with the analysis of a network coloring game. This is a game that is motivated by conflict resolution situations and is played on a graph. The vertices of the graph are thought of as players having a fixed set of available colors. The game is played in rounds and in each round all players simultaneously and individually choose a color with the perspective of ending up with a color that is different from the colors chosen by their neighbors. We analyze the network game by introducing a very simple search game. The optimal strategy of the searchers in this game involves tosses of fair colored coins and leads to the following combinatorial probability problem that is interesting on its own. Suppose that you can color n fair coins with n colors. It is not allowed to colors both sides of a coin with the same color, but all other combinations are allowed. Let X be the number of different colors after a toss of the coins. In what way should you color the coins such that you maximize the median of X? We solve this problem and consider its natural generalization to the case of biased coins. The later case builds on the study of Bernoulli random variables whose total number of successes is of fixed parity.

The main motivation behind this thesis is a certain type of win-lose games that are played on hypergraphs and can be translated into the following puzzle. Suppose there are two persons, say Alice and Bob. There are n biscuits, where n is a positive integer, and Alice chooses s of them uniformly at random. Bob possesses h grams of poison, where h is greater than or equal to 1, and the lethal dose is 1 gram. How should Bob distribute the poison over the biscuits in order to maximize the probability of poisoning Alice? This problem is due to Ken Kikuta and William Ruckle who, driven by less devious motives, formulated it in terms of accumulation games between two players. They conjectured that the optimal distribution of poison uses dosages of 1/j grams in as many biscuits as possible, where j is a positive integer that depends on h,n,s. In Chapter 1 we introduce the poisoning problem and discuss its relation to known results from the literature. The conjecture of Kikuta and Ruckle is related to two other conjectures, one from extremal combinatorics and one from the theory of probability. The combinatorial flavor of the Kikuta-Ruckle conjecture is its relation to the matching conjecture of Paul Erdos and its fractional analogue. Its probabilistic flavor is its relation to a conjecture of Stephen Samuels on a tail probability problem. We also consider a poisoning problem on more general ground spaces. This leads to a geometric problem that generalizes the isodiametric one. In Chapter 2 we settle the Kikuta-Ruckle conjecture in case n=2s-1. This case corresponds to the, so called, Odd graph. We also settle the conjecture for a few more cases using elementary combinatorial and game-theoretic arguments. In Chapter 3 we consider the poisoning game on the cyclic graph. In this game the n biscuits are arranged cyclically and Alice chooses s consecutive of them uniformly at random. We find the value of this game along with the optimal strategies of both players. In addition, we give a characterization of the fractional covering number of uniform hypergraphs obtained from the cyclic graph. Chapter 4 deals with the analysis of a network coloring game. This is a game that is motivated by conflict resolution situations and is played on a graph. The vertices of the graph are thought of as players having a fixed set of available colors. The game is played in rounds and in each round all players simultaneously and individually choose a color with the perspective of ending up with a color that is different from the colors chosen by their neighbors. We analyze the network game by introducing a very simple search game. The optimal strategy of the searchers in this game involves tosses of fair colored coins and leads to the following combinatorial probability problem that is interesting on its own. Suppose that you can color n fair coins with n colors. It is not allowed to colors both sides of a coin with the same color, but all other combinations are allowed. Let X be the number of different colors after a toss of the coins. In what way should you color the coins such that you maximize the median of X? We solve this problem and consider its natural generalization to the case of biased coins. The later case builds on the study of Bernoulli random variables whose total number of successes is of fixed parity.

We consider the problem of searching for an unknown horizontal or vertical line in a plane. A search path in the plane starts at the origin and detects the unknown line, if the path hits the line for the first time. The performance of the search path is measured by competitive analysis. That is, we compute the ratio of the length of the path until the line is detected over the shortest path from the origin to the given line. The competitive ratio of a given search path is the worst-case ratio of the path among all horizontal and vertical lines in the plane. In this paper, we design a search path that attains a competitive ratio of 12.53853842…, and slightly improves the current best-known search path. Furthermore, we prove that the search path is optimal among all paths that proceed in a cyclic manner. There is a strong conjecture that this path is the general optimal search path for searching axis-parallel lines.

We define a general game which forms a basis for modelling situations of static search and concealment over regions with spatial structure. The game involves two players, the searching player and the concealing player, and is played over a metric space. Each player simultaneously chooses to deploy at a point in the space; the searching player receiving a payoff of 1 if his opponent lies within a predetermined radius r of his position, the concealing player receiving a payoff of 1 otherwise. The concepts of dominance and equivalence of strategies are examined in the context of this game, before focusing on the more specific case of the game played over a graph. Methods are presented to simplify the analysis of such games, both by means of the iterated elimination of dominated strategies and through consideration of automorphisms of the graph. Lower and upper bounds on the value of the game are presented and optimal mixed strategies are calculated for games played over a particular family of graphs.

Submodular functions have appeared to be a key tool for proving the monotonicity of several graph searching games. In this paper we provide a general game theoretic framework able to unify old and new monotonicity results in a unique min-max theorem. Our theorem, provides a game theoretic analogue to a wide number of graph theoretic parameters such as linear-width and cutwidth.

In general, graph search can be described in terms of a sequence of searchers' moves on a graph, able to capture a fugitive resorting on its vertices/edges. Several variations of graph search have been introduced, differing on the abilities of the fugitive as well as of the search. In this paper, we examine the case where the fugitive is inert, i.e., it moves only whenever the search is about to capture it. Mainly, there are two variants for