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.     

A game with three players

In the classical gambling problem (two players with initial capital a₁ and a₂, respectively) the expected time to ruin is a₁a₂. Here we extend this problem to three players and prove that the expected time to ruin equals (a₁a₂a₃)/(a₁ + a₂ + a₃ − 2).     

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 the centipede game with a social norm

In this paper, we present a formulation of the centipede game where inter-subjectivity between players is formalized through random costs that are an increasing function, in the sense of first-order stochastic dominance, of the number of iterations for which the game is played. This injection of a time-dependent social norm, one that also parametrizes player proximity, as an element of each player’s introspective calculations formalizes a setting under which subgame perfection dictates cooperative outcomes.     

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