Construction of the Solvability Set in Differential Games with Simple Motion and Nonconvex Terminal Set

We consider planar zero-sum differential games with simple motion, fixed terminal time, and polygonal terminal set. The geometric constraint on the control of each player is a convex polygonal set or a line segment. In the case of a convex terminal set, an explicit formula is known for the solvability set (a level set of the value function, maximal u-stable bridge, viability set). The algorithm corresponding to this formula is based on the set operations of algebraic sum and geometric difference (the Minkowski difference). We propose an algorithm for the exact construction of the solvability set in the case of a nonconvex polygonal terminal set. The algorithm does not involve the additional partition of the time interval and the recovery of intermediate solvability sets at additional instants. A list of half-spaces in the three-dimensional space of time and state coordinates is formed and processed by a finite recursion. The list is based on the polygonal terminal set with the use of normals to the polygonal constraints on the controls of the players.     

Numerical construction of Nash and Stackelberg solutions in a two-player linear non-zero-sum positional differential game

Numerical methods are proposed for constructing Nash and Stackelberg solutions in a two-player linear non-zero-sum positional differential game with terminal cost functionals and geometric constraints on the players’ controls. The formalization of the players’ strategies and of the motions generated by them is based on the formalization and results from the theory of positional zero-sum differential games developed by N.N. Krasovskii and his school. It is assumed that the game is reduced to a planar game and the constraints on the players’ controls are given in the form of convex polygons. The problem of finding solutions of the game may be reduced to solving nonstandard optimal control problems. Several computational geometry algorithms are used to construct approximate trajectories in these problems, in particular, algorithms for constructing the convex hull as well as the union, intersection, and algebraic sum of polygons.     

Semigroup property of the program absorption operator in games with simple motions on the plane

The program absorption operator takes the terminal set given at the terminal time to some set defined at the initial time. For differential games with simple motions on the plane, we obtain sufficient conditions under which the semigroup property also holds in the case of a nonconvex terminal set.     

A game of optimal pursuit of one object by several

A differential game in which m dynamical objects pursue a single one is investigated. All the players perform simple motions. The termination time of the game is fixed. The controls of the first k (k ⩽ m) pursuers are subject to integral constraints and the controls of the other pursuers and the evader are subject to geometric constraints. The payoff of the game is the distance between the evader and the closest pursuer at the instant the game is over. Optimal strategies for the players are constructed and the value of the game is found.     

Solution methods for two-player differential games

A numerical solution method is proposed for the pursuit-and-evasion game in which the terminal set is the sum of a two-dimensional convex compactum and a linear subspace of codimension 2. The “convexification method” is applied to compute the alternated sums. Simple switching lines are constructed for the case when the set of constraints on pursuer controls is a polyhedron. These simple switching lines essentially simplify the construction of a pursuit strategy in the convex programming problem. Translated from Nelineinye Dinamicheskie Sistemy: Kachestvennyi Analiz i Upravlenie — Sbornik Trudov, No. 2, pp. 49–66, 1994.     

On intersections of abelian and nilpotent subgroups in finite groups. I

We consider Pontryagin’s generalized nonstationary example with identical dynamic and inertial capabilities of the players under phase constraints on the evader’s states. The boundary of the phase constraints is not a “death line” for the evader. The set of admissible controls is a ball centered at the origin, and the terminal sets are the origin. We obtain sufficient conditions for a multiple capture of one evader by a group of pursuers in the case when some functions corresponding to the initial data and to the parameters of the game are recurrent.     

Cores of convex games

The core of ann-person game is the set of feasible outcomes that cannot be improved upon by any coalition of players. A convex game is defined as one that is based on a convex set function. In this paper it is shown that the core of a convex game is not empty and that it has an especially regular structure. It is further shown that certain other cooperative solution concepts are related in a simple way to the core: The value of a convex game is the center of gravity of the extreme points of the core, and the von Neumann-Morgenstern stable set solution of a convex game is unique and coincides with the core.     

Collusive game solutions via optimization

A Nash-based collusive game among a finite set of players is one in which the players coordinate in order for each to gain higher payoffs than those prescribed by the Nash equilibrium solution. In this paper, we study the optimization problem of such a collusive game in which the players collectively maximize the Nash bargaining objective subject to a set of incentive compatibility constraints. We present a smooth reformulation of this optimization problem in terms of a nonlinear complementarity problem. We establish the convexity of the optimization problem in the case where each player's strategy set is unidimensional. In the multivariate case, we propose upper and lower bounding procedures for the collusive optimization problem and establish convergence properties of these procedures. Computational results with these procedures for solving some test problems are reported. It is with great honor that we dedicate this paper to Professor Terry Rockafellar on the occasion of his 70th birthday. Our work provides another example showing how Terry's fundamental contributions to convex and variational analysis have impacted the computational solution of applied game problems. This author's research was partially supported by the National Science Foundation under grant ECS-0080577. This author's research was partially supported by the National Science Foundation under grant CCR-0098013.     

On the Numerical Solution of Differential Games for Neutral-Type Linear Systems

The paper deals with a zero-sum differential game, in which the dynamics of a conflict-controlled system is described by linear functional differential equations of neutral type and the quality index is the sum of two terms: the first term evaluates the history of motion of the system realized up to the terminal time, and the second term is an integral–quadratic evaluation of the corresponding control realizations of the players. To calculate the value and construct optimal control laws in this differential game, we propose an approach based on solving a suitable auxiliary differential game, in which the motion of a conflict-controlled system is described by ordinary differential equations and the quality index evaluates the motion at the terminal time only. To find the value and the saddle point in the auxiliary differential game, we apply the so-called method of upper convex hulls, which leads to an effective solution in the case under consideration due to the specific structure of the quality index and the geometric constraints on the control actions of the players. The efficiency of the approach is illustrated by an example, and the results of numerical simulations are presented. The constructed optimal control laws are compared with the optimal control procedures with finitedimensional approximating guides, which were developed by the authors earlier.     

Two evasion problems in a plane with separate controls and non-convex terminal sets

Two different pursuit-evasion games are considered from the evader's point of view. The phase space is a plane, each of the two players controlling the motion of a point only along its own coordinate. The terminal sets are not convex; in the first problem, the set is an arc of a circle, in the second, the union of tow segments. In both games evasion cannot the achieved by means of programmed controls, but it can be achieved using feedback control. However, the strategies, which are continuous functions of the phase vector, have different properties in each problem. In the first, they cannot guarantee evasion (which is typical for the linear-convex case as well), but in the second they can (which is impossible in linear-convex games with a fixed final time). Verification that evasion is unachievable using such strategies reduces here to proving the solvability of a certain initial-value problem for an advanced differential equation, to which the Schauder principle is applicable.     

The construction of stable bridges in differential games with phase constraints

A differential approach-and-evasion game in a finite time interval is considered [1]. It is assumed that the positions of the game are constricted by certain constraints which represent a closed set in the space of the positions. In the case of the first player, it is necessary to ensure that the phase point falls into the terminal set at a finite instant of time and, in the case of the second player, that this terminal set is evaded at this instant [1]. A method is proposed for the approximate construction of the positional absorption set, that is, the set of all positions belonging to a constraint from which the problem of approach facing the first player is solvable. Relations are written out which determine the system of sets which approximates the positional absorption set. The main result is a proof of the convergence of the approximate system of sets to the positional absorption set and the construction of a computational procedure for constructing the approximate system of sets.     

Approximation of three-dimensional convex bodies by affine-regular prisms

The author suggests a method for constructing a differential game with given successful solvability set of the guidance problem. By using this method, it is shown that the sections of the successful solvability set can be sufficiently irregular: the sections of the successful solvability set can discontinuously depend on time, and they can be disconnected sets even in the case where the terminal set is connected. Also, the author obtains a sufficient condition for the continuous dependence of sections of the successful solvability sets on time. Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 53, Suzdal Conference-2006, Part 1, 2008.     

Existence theorems of equilibrium points in stackelberg

A two players static. Stackelberg game is considered with constraints on the decision variables. Existence theorems of equilibrium points are given when the reaction set of the follower to the strategy of the leader, is a singleton. Some definition are presented and discussed and a simple existence theorem is given also in the case when the follower has more than one element in his reaction set. Finally an example of dynamic Stackelbebg game- is analized to emphasize some features arising when constraints are present on control variables.     

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.     

Convexity properties for interior operator games

Interior operator games arose by abstracting some properties of several types of cooperative games (for instance: peer group games, big boss games, clan games and information market games). This reason allow us to focus on different problems in the same way. We introduced these games in Bilbao et al. (Ann. Oper. Res. 137:141–160, 2005) by a set system with structure of antimatroid, that determines the feasible coalitions, and a non-negative vector, that represents a payoff distribution over the players. These games, in general, are not convex games. The main goal of this paper is to study under which conditions an interior operator game verifies other convexity properties: 1-convexity, k-convexity (k≥2 ) or semiconvexity. But, we will study these properties over structures more general than antimatroids: the interior operator structures. In every case, several characterizations in terms of the gap function and the initial vector are obtained. We also find the family of interior operator structures (particularly antimatroids) where every interior operator game satisfies one of these properties.     

On the theory of three-person differential games

A differential game of three players with dynamics described by linear differential equations under geometric constraints on the control parameters is considered. Sufficient conditions are obtained for the existence of the first player’s strategy guaranteeing that the trajectory of the game reaches a given target set for any admissible control of the second player and avoids the terminal set of the third player. An algorithm of constructing the first player’s strategy guaranteeing the game’s termination in finite time is suggested. A solution of a model example is given.     

A simple pursuit-evasion problem on a ball of a Riemannian manifold

Mathematical Notes - Apursuit-evasion differential game with simple motions, in which points (players) move on a ball of a Riemannian manifold, is studied. It is assumed that all players have the...     

A globalized Newton method for the computation of normalized Nash equilibria

The generalized Nash equilibrium is a Nash game, where not only the players’ cost functions, but also the constraints of a player depend on the rival players decisions. We present a globally convergent algorithm that is suited for the computation of a normalized Nash equilibrium in the generalized Nash game with jointly convex constraints. The main tool is the regularized Nikaido–Isoda function as a basis for a locally convergent nonsmooth Newton method and, in another way, for the definition of a merit function for globalization. We conclude with some numerical results.     

Two-stage non-cooperative games with risk-averse players

This paper formally introduces and studies a non-cooperative multi-agent game under uncertainty. The well-known Nash equilibrium is employed as the solution concept of the game. While there are several formulations of a stochastic Nash equilibrium problem, we focus mainly on a two-stage setting of the game wherein each agent is risk-averse and solves a rival-parameterized stochastic program with quadratic recourse. In such a game, each agent takes deterministic actions in the first stage and recourse decisions in the second stage after the uncertainty is realized. Each agent’s overall objective consists of a deterministic first-stage component plus a second-stage mean-risk component defined by a coherent risk measure describing the agent’s risk aversion. We direct our analysis towards a broad class of quantile-based risk measures and linear-quadratic recourse functions. For this class of non-cooperative games under uncertainty, the agents’ objective functions can be shown to be convex in their own decision variables, provided that the deterministic component of these functions have the same convexity property. Nevertheless, due to the non-differentiability of the recourse functions, the agents’ objective functions are at best directionally differentiable. Such non-differentiability creates multiple challenges for the analysis and solution of the game, two principal ones being: (1) a stochastic multi-valued variational inequality is needed to characterize a Nash equilibrium, provided that the players’ optimization problems are convex; (2) one needs to be careful in the design of algorithms that require differentiability of the objectives. Moreover, the resulting (multi-valued) variational formulation cannot be expected to be of the monotone type in general. The main contributions of this paper are as follows: (a) Prior to addressing the main problem of the paper, we summarize several approaches that have existed in the literature to deal with uncertainty in a non-cooperative game. (b) We introduce a unified formulation of the two-stage SNEP with risk-averse players and convex quadratic recourse functions and highlight the technical challenges in dealing with this game. (c) To handle the lack of smoothness, we propose smoothing schemes and regularization that lead to differentiable approximations. (d) To deal with non-monotonicity, we impose a generalized diagonal dominance condition on the players’ smoothed objective functions that facilitates the application and ensures the convergence of an iterative best-response scheme. (e) To handle the expectation operator, we rely on known methods in stochastic programming that include sampling and approximation. (f) We provide convergence results for various versions of the best-response scheme, particularly for the case of private recourse functions. Overall, this paper lays the foundation for future research into the class of SNEPs that provides a constructive paradigm for modeling and solving competitive decision making problems with risk-averse players facing uncertainty; this paradigm is very much at an infancy stage of research and requires extensive treatment in order to meet its broad applications in many engineering and economics domains.     

Quasistrategies in an abstract guidance control problem

We consider an abstract guidance control problem with elements of uncertainty, where the control procedures are identified with set-valued quasistrategies. The goal of the control consists in the guidance to the objective set under phase constraints.We construct the solvability set by the method of program iterations which is well known in the theory of differential games. We prove that the limit of the iterative procedure has the sense of the set of positional absorption (the stable bridge) introduced by N. N. Krasovskii. This limit coincides with the solvability set in the class of quasistrategies.