Stochastic pursuit-evasion differential games in 3D

A stochastic version of Isaacs's homicidal chauffeur game in the (x, y, z)-space is considered. This is used to solve a pursuit-evasion problem in the (x, y, z)-space in which the pursuer has incomplete information on the evader motion. Optimal feedback strategies for the game, and optimal feedback guidance laws for the pursuer, which uses only the measurements available to the pursuer, are computed. A simple suboptimal guidance law for the pursuer is suggested.     

A stochastic homicidal chauffeur pursuit-evasion differential game

A certain stochastic pursuit-evasion problem of the homicidal chauffeur type is considered. The pursuer strategy synthesized in this paper is fairly simple in contrast to the less straightforward swerve maneuver employed in the deterministic model. The analysis may partially explain why relatively simple pursuit strategies are apparently always adopted in practice.This work was partially supported by a grant from Control Data.The authors wish to thank Dr. D. H. Martin for a very enlightening discussion.     

Guaranteed avoidance strategies

We consider a dynamical system under the control of two agents, one of whom desires to keep the system's state out of a given set regardless of the other agent's actions. The guaranteed avoidance conditions of Ref. 1 are generalized to admit piecewiseC ¹ test functions; this generalization permits application to a wider class of problems. The results are illustrated by application to a version of the homicidal chauffeur game.Dedicated to R. BellmanThis paper is based on research supported by NSF under Grant No. ENG-78-13931.     

An efficient algorithm for perturbed shortest path problems

We present an efficient algorithm for perturbed shortest paths problems that arise, e.g., in dynamic games. Via a minmax version of Dijkstra's algorithm we compute piecewise constant upper and lower bounds on the upper value function of the game. Convergence of the bounds in the limit of vanishing cell diameter can be proved. The method is numerically demonstrated on a simple 2d dynamic game, the homicidal chauffeur. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Homicidal Chauffeur Game with Target Set in the Shape of a Circular Angular Sector: Conditions for Existence of a Closed Barrier

A planar constant-speed pursuit-evasion problem with dynamic model similar to the one of the homicidal chauffeur game and with prescribed angular constraints in the capture criterion is analyzed as a differential game of kind. Because of the angular constraints, the target set of the game has the shape of a circular angular sector. Conditions for the existence of the game barrier (closed) are obtained. Using these conditions, a necessary and sufficient condition for capture of a slower evader from any initial state of the game is established. This condition is represented by an expression for the minimal nondimensional capture radius, normalized by the pursuer minimal turning radius, which guarantees capture of all slower evaders. This minimal capture radius depends on the angular constraints. Capture from any initial state implies that the barrier of the game does not exist and vice versa. In this game, two types of barrier are derived, with termination at either points of smoothness or points of nonsmoothness (corner points) of the boundary of the target set. The results are illustrated by numerical examples.     

Winning strategies in club games and their applications

We present results concerning winning strategies and tactics in club games on ??λ. We show that there is generally no winning tactic for the player trying to get inside the club. The bound‐countable game turns out to be rather fruitful and adds to some previous results about the construction of elementary substructures and their localization in certain intervals. We show that Player II has a winning strategy in the bound‐countable game, thus establishing a new ZFC result. The applications given are new proofs for two cardinal diamonds and the impossibility of collapsing cardinals to ?₂ under certain conditions (© 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Stochastic two-target pursuit-evasion differential games in the plane

A stochastic version of a two-target homicidal chauffeur, pursuit-evasion differential game (using polar coordinates) is considered. This is used to model a dogfight between a very agile playerQ and a less maneuverable playerP. First, the case where both players have complete observation of the state of the game is considered. A numerical study is conducted, by solving numerically a nonlinear partial differential equation on a torus in ², to investigate the role of the parameters of speed, maneuverability, and performance of the weapon systems, in the encounter. Second, the model is extended to include the case where playerP is jamming playerQ's measurements of , where denotes the bearing ofQ fromP. A numerical study is conducted, by solving numerically a nonlinear partial differential equation on a generalized torus in ³, to investigate the role of the jamming parameter on the outcome of the combat.     

Learning of winning strategies for terminal games with linear-size memory

We prove that if one or more players in a locally finite positional game have winning strategies, then they can find it by themselves, not losing more than a bounded number of plays and not using more than a linear-size memory, independently of the strategies applied by the other players. We design two algorithms for learning how to win. One of them can also be modified to determine a strategy that achieves a draw, provided that no winning strategy exists for the player in question but with properly chosen moves a draw can be ensured from the starting position. If a drawing- or winning strategy exists, then it is learnt after no more than a linear number of plays lost (linear in the number of edges of the game graph). Z. Tuza’s research has been supported in part by the grant OTKA T-049613.     

Analysis of a game of graph solitaire

Let G be a simple undirected graph. To each vertex assign one of two colours say red or blue. A solitaire game is played on G as follows. A move consists of selecting a blue vertex, inverting the colours of its neighbours and then deleting the chosen vertex and all edges incident upon it. The goal is to delete all the vertices. The question of finding a winning strategy in the case when G is a simple cycle was proposed in the problems section of the American Mathematical Monthly. In this article some general results on winning colour configurations are derived and the game is analysed for certain other graph classes.     

Potential theory for mean payoff games

The paper presents an O(mn2ⁿ log Z) deterministic algorithm for solving the mean payoff game problem, m and n being the numbers of arcs and vertices, respectively, in the game graph, and Z being the maximum weight (the weights are assumed to be integers). The theoretical basis for the algorithm is the potential theory for mean payoff games. This theory allows one to restate the problem in terms of solving systems of algebraic equations with minima and maxima. Also, in order to solve the mean payoff game problem, the arc reweighting technique is used. To this end, simple modifications, which do not change the set of winning strategies, are applied to the game graph; in the end, a trivial instance of the problem is obtained. It is shown that any game graph can be simplified by n reweightings. Bibliography: 16 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 340, 2006, pp. 61–75.     

Coalitions and payoffs in three‐person sequential games: Initial tests of two formal models

In this paper we develop two formal models predicting coalitions and payoffs among rank striving players in a sequential three‐person game. We test the models’ predictions with data from a laboratory study of eleven male triads. Each triad plays a sequence of games; in each game a two‐person coalition forms and divides the coalition's point value between the two coalition partners. Participants know that the sequence of games will end without warning at a randomly chosen time; at the sequence's end each player's monetary payoff is a linear function of the rank of his accumulated point score, relative to those of the other members of his triad. The complexity of this situation prevents players and analysts from representing it as a single game; thus they are unable to use n‐person game theory to identify optimal strategies. Consequently, we assume that players, unable to develop strategies that are demonstrably optimal in the long run, adopt certain bargaining heuristics and surrogate short run objectives.

The two models follow the same basic outline; they differ, however, in the planning horizon they assume players to use. Proceeding from a priori assumptions concerning each player's decision calculus and the bargaining process, the two models state the probability that each coalition forms and predict the point divisions in the winning coalition. The laboratory data provide consistently strong support for the predictions of both models.     

Some undecidable determined games

Computing machines using algorithms play games and even learn to play games. However, the inherent finiteness properties of algorithms impose limitations on the game playing abilities of machines. M. Rabin illustrated this limitation in 1957 by constructing a two-person win-lose game with decidable rules but no computable winning strategies. Rabin's game was of the type where two players take turns choosing integers to satisfy some decidable but very complicated winning condition. In the present paper we obtain similar theorems of this type but the winning conditions are extremely simple relations (polynomial equations). Specific examples are given.     

三步矩阵对策上的无中生有计及其实例

基于一个历史实例及假定:①三步矩阵对策中赢得矩阵都不变,②每步都是局中人1先行动,③对于每步对策,局中人2观测不到对手究竟使用了何策略;但局中人1可以观测到对手所用的策略,建立了三步矩阵对策上的无中生有计(《三十六计》中的第七计)的对策模型.研究了当局中人2中计,半识破和完全识破对手的无中生有计时的赢得和所用的策略的情况.并用上述实例对模型作了说明.     

Computational complexity of winning strategies in two-person polynomial games

One considers two-person games, with players called I and II below. In order, they choose natural numbers, for example, for length 4, I chooses x₁, II chooses x₂. I chooses x₃, II chooses x₄. Then I wins if P(x₁,x₂,x₃,x₄)=0.Here P is a polynomial with integer coefficients. An old theorem of von Neumann and Zermelo shows that such a game is determined, i.e., there exists a winning strategy for one player or the other but not necessarily a computable winning strategy or one computable in polynomial time. It will be shown that there exists a game of polynomial type of length 4 for which there do not exist winning strategies for either player which are computable in polynomial time.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 192, pp. 69–73, 1991.     

The winning strategy for Hironaka’s polyhedra game is almost arbitrary

This paper proves that the winning strategy for Hauser’s version of Hironaka’s polyhedra game is almost arbitrary. The winning strategy and its associated invariants are based on an algorithm of matrix triangulations and matrix diagonalizations. It is proved that if a set sequence constitutes a winning strategy for the game, then so does every set sequence containing it. The same holds for Hironaka’s version of the game if every move is permissible.     

Topological spaces related to the Banach-Mazur game and the generic well-posedness of optimization problems

The existence of special kind of winning strategies in the Banach-Mazur game in a completely regular topological spaceX is shown to be equivalent to generic stability properties of optimization problems generated by the continuous bounded real-valued functions inX.Research partially supported by the National Foundation for Scientific Research at the Bulgarian Ministry of Education and Science under Grant Number MM-408/94.     

Winning Sets, Quasiconformal Maps and Diophantine Approximation

This paper describes two new types of winning sets in \mathbbRⁿ{\mathbb{R}^n}, defined using variants of Schmidt’s game. These strong and absolute winning sets include many Diophantine sets of measure zero and first category, and have good behavior under countable intersections. Most notably, they are invariant under quasiconformal maps, while classical winning sets are not.     

σ‐short Boolean algebras

We introduce properties of Boolean algebras which are closely related to the existence of winning strategies in the Banach‐Mazur Boolean game. A σ‐short Boolean algebra is a Boolean algebra that has a dense subset in which every strictly descending sequence of length ω does not have a nonzero lower bound. We give a characterization of σ‐short Boolean algebras and study properties of σ‐short Boolean algebras. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the optimality of the uniform random strategy

Biased Maker‐Breaker games, introduced by Chvátal and Erd?s, are central to the field of positional games and have deep connections to the theory of random structures. The main questions are to determine the smallest bias needed by Breaker to ensure that Maker ends up with an independent set in a given hypergraph. Here we prove matching general winning criteria for Maker and Breaker when the game hypergraph satisfies certain “container‐type” regularity conditions. This will enable us to answer the main question for hypergraph generalizations of the H‐building games studied by Bednarska and ?uczak as well as a generalization of the van der Waerden games introduced by Beck. We find it remarkable that a purely game‐theoretic deterministic approach provides the right order of magnitude for such a wide variety of hypergraphs, while the analogous questions about sparse random discrete structures are usually quite challenging.