The vertex picking game and a variation of the game of dots and boxes

A two-player game played on a graph is introduced and completely solved. As a consequence, a solution to a simplified variation of a well-known game called dots and boxes played on a grid [2] is given.     

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     

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].     

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 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.     

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 linear pursuit game with an unknown trap

A linear pursuit game with a trap, the location of which is unknown to the evader, is defined and investigated. The cases in which one of the players has complete energy dominance over his adversary are solved completely. In the general case, when no player dominates, the solution is indicated for the two-stage game.This research was supported in part by the Technion Fund for promotion of research.     

On a repeated game with state dependent signalling matrices

We prove the existence of the minmax and the maxmin for a repeated game with lack of information on both sides and signalling matrices which depend on the state.     

On a variational inequality associated with a stopping game combined with a control

We study a non-linear elliptic variational inequality which corresponds to a zero-sum stopping game (Dynkin game) combined with a control. Our result is a generalization of the existing works by Bensoussan [ Stochastic Control by Functional Analysis Methods (North-Holland, Amsterdam), 1982], Bensoussan and Lions [ Applications des Inéquations Variationnelles en Contrôle Stochastique (Dunod, Paris), 1978] and Friedman [ Stochastic Differential Equations and Applications (Academic Press, New York), 1976] in the sense that a non-linear term appears in the variational inequality, or equivalently, that the underlying process for the corresponding stopping game is subject to a control. By using the dynamic programming principle and the method of penalization, we show the existence and uniqueness of a viscosity solution of the variational inequality and describe it as the value function of the corresponding combined-stochastic game problem.     

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 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 game of policemen and robber

We consider a game where policemen try to catch a robber on a graph G (as defined by A. Quilliot) and we find the exact minimal number of policemen needed when G is a Cartesian product of trees.     

On the number of minimal partitions of a box into boxes

The number of minimal partitions of a box into proper boxes is examined.     

On a pursuit game on cayley graphs

The game cops and robbers is considered on Cayley graphs of abelian groups. It is proved that if the graph has degreed, then [(d+1)/2] cops are sufficient to catch one robber. This bound is often best possible.     

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 generalized Cournot oligopolistic competition game

We consider a model whereby players compete for a set of shared resources to produce and sell substitute products in the same market, which can be viewed as a generalization of the classical Cournot oligopolistic competition model, or, from a different angle, the Wardrop type routing model. In particular, we suppose that there are K players, who compete for the usage of resources as well as the sales of the end-products. Moreover, the unit costs of the shared resources and the selling prices of the products are assumed to be affine linear functions in the consumption/production quantities. We show that the price of anarchy in this case is lower bounded by 1/K, and this bound is essentially tight, which manifests the harsh nature of the competitive market for the producers.     

On an N-person noncooperative Markov game with a metric state space

We consider a noncooperative N-person discounted Markov game with a metric state space, and define the total expected discounted gain. Under some conditions imposed on the objects in the game system, we prove that our game system has an equilibrium point and each player has his equilibrium strategy. Moreover in the case of a nondiscounted game, the total expected gain up to a finite time can be obtained, and we define the long-run expected average gain. Thus if we impose a further assumption for the objects besides the conditions in the case of the discounted game, then it is proved that the equilibrium point exists in the nondiscounted Markov game. The technique for proving the nondiscounted case is essentially to modify the objects of the game so that they become objects of a modified Markov game with a discounted factor which has an equilibrium point in addition to the equilibrium point of the discounted game.     

Construction of the value function in a pursuit-evasion game with three pursuers and one evader

A differential pursuit-evasion game is considered with three pursuers and one evader. It is assumed that all objects (players) have simple motions and that the game takes place in a plane. The control vectors satisfy geometrical constraints and the evader has a superiority in control resources. The game time is fixed. The value functional is the distance between the evader and the nearest pursuer at the end of the game. The problem of determining the value function of the game for any possible position is solved.

Three possible cases for the relative arrangement of the players at an arbitrary time are studied: “one-after-one”, “two-after-one”, “three-after-one-in-the-middle” and “three-after-one”. For each of the relative arrangements of the players a guaranteed result function is constructed. In the first three cases the function is expressed analytically. In the fourth case a piecewise-programmed construction is presented with one switchover, on the basis of which the value of the function is determined numerically. The guaranteed result function is shown to be identical with the game value function. When the initial pursuer positions are fixed in an arbitrary manner there are four game domains depending on their relative positions. The boundary between the “three-after-one-in-the-middle” domain and the “three-after-one” domain is found numerically, and the remaining boundaries are interior Nicomedean conchoids, lines and circles. Programs are written that construct singular manifolds and the value function level lines.