Total Reward Stochastic Games and Sensitive Average Reward Strategies

In this paper, total reward stochastic games are surveyed. Total reward games are motivated as a refinement of average reward games. The total reward is defined as the limiting average of the partial sums of the stream of payoffs. It is shown that total reward games with finite state space are strategically equivalent to a class of average reward games with an infinite countable state space. The role of stationary strategies in total reward games is investigated in detail. Further, it is outlined that, for total reward games with average reward value 0 and where additionally both players possess average reward optimal stationary strategies, it holds that the total reward value exists.     

Zero-sum games for continuous-time Markov jump processes with risk-sensitive finite-horizon cost criterion

In this paper we study the zero-sum games for continuous-time Markov jump processes under the risk-sensitive finite-horizon cost criterion. The state space is a Borel space and the transition rates are allowed to be unbounded. Under the suitable conditions, we use a new value iteration approach to establish the existence of a solution to the risk-sensitive finite-horizon optimality equations of the players, obtain the existence of the value of the game and show the existence of saddle-point equilibria.     

Optimality in matrix games with incompletely defined payoff

We study two-person, zero-sum matrix games whose payoffs are not defined for every pair of strategies. A necessary and sufficient condition for these games to possess a value is given, and we show that the value can be approximated by using universally playable strategies.This work was supported by the Centre d'Etudes Nucléaires, Saclay, France.     

Solution concepts in two-person multicriteria games

In this paper, we propose new solution concepts for multicriteria games and compare them with existing ones. The general setting is that of two-person finite games in normal form (matrix games) with pure and mixed strategy sets for the players. The notions of efficiency (Pareto optimality), security levels, and response strategies have all been used in defining solutions ranging from equilibrium points to Pareto saddle points. Methods for obtaining strategies that yield Pareto security levels to the players or Pareto saddle points to the game, when they exist, are presented. Finally, we study games with more than two qualitative outcomes such as combat games. Using the notion of guaranteed outcomes, we obtain saddle-point solutions in mixed strategies for a number of cases. Examples illustrating the concepts, methods, and solutions are included.     

Zero-sum risk-sensitive stochastic games for continuous time Markov chains

We study infinite horizon discounted-cost and ergodic-cost risk-sensitive zero-sum stochastic games for controlled continuous time Markov chains on a countable state space. For the discounted-cost game, we prove the existence of value and saddle-point equilibrium in the class of Markov strategies under nominal conditions. For the ergodic-cost game, we prove the existence of values and saddle point equilibrium by studying the corresponding Hamilton-Jacobi-Isaacs equation under a certain Lyapunov condition.     

Nonlinear separation approach to inverse variational inequalities

In this paper, we employ the image space analysis to investigate an inverse variational inequality (for short, IVI) with a cone constraint. By virtue of the nonlinear scalarization function commonly known as the Gerstewitz function, three nonlinear weak separation functions, two nonlinear regular weak separation functions and a nonlinear strong separation function are first introduced. Then, by these nonlinear separation functions, theorems of the weak and strong alternative and some optimality conditions for IVI with a cone constraint are derived without any convexity. In particular, a global saddle-point condition for a nonlinear function is investigated. It is shown that the existence of a saddle point is equivalent to a nonlinear separation of two suitable subsets of the image space. Finally, two gap functions and an error bound for IVI with a cone constraint are obtained.     

State transformations and the derivation of Nash closed-loop equilibria for non-zero-sum differential games

In this paper the usefulness of state transformations in differential games is demonstrated. It is shown that different (admissible) state transformations give rise to different closed-loop Nash equilibrium candidates, which may all be found by solving systems of ordinary differential equations. A linear-quadratic duopoly differential game is solved to illustrate the results.     

Saddle point for differential games with strongly convex-concave integrand

On a fixed time interval we consider zero-sum nonlinear differential games for which the integrand in the criterion functional is a sufficiently strongly convex-concave function of chosen controls. It is shown that in our setting there exists a saddle point in the class of programmed strategies, and a minimax principle similar to Pontryagin's maximum principle is a necessary and sufficient condition for optimality. An example in which the class of games under study is compared with two known classes of differential games is given. Translated fromMatematicheskie Zametki, Vol. 62, No. 5, pp. 725–743, November, 1997. Translated by N. K. Kulman     

Nonlinear Separation Approach to Constrained Extremum Problems

In this paper, by virtue of a nonlinear scalarization function, two nonlinear weak separation functions, a nonlinear regular weak separation function, and a nonlinear strong separation function are first introduced, respectively. Then, by the image space analysis, a global saddle-point condition for a nonlinear function is investigated. It is shown that the existence of a saddle point is equivalent to a nonlinear separation of two suitable subsets of the image space. Finally, some necessary and sufficient optimality conditions are obtained for constrained extremum problems.     

On the saddle-point solution of a class of stochastic differential games

This paper deals with the saddle-point solution of a class of stochastic differential games described by linear state dynamics and quadratic objective functionals. The information structure of the problem is such that both players have access to a common noisy linear measurement of the state and they are permitted to utilize only this information in constructing their controls. The saddle-point solution of such differential game problems has been discussed earlier in Ref. 1, but the conclusions arrived there are incorrect, as is explicitly shown in this paper. We extensively discuss the role of information structure on the saddle-point solution of such stochastic games (specifically within the context of an illustrative discrete-time example) and then obtain the saddle-point solution of the problem originally formulated by employing an indirect approach.This work was done while the author was on sabbatical leave at Twente University of Technology, Department of Applied Mathematics, Enschede, Holland, from Applied Mathematics Division, Marmara Scientific and Industrial Research Institute, Gebze, Kocaeli, Turkey.     

Weak maximum principle and accessory problem for control problems on time scales

In this paper we derive the first and second variations for a nonlinear time scale optimal control problem with control and state-endpoints equality constraints. Using the first variation, a first order necessary condition for weak local optimality is obtained under the form of a weak maximum principle generalizing the Dubois–Reymond Lemma to the optimal control setting and time scales. A second order necessary condition in terms of the accessory problem is derived by using the nonnegativity of the second variation at all admissible directions. The control problem is studied under a controllability assumption, and with or without the shift in the state variable. These two forms of the problem are shown to be equivalent.     

Optimal control of a class of strongly nonlinear parabolic systems

This paper considers some typical optimal control problems for a class of strongly nonlinear parabolic systems. After some necessary preparation, it is shown that the family of admissible trajectories is a weakly closed and weakly sequentially compact subset of a reflexive Banach space and that the set of attainable states at any given time is a weakly compact subset of a Hilbert space. Using these basic results, proofs of existence of optimal controls are presented. A terminal control problem, a special Bolza problem, and a time optimal control problem are solved, and the necessary conditions of optimality for the corresponding control problems are given.     

Nonlinear separation in the image space with applications to constrained optimization

In this paper, by means of the image space analysis, we obtain optimality conditions for vector optimization of objective multifunction with multivalued constraints based on disjunction of two suitable subsets of the image space. By the oriented distance function a nonlinear regular separation is introduced and some optimality conditions for the constrained extremum problem are obtained. It is shown that the existence of a nonlinear separation is equivalent to a saddle point condition for the generalized Lagrangian function.     

Zero-sum games with incompletely defined payoff

It is shown that a saddle-point solution exists in a two-person, zero-sum game whose payoff is given by a matrix which is not completely defined. On the other hand, we show that such games do not always have a value, so that a saddle-point solution is not necessarily an optimal solution.This work was supported by the Centre d'Etudes Atomiques, Saclay, France.     

Some thoughts on saddle-point conditions and information structures in zero-sum differential games

For a very simple two-stage, linear-quadratic, zero-sum difference game with dynamic information structure, we show that (i) there exist nonlinear saddle-point strategies which require the same existence conditions as the well-known linear, closed-loop, no-memory solution and (ii) there exist both linear and nonlinear saddle-point strategies which require more stringent conditions than the unique open-loop solution. We then discuss the implication of this result with respect to the existence of saddle points in zero-sum differential games for different information patterns.     

Separation Approach for Augmented Lagrangians in Constrained Nonconvex Optimization

This paper aims at showing that the class of augmented Lagrangian functions, introduced by Rockafellar and Wets, can be derived, as a particular case, from a nonlinear separation scheme in the image space associated with the given problem; hence, it is part of a more general theory. By means of the image space analysis, local and global saddle-point conditions for the augmented Lagrangian function are investigated. It is shown that the existence of a saddle point is equivalent to a nonlinear separation of two suitable subsets of the image space. Under second-order sufficiency conditions in the image space, it is proved that the augmented Lagrangian admits a local saddle point. The existence of a global saddle point is then obtained under additional assumptions that do not require the compactness of the feasible set.     

Regularized extragradient method for searching for an equilibrium point in two-person saddle-point games

A two-person saddle-point game with approximately given input data is examined. Since, in games of this type, the search for an equilibrium point is unstable with respect to perturbations in the input data, two variants of the regularized extragradient method are proposed. Their convergence is analyzed, and a regularizing operator is constructed.     

Sufficient Optimality Conditions for Optimal Control Problems with State Constraints

It is well-known in optimal control theory that the maximum principle, in general, furnishes only necessary optimality conditions for an admissible process to be an optimal one. It is also well-known that if a process satisfies the maximum principle in a problem with convex data, the maximum principle turns to be likewise a sufficient condition. Here an invexity type condition for state constrained optimal control problems is defined and shown to be a sufficient optimality condition. Further, it is demonstrated that all optimal control problems where all extremal processes are optimal necessarily obey this invexity condition. Thus optimal control problems which satisfy such a condition constitute the most general class of problems where the maximum principle becomes automatically a set of sufficient optimality conditions.     

Perfect equilibrium points and lexicographic domination

This paper investigates a problem of the perfect equilibrium point in games in normal form by introducing a lexicographic domination of strategies for players, which turns out to be equivalent to a “local” domination of strategies. It is shown that a perfect equilibrium point is lexicographically undominated, and moreover that the lexicographic domination can narrow down the set of undominated equilibrium points in the ordinary sense when there are more than two players in a game.