Algorithms for computing Nash equilibria in deterministic LQ games

In this paper we review a number of algorithms to compute Nash equilibria in deterministic linear quadratic differential games. We will review the open-loop and feedback information case. In both cases we address both the finite and the infinite-planning horizon.     

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 one class of differential operators and their application

We use a generalized differentiation operator to construct a generalized shift operator, which makes it possible to define a generalized convolution operator in the space H(?). Next, we consider the characteristic function of this operator and introduce a generalized Laplace transform. We study the homogeneous equation of the generalized convolution operator, investigate its solvability, and consider the multipoint Vallée Poussin problem.     

Rational differential operators and their kernels

A linear differential/integral operator is associated to a rational matrix in a natural way, and the behavior is defined to be the kernel of this operator. Conditions under which two rational matrices have the same behavior are derived.     

Algorithms for lattice games

This paper provides effective methods for the polyhedral formulation of impartial finite combinatorial games as lattice games (Guo et al. Oberwolfach Rep 22: 23–26, 2009; Guo and Miller, Adv Appl Math 46:363–378, 2010). Given a rational strategy for a lattice game, a polynomial time algorithm is presented to decide (i) whether a given position is a winning position, and to find a move to a winning position, if not; and (ii) to decide whether two given positions are congruent, in the sense of misère quotient theory (Plambeck, Integers, 5:36, 2005; Plambeck and Siegel, J Combin Theory Ser A, 115: 593–622, 2008). The methods are based on the theory of short rational generating functions (Barvinok and Woods, J Am Math Soc, 16: 957–979, 2003).     

Shimura invariant differential operators and their eigenvalues

Let be the covariant Cauchy-Riemann operator and the covariant holomorphic differential operator on a line bundle over a Hermitian symmetric space . We study the Shimura invariant differential operators defined via and . We find the eigenvalues of a family of the Shimura operators and of the generators. Received October 2, 1999 / Published online October 30, 2000     

Algorithms for discounted stochastic games

In this paper, a two-person zero-sum discounted stochastic game with a finite state space is considered. The movement of the game from state to state is jointly controlled by the two players with a finite number of alternatives available to each player in each of the states. We present two convergent algorithms for arriving at minimax strategies for the players and the value of the game. The two algorithms are compared with respect to computational efficiency. Finally, a possible extension to nonzero sum stochastic game is suggested.This research was supported in part by funds allocated to the Department of Operations Research, School of Management, Case Western Reserve University under Contract No. DAHC 19-68-C-0007 (Project Themis) with the U.S. Army Research Office, Durham, North Carolina. The authors thank the referees for their valuable suggestions.     

Algorithms for computing multiplier ideals

We give algorithms for computing multiplier ideals using Gröbner bases in Weyl algebras. To this end, we define a modification of Budur-Musta?aˇ-Saito’s generalized Bernstein-Sato polynomial. We present several examples computed by our algorithm.     

A method for computing lowest eigenvalues of symmetric polynomial differential operators by semidefinite programming

A method for computing global minima of real multivariate polynomials based on semidefinite programming was developed by N.Z. Shor, J.B. Lasserre and P.A. Parrilo. The aim of this article is to extend a variant of their method to noncommutative symmetric polynomials in variables X and Y satisfying YX−XY=1 and X^*=X, Y^*=−Y. Global minima of such polynomials are defined and showed to be equal to minima of the spectra of the corresponding differential operators. We also discuss how to exploit sparsity and symmetry. Several numerical experiments are included. The last section explains how our theory fits into the framework of noncommutative real algebraic geometry.     

Space-like Weingarten surfaces in the three-dimensional Minkowski space and their natural partial differential equations

On any space-like Weingarten surface in the three-dimensional Minkowski space we introduce locally natural principal parameters and prove that such a surface is determined uniquely up to motion by a special invariant function, which satisfies a natural non-linear partial differential equation. This result can be interpreted as a solution to the Lund-Regge reduction problem for space-like Weingarten surfaces in Minkowski space. We apply this theory to linear fractional space-like Weingarten surfaces and obtain the natural non-linear partial differential equations describing them. We obtain a characterization of space-like surfaces, whose curvatures satisfy a linear relation, by means of their natural partial differential equations. We obtain the ten natural PDE’s describing all linear fractional space-like Weingarten surfaces.     

Semi-cooperative strategies for differential games

The paper is concerned with a non-cooperative differential game for two players. We first consider Nash equilibrium solutions in feedback form. In this case, we show that the Cauchy problem for the value functions is generically ill-posed. Looking at vanishing viscosity approximations, one can construct special solutions in the form of chattering controls, but these also appear to be unstable. In the second part of the paper we propose an alternative semi-cooperative pair of strategies for the two players, seeking a Pareto optimum instead of a Nash equilibrium. In this case, we prove that the corresponding Hamiltonian system for the value functions is always weakly hyperbolic.Revised: May 2004     

Dense linear manifolds and application to linear differential operators

Oscillation criteria are obtained for a class of functional differential equations including the generalized Emden-Fowler equation $\text{x}{}^{\mathrm{(n)}}\text{+ q(t) ¦x[g(t)]¦}{}^{\mathrm{\gamma }}\text{sgn}\text{(x[g(t)]) = 0, γ > 0}$, as a special case. The purpose of this paper is to extend and improve known fundamental oscillation criteria for superlinear, sublinear, and linear differential equations with retarded arguments.     

Composition problem for differential games

The task of finding a relationship between optimal control problems and differential games is considered. Two classes of differential games are shown to have the property that their solution, the value function, can be constructed from solutions to associated one-player optimal control problems.This work was partially supported under NSF Grant No. GK 355 at the Department of Electrical Engineering, University of Notre Dame, South Bend, Indiana. The author wishes to express his gratitude to Professor Celso de Renna e Souza for the motivation and guidance received throughout the work which led to this paper.     

Informational structure for differential games

A positional approach for the definition of information structure in differential games is considered. A generalization ofKuhn's theorem [1953] concerning pure strategy equivalence for finite positional games is proved.     

Algorithms for stochastic games — A survey

We consider finite state, finite action, stochastic games over an infinite time horizon. We survey algorithms for the computation of minimax optimal stationary strategies in the zerosum case, and of Nash equilibria in stationary strategies in the nonzerosum case. We also survey those theoretical results that pave the way towards future development of algorithms.

---

Zusammenfassung In dieser Arbeit werden unendlichstufige stochastische Spiele mit endlichen ZuStands- und Aktionenräumen untersucht. Es wird ein Überblick gegeben über Algorithmen zur Berechnung von optimalen stationären Minimax-Strategien in Nullsummen-Spielen und von stationären Nash-Gleichgewichtsstrategien in Nicht-Nullsummen-Spielen. Einige theoretische Ergebnisse werden vorgestellt, die für die weitere Entwicklung von Algorithmen nützlich sind.

---

---

This paper is based on the invited lectures given by the authors at the 12th Symposium for Operations Research in Passau, 1987. We are indebted to M. Abbad, Evangelista Fe, F. Thuijsman and O. J. Vrieze for valuable comments and discussion. Any remaining errors of either misinterpretation or of omission are the authors' alone.

---

Supported in part by the NSF under the grant # DMS-82601403.

---

Supported in part by the AFOSR and the NSF under the grant # ECS-8704954.     

Diffeomorphisms and differential games

This paper illustrates the usefulness of state transformations in differential games. It is shown that different state diffeomorphisms give birth to closed-loop Nash equilibrium candidates with different control and state value.