A cops and robber game in multidimensional grids

We theoretically analyze the ‘cops and robber’ game for the first time in a multidimensional grid. It is shown that in an n-dimensional grid, at least n cops are necessary if one wants to catch the robber for all possible initial configurations. We also present a set of cop strategies for which n cops are provably sufficient to catch the robber. Further, we revisit the game in a two-dimensional grid and provide an independent proof of the fact that the robber can be caught even by a single cop under certain conditions.     

Locating a robber on a graph

Consider the following game of a cop locating a robber on a connected graph. At each turn, the cop chooses a vertex of the graph to probe and receives the distance from the probe to the robber. If she can uniquely locate the robber after this probe, then she wins. Otherwise the robber may either stay put or move to any vertex adjacent to his location other than the probe vertex. The cop’s goal is to minimize the number of probes required to locate the robber, while the robber’s goal is to avoid being located. This is a synthesis of the cop and robber game with the metric dimension problem. We analyse this game for several classes of graphs, including cycles and trees.     

On a combinatorial game

A drawing strategy is explained which applies to a wide class of combinatorial and positional games. In some settings the strategy is best possible. When applied to n-dimensional Tic-Tac-Toe, it improves a result of Hales and Jewett [5].     

Locating a robber with multiple probes

We consider a game in which a cop searches for a moving robber on a connected graph using distance probes, which is a slight variation on one introduced by Seager (2012). Carragher, Choi, Delcourt, Erickson and West showed that for any $n$-vertex graph $G$ there is a winning strategy for the cop on the graph $G^{1∕m}$ obtained by replacing each edge of $G$ by a path of length $m$, if $m\ge n$ (Carragher et al., 2012). The present authors showed that, for all but a few small values of $n$, this bound may be improved to $m\ge n∕2$, which is best possible (Haslegrave et al., 2016). In this paper we consider the natural extension in which the cop probes a set of $k$ vertices, rather than a single vertex, at each turn. We consider the relationship between the value of $k$ required to ensure victory on the original graph with the length of subdivisions required to ensure victory with $k=1$. We give an asymptotically best-possible linear bound in one direction, but show that in the other direction no subexponential bound holds. We also give a bound on the value of $k$ for which the cop has a winning strategy on any (possibly infinite) connected graph of maximum degree $\Delta$, which is best possible up to a factor of $(1?o\left(1\right))$.     

On a dynamic fractional game

Consider a two-person zero-sum game constructed by a dynamic fractional form. We establish the upper value as well as the lower value of a dynamic fractional game, and prove that the dual gap is equal to zero under certain conditions. It is also established that the saddle point function exists in the fractional game system under certain conditions so that the equilibrium point exists in this game system.     

On a game in manufacturing

We analyse a non-zero sum two-person game introduced by Teraoka and Yamada to model the strategic aspects of production development in manufacturing. In particular we investigate how sensitive their solution concept (Nash equilibrium) is to small variations in their assumptions. It is proved that a Nash equilibrium is unique if it exists and that a Nash equilibrium exists when the capital costs of the players are zero or when the players are equal in every respect. However, when the capital costs differ, in general a Nash equilibrium exists only when the players' capital costs are high compared to their profit rates.     

On a differential encounter game

A game of the encounter of two objects subject to viscous friction and control forces is examined. The sufficient conditions for the equality of the game's value to the programmed maximin are obtained under constraints of a general form.     

On a square haystack game

A haystack game is a hider-seeker zero-sum game of locating a needle in a haystack. Baston and Bostock have obtained partial solutions to this game for the case of a square haystack. This paper supplements their results, thus confirming their belief that a complete solution is difficult.The author would like to thank a referee for his helpful comments, in particular for suggesting Lemma 2.1 which has led to a more concise and transparent treatment of Section 2.     

Edge critical cops and robber

We consider edge critical graphs when playing cops and robber. Specifically, we look at those graphs whose copnumbers change from one to two when any edge is added, deleted, subdivided or contracted. We characterize all such sets, showing that they are empty, trees, all 2-edge-connected graphs and empty, respectively. We also consider those graphs which change from copnumber two to one when any edge is added, and give a characterization in the k-regular case.     

On synthesis in a differential game

The control problem is considered with minimization of the guaranteed result for a system described by an ordinary differential equation in the presence of uncontrolled noise. The concepts and formulation of the problem in /1/ are used. It is shown that, when forming the optimal control by the method of programmed stochastic synthesis /1–3/, the extremal shift at the accompanying point /1, 4/ can be reduced to extremal shift agianst the gradient of the appropriate function. This explains the connection between the programmed stochastic synthesis and the generalized Hamilton-Jacobi equation /5, 6/ in the theory of differential games.     

On a discrete evasion game of Isaacs

The discrete evasion game with a three-move lag, formulated over thirty years ago, was one of the earliest games with time-lag complications. This game remains unsolved, even though it is well-known that the game has a value. By considering the bomber-battleship duel and by constructing an explicit strategy for the bomber, we bound the value from below as 0.28648. This is believed to be the best lower bound known.     

On a repeated game without a recursive structure

The solution is given here for the infinitely repeated two-person zero-sum games of incomplete information characterized by 2×2 games, with information matrices $\left( {{*{20}c} a & b \\ b & b \\ } \right)$\left( {\begin{array}{*{20}c} a & b \\ b & b \\ \end{array} } \right) for the first game and $\left( {{*{20}c} b & b \\ b & a \\ } \right)$\left( {\begin{array}{*{20}c} b & b \\ b & a \\ \end{array} } \right) for the second game.     

On a nonsingular singular surface of a differential game

A differential game in which nonterminating play is assigned a fixed value is examined. The solution exhibits a new kind of singular surface which an optimal path takes an infinite time to cross. By playing nonoptimally in a sufficiently small neighborhood of this surface, the player who prefers the optimal (terminating) value to the value of nonterminating play can force the state across this surface and obtain a value arbitrarily close to the optimal.This work was carried out with the support of a CSIRO postgraduate studenship.     

On the core: complement-reduced game and max-reduced game

This paper presents two characterizations of the core on the domain of all NTU games. One is based on consistency with respect to “complement-reduced game” and converse consistency with respect to “max-reduced game”. The other is based on consistency with respect to “max-reduced game” and weak converse consistency with respect to “complement-reduced game”. Besides, we introduce an alternative definition of individual rationality, we name conditional individual rationality, which is compatible with non-emptiness. We discuss axiomatic characterizations involving conditional individual rationality for the core.     

On the decisiveness of a game in a tournament

In sport tournaments in which teams are matched two at a time, it is useful for a variety of reasons to be able to quantify how important a particular game is. The need for such quantitative information has been addressed in the literature by several more or less simple measures of game importance. In this paper, we point out some of the drawbacks of those measures and we propose a different approach, which rather targets how decisive a game is with respect to the final victory. We give a definition of this idea of game decisiveness in terms of the uncertainty about the eventual winner prevailing in the tournament at the time of the game. As this uncertainty is strongly related to the notion of entropy of a probability distribution, our decisiveness measure is based on entropy-related concepts. We study the suggested decisiveness measure on two real tournaments, the 1988 NBA Championship Series and the UEFA 2012 European Football Championship (Euro 2012), and we show how well it agrees with what intuition suggests. Finally, we also use our decisiveness measure to objectively analyse the recent UEFA decision to expand the European Football Championship from 16 to 24 nations in the future, in terms of the overall attractiveness of the competition.     

On the contribution of a player to a game

In ann-person game, corresponding toMilnor's upper bound,b (i), a quantitym (i) is defined, which is a lower bound ofX _i whenx belongs to the kernel. In the case of the bargaining set, it is shown for particular games thatb (i),m (i) are bounds ofx _i .     

On a deception game with three boxes

This paper clarifies the status of a deception game posed by Spencer. We show the value of this game is zero.     

On a stochastic game with one-chance recovery

Summary Bernoulli trials with success ratep are considered. Peter, who is a gambler of success ratep, gets 1 unit if the first trial results in success and loses the same unit otherwise. For thekth trial (k≧2), he gets or loses 1 according as success or failure unless his previous gainS _k−1 is negative. WhenS _k−1 is minus, Peter gets or loses −S _k−1 . Then Peter's gainS _n inn trials is the sum of “dependent” random variables. Therefore, Peter has always the chancep of recovering his minus gain instantaneously. The probability function ofS _n is given and the expected gain is compared with the ordinary (non-symmetric) random walk situation. It will be concluded that Peter should not play the game with one-chance recovery because whenp is less than 1/2, he must be afraid of suffering a bigger risk than the usual case. The Institute of Statistical Mathematics