Construction of a maximal stable bridge in games with simple motions on the plane

It is known that the solvability set (the maximal stable bridge) in a zero-sum differential game with simple motions, fixed terminal time, geometric constraints on the controls of the first and second players, and convex terminal set can be constructed by means of a program absorption operator. In this case, a backward procedure for the construction of t-sections of the solvability set does not need any additional partition times. We establish the same property for a game with simple motions, polygonal terminal set (which is generally nonconvex), and polygonal constraints on the players’ controls on the plane. In the particular case of a convex terminal set, the operator used in the paper coincides with the program absorption operator.     

Approximation of convex functions by projections of polyhedra

A method for approximate solution of minimization problems for multivariable convex functions with convex constraints is proposed. The main idea consists in approximation of the objective function and constraints by piecewise linear functions and subsequent reduction of the initial convex programming problem to a problem of linear programming. We present algorithms constructing approximating polygons for some classes of single variable convex functions. The many-dimensional problem is reduced to a one-dimensional one by an inductive procedure. The efficiency of the method is illustrated by numerical examples.     

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.     

Existence of a Value and a Saddle Point in Positional Differential Games for Neutral-Type Systems

For a conflict-controlled dynamical system described by functional differential equations of neutral type in Hale’s form, we consider a differential game with a performance index that estimates the motion history realized up to the terminal time and includes an integral estimation of realizations of the players’ controls. The game is formalized in the class of pure positional strategies. The main result is the proof of the existence of a value and a saddle point in this game.     

Mixed strategies and their application in the encounter-evasion differential games

A positional encounter-evasion differential game with geometric constraints on the players' controls, depending on the system's state, is examined. The concept of the players' mixed strategies is introduced and an alternative is proved which asserts that either the positional encounter game or the positional evasion game is always solvable. The paper continues the investigations in /1–4/.     

On the solution of affine generalized Nash equilibrium problems with shared constraints by Lemke’s method

Affine generalized Nash equilibrium problems (AGNEPs) represent a class of non-cooperative games in which players solve convex quadratic programs with a set of (linear) constraints that couple the players’ variables. The generalized Nash equilibria (GNE) associated with such games are given by solutions to a linear complementarity problem (LCP). This paper treats a large subclass of AGNEPs wherein the coupled constraints are shared by, i.e., common to, the players. Specifically, we present several avenues for computing structurally different GNE based on varying consistency requirements on the Lagrange multipliers associated with the shared constraints. Traditionally, variational equilibria (VE) have been amongst the more well-studied GNE and are characterized by a requirement that the shared constraint multipliers be identical across players. We present and analyze a modification to Lemke’s method that allows us to compute GNE that are not necessarily VE. If successful, the modified method computes a partial variational equilibrium characterized by the property that some shared constraints are imposed to have common multipliers across the players while other are not so imposed. Trajectories arising from regularizing the LCP formulations of AGNEPs are shown to converge to a particular type of GNE more general than Rosen’s normalized equilibrium that in turn includes a variational equilibrium as a special case. A third avenue for constructing alternate GNE arises from employing a novel constraint reformulation and parameterization technique. The associated parametric solution method is capable of identifying continuous manifolds of equilibria. Numerical results suggest that the modified Lemke’s method is more robust than the standard version of the method and entails only a modest increase in computational effort on the problems tested. Finally, we show that the conditions for applying the modified Lemke’s scheme are readily satisfied in a breadth of application problems drawn from communication networks, environmental pollution games, and power markets.     

Perturbation approach to generalized Nash equilibrium problems with shared constraints

This paper aims to consider an application of conjugate duality in convex optimization to the generalized Nash equilibrium problems with shared constraints and nonsmooth cost functions. Sufficient optimality conditions for the problems regarding to players are rewritten as inclusion problems and the maximal monotonicity of set-valued mappings generated by the subdifferentials of functions from data of GNEP is proved. Moreover, some assertions dealing with solutions to GNEP are obtained and applications of splitting algorithms to the oligopolistic market equilibrium models are presented.     

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.     

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.     

Optimization of the Hausdorff distance between sets in Euclidean space

Set approximation problems play an important role in many areas of mathematics and mechanics. For example, approximation problems for solvability sets and reachable sets of control systems are intensively studied in differential game theory and optimal control theory. In N.N. Krasovskii and A.I. Subbotin’s investigations devoted to positional differential games, one of the key problems was the problem of identification of solvability sets, which are maximal stable bridges. Since this problem can be solved exactly in rare cases only, the question of the approximate calculation of solvability sets arises. In papers by A.B. Kurzhanskii and F.L. Chernous’ko and their colleagues, reachable sets were approximated by ellipsoids and parallelepipeds.In the present paper, we consider problems in which it is required to approximate a given set by arbitrary polytopes. Two sets, polytopes A and B, are given in Euclidean space. It is required to find a position of the polytopes that provides a minimum Hausdorff distance between them. Though the statement of the problem is geometric, methods of convex and nonsmooth analysis are used for its investigation.One of the approaches to dealing with planar sets in control theory is their approximation by families of disks of equal radii. A basic component of constructing such families is best n-nets and their generalizations, which were described, in particular, by A.L. Garkavi. The authors designed an algorithm for constructing best nets based on decomposing a given set into subsets and calculating their Chebyshev centers. Qualitative estimates for the deviation of sets from their best n-nets as n grows to infinity were given in the general case by A.N. Kolmogorov. We derive a numerical estimate for the Hausdorff deviation of one class of sets. Examples of constructing best n-nets are given.     

On procedures for constructing solutions in differential games on a finite interval of time

Many problems of conflict-control theory can be reduced to approach-avoidance games with a certain terminal set. One of the main approaches to solution of such problems is the approach suggested by N. N. Krasovskii, which is based on positional constructions. The basis of these constructions consists of the extremal aiming principle at stable bridges. In this connection, the problem of constructing the maximal stable bridge, the set of all positions from which the problem of approaching the terminal set (which is the main task of one of the problem) is solvable, is important. The paper considers the approach-avoidance game on a finite interval of time in which the first player must ensure the attainment by the state vector of the control system of the terminal set on this interval, and the second player must ensure the avoidance of the terminal set. The main subject of the study is the maximal stable bridge, which is the set of positional consumption in this game. The problem of exactly constructing the set of positional consumption is solvable only in simple cases, and it is more realistic to consider and solve the problem of approximate construction of this set. The paper proposes approaches to approximate construction of the set of positional consumption based on sampling the time interval of the game and the technique of backward constructions, which has been developed at the scientific school of N. N. Krasovskii since the 1980s. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 23, Optimal Control, 2005.     

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

Shape Optimization Under Width Constraint

We introduce new numerical methods to solve optimization problems among convex bodies which satisfy standard width geometrical constraints. We describe two different numerical approaches to handle width equality and width inequality constraints. To illustrate the efficiency of our method, our algorithms are used to approximate optimal solutions of Meissner’s problem and to confirm two conjectures of Heil.     

Unification of differential games,generalized solutions of the Hamilton-Jacobi equations,and a stochastic guide

On the basis of a minimax-maximin differential game of minimal deviation of a moving object from a given target on a given time interval, we discuss the relationship between the unified form of the game and the interpretation of this game in terms of Subbotin’s generalized minimax solution of Hamilton-Jacobi equations. In addition, we consider the relationship between the chosen formalization of a differential game and investigations of this game on the basis of solutions of parabolic equations degenerating into Hamilton-Jacobi equations as the diffusion term tends to zero. The related generation of minimax and maximin controls with a stochastic guide is described. We analyze the similarity between the unified form of a differential game and the concept of differential game suggested by Pontryagin.     

Paths leading to the Nash set for nonsmooth games

Maschler, Owen and Peleg (1988) constructed a dynamic system for modelling a possible negotiation process for players facing a smooth n-person pure bargaining game, and showed that all paths of this system lead to the Nash point. They also considered the non-convex case, and found in this case that the limiting points of solutions of the dynamic system belong to the Nash set. Here we extend the model to i) general convex pure bargaining games, and to ii) games generated by “divide the cake” problems. In each of these cases we construct a dynamic system consisting of a differential inclusion (generalizing the Maschler-Owen-Peleg system of differential equations), prove existence of solutions, and show that the solutions converge to the Nash point (or Nash set). The main technical point is proving existence, as the system is neither convex valued nor continuous. The intuition underlying the dynamics is the same as (in the convex case) or analogous to (in the division game) that of Maschler, Owen, and Peleg. Received August 1997/Final version May 1998     

Absolutely expedient algorithms for learning Nash equilibria

This paper considers a multi-person discrete game with random payoffs. The distribution of the random payoff is unknown to the players and further none of the players know the strategies or the actual moves of other players. A class of absolutely expedient learning algorithms for the game based on a decentralised team of Learning Automata is presented. These algorithms correspond, in some sense, to rational behaviour on the part of the players. All stable stationary points of the algorithm are shown to be Nash equilibria for the game. It is also shown that under some additional constraints on the game, the team will always converge to a Nash equilibrium. Dedicated to the memory of Professor K G Ramanathan     

Differential games on partially overlapping sets

We suggest four new notions of optimality (equilibrium) and use them to construct a theory providing the existence and (almost always) the uniqueness of solutions of game problems (both static problems and problems described by differential equations) with partially overlapping game sets of the players; such problems, which are used when modeling conflict problems with incidental interests (or incidental profits) of the players, have not been studied in the classical theory.     

The Π-strategy in a differential game with linear control constraints

The concept of a linear constraint on the controls of the players in a differential game of pursuit, which, in a certain sense, generalizes both integral and geometrical constraints, is introduced. The optimal parallel pursuit strategy (Π-strategy) is constructed for the corresponding problem.