A stability theorem for symmetrically rational counterplanning

In the absence of contrary information, it would seem prudent for a competitor to attribute to his opponents the same level of rationality that he himself employs. In the context of a general, linear-quadratic, nonzero-sum, two-person game, it is shown that a counterplanning procedure consistent with this principle of symmetrical rationality always converges to the unique Nash equilibrium for the game.The work of R. Kalaba and L. Tesfatsion was partially supported by the National Science Foundation under Grant No. ENG-77-28432 and by the National Institutes of Health under Grant No. GM-23732-03.     

Approximate solution of singularly perturbed nonlinear pursuit-evasion games

A methodology to obtain an approximate solution of a singularly perturbed nonlinear differential game is presented. The outcome of the game with approximate strategies, defined as extended value, is related to the saddle-point value of the game. In an example of a simple pursuit-evasion game, it is shown that the proposed methodology leads to an easily implementable feedback form solution with fairly accurate results. This approach seems to be attractive for analyzing realistic air-combat models without solving a two-point boundary-value problem.This research was partially supported by AFSC Contract No. F-49620-79-6-0135. The authors are grateful to Prof. J. V. Breakwell for encouraging the approach taken in this research. Thanks are also due to Dr. S. Gutman and Dr. J. Lewin for their useful comments.     

The sequence method for finding solutions to infinite games: A first demonstrating example

A noncooperative infinite game can be approached by a sequence of discrete games. For each game in the sequence, a Nash solution can be found as well as their limit. This idea and procedure was used before as a theoretical device to prove existence of solutions to games with continuous payoffs and recently even for a class of games with discontinuous ones (Dasgupta and Maskin, 1981). No one, however, used the method for the actual solution of a game. Here, an example demonstrates the method's usefulness in finding a solution to a two-person game on the unit square with discontinuous payoff functions.The author wishes to thank D. McFadden for very useful discussions. Financial support was provided in part by NSF Grant No. SOC-72-05551A02 to the University of California, Berkeley, California.     

A solution for noncooperative games

In this paper, we study solutions of strict noncooperative games that are played just once. The players are not allowed to communicate with each other. The main ingredient of our theory is the concept of rationalizing a set of strategies for each player of a game. We state an axiom based on this concept that every solution of a noncooperative game is required to satisfy. Strong Nash solvability is shown to be a sufficient condition for the rationalizing set to exist, but it is not necessary. Also, Nash solvability is neither necessary nor sufficient for the existence of the rationalizing set of a game. For a game with no solution (in our sense), a player is assumed to recourse to a standard of behavior. Some standards of behavior are examined and discussed.This work was sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and by the National Science Foundation under Grant No. MCS-75-17385-A01. The author is grateful to J. C. Harsanyi for his comments and to S. M. Robinson for suggesting the problem.     

Additional aspects of the Stackelberg strategy in nonzero-sum games

The Stackelberg strategy in nonzero-sum games is a reasonable solution concept for games where, either due to lack of information on the part of one player about the performance function of the other, or due to different speeds in computing the strategies, or due to differences in size or strength, one player dominates the entire game by imposing a solution which is favorable to himself. This paper discusses some properties of this solution concept when the players use controls that are functions of the state variables of the game in addition to time. The difficulties in determining such controls are also pointed out. A simple two-stage finite state discrete game is used to illustrate these properties.This work was supported in part by the U.S. Air Force under Grant No. AFOSR-68-1579D, in part by NSF under Grant No. GK-36276, and in part by the Joint Services Electronics Program under Contract No. DAAB-07-72-C-0259 with the Coordinated Science Laboratory, University of Illinois, Urbana, Illinois.     

A markov chain game with dynamic information

Two players, not knowing each other's position, move in a domain and can flash a searchlight. The game terminates when one player is caught within the area illuminated by the flash of the other. However, if this first player is not in this area, then the other player has disclosed his position to the former one, who may be able to exploit this information. The game is considered on a finite state space and in discrete time.The work of the second author was supported by ZWO, The Netherlands Organization for the Advancement of Pure Research, Contract No. B62-239, by the US Air Force Office of Scientific Research, Grant No. AFOSR-85-0245, and by the National Science Foundation, Grant No. NSF-INT-8504097.Visiting Professor at Delft University of Technology during 1986.     

A minimax problem for semilinear nonlocal competitive systems

A two-sided game for the control of a stationary semilinear competitive system with autonomous sources is considered, where the controls are the kernels of the nonlocal interaction terms. The saddle point (the optimal solution of the game) is characterized as the unique solution of the associated optimality system, which is solved by an iterative scheme.This research has been partially sponsored by DARPA under Contract No. 1868-A037-A1 with Martin Marietta Energy Systems, Inc., under Contract No. DE-AC05-84OR21400 with U.S. Department of Energy. S. Lenhart's work was also partially supported by an NSF grant.     

Evolutionary games

This paper deals with a mathematical game. As the name implies, the game concept is formulated with biological evolution in mind. An evolutionary game differs from the usual game concepts in that the players cannot choose their strategies. Rather, the strategies used by the players are handed down from generation to generation. It is the survival characteristics of a strategy that determine the outcome of the evolutionary game. Players interact and receive payoffs according to the strategies they are using. These interactions, in turn, determine the fitness of players using a given strategy. The survival characteristics of strategy are determined directly from the fitness functions. Necessary conditions for determining an evolutionarily stable strategy are developed here for a continuous game. Results are illustrated with an example.Dedicated to G. LeitmannThis work was supported by NSF Grant No. INT-82-10803 and The University of Western Australia (Visiting Fellowship, Department of Mathematics, 1983).     

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.     

Series Nash solution of two-person,nonzero-sum,linear-quadratic differential games

It is well-known that the Nash equilibrium solution of a two-person, nonzero-sum, linear differential game with a quadratic cost function can be expressed in terms of the solution of coupled generalized Riccati-type matrix differential equations. For high-order games, the numerical determination of the solution of the nonlinear coupled equations may be difficult or even impossible when the application dictates the use of small-memory computers. In this paper, a series solution is suggested by means of a parameter imbedding method. Instead of solving a high-order matrix-Riccati equation, a lower-order matrix-Riccati equation corresponding to a zero-sum game is solved. In addition, lower-order linear equations have to be solved. These solutions to lower-order equations are the coefficients of the series solution for the nonzero-sum game. Cost functions corresponding to truncated solutions are compared with those for exact Nash equilibrium solutions.This research was supported in part by the National Science Foundation under Grant No. GK-3893, in part by the Air Force under Grant No. AFOSR-68-1579B, and in part by the Joint Services Electronics Program under Contract No. DAAB-07-67-C-0199 with the Coordinated Science Laboratory, University of Illinois, Urbana, Illinois.     

Informational aspects of a class of subjective games of incomplete information: Static case

Subjective games of incomplete information are formulated where some of the key assumptions of Bayesian games of incomplete information are relaxed. The issues arising because of the new formulation are studied in the context of a class of nonzero-sum, two-person games, where each player has a different model of the game. The static game is investigated in this note. It is shown that the properties of the static subjective game are different from those of the corresponding Bayesian game. Counterintuitive outcomes of the game can occur because of the different beliefs of the players. These outcomes may lead the players to realize the differences in their models.This work was sponsored by the Office of Naval Research under Contract No. N00014-84-C-0485.     

A conjugate-point condition for a class of differential games

A conjugate-point necessary condition is derived for a class of differential games. This is done by considering the conjugate-point condition for the minimum problem and maximum problem associated with a differential game. Two definitions of a conjugate point and two conjugate-point necessary conditions result. These two definitions and necessary conditions are shown to be equivalent and are combined into one definition and one necessary condition.This research was primarily supported by the National Science Foundation under Traineeship No. 1721-80-282 and Grant No. GK-3341. Additional support was obtained from NASA Institutional Grant No. NGR-15-005-021.     

Learning algorithms for repeated bimatrix Nash games with incomplete information

The purpose of this paper is to study a particular recursive scheme for updating the actions of two players involved in a Nash game, who do not know the parameters of the game, so that the resulting costs and strategies converge to (or approach a neighborhood of) those that could be calculated in the known parameter case. We study this problem in the context of a matrix Nash game, where the elements of the matrices are unknown to both players. The essence of the contribution of this paper is twofold. On the one hand, it shows that learning algorithms which are known to work for zero-sum games or team problems can also perform well for Nash games. On the other hand, it shows that, if two players act without even knowing that they are involved in a game, but merely thinking that they try to maximize their output using the learning algorithm proposed, they end up being in Nash equilibrium.This research was supported in part by NSF Grant No. ECS-87-14777.     

Control-space properties of cooperative games

If two or more players agree to cooperate while playing a game, they help one another to minimize their respective costs as long as it is not to their individual disadvantages. This leads at once to the concept of undominated solutions to a game. Anundominated orPareto-optimal solution has the property that, compared to any other solution, at least one playerdoes worse or alldo the same if they use a solution other than the Pareto-optimal one.Closely related to the concept of a Pareto-optimal solution is theabsolutely cooperative solution. Such a solution has the property that, compared to any other permissible solution,every playerdoes no better if a solution other than the absolutely cooperative one is employed.This paper deals with control-space properties of Pareto-optimal and absolutely cooperative solutions for both static, continuous games and differential games. Conditions are given for cases in which solutions to the Pareto-optimal and absolutely cooperative games lie in the interior or on the boundary of the control set.The solution of a Pareto-optimal or absolutely cooperative game is related to the solution of a minimization problem with avector cost criterion. The question of whether or not a problem with a vector cost criterion can be reduced to a family of minimization problems with ascalar cost criterion is also discussed.An example is given to illustrate the theory.This research was supported in part by NASA Grant No. NGR-03-002-011 and ONR Contract No. N00014-69-A-0200-1020.     

Absolutely cooperative solution for a linear,multiplayer differential game

If the players of ann-player differential game agree to cooperate, then the solutions to the game should be confined to undominated ones. A property of an undominated or Pareto-optimal solution is that, when compared locally with any other solution, at least one player must do worse or all do the same if they use a solution other than the Pareto-optimal one.Closely related to the concept of a Pareto-optimal solution is the concept of an absolutely cooperative solution. The absolutely cooperative solution is given the property that, when compared locally with any other solution, every player will do no better if a solution other than the absolutely cooperative one is used.A set of necessary and sufficient conditions for an absolutely cooperative solution is presented in this paper. The circumstance under which the control variables may take on interior values is also included.This research was supported in part by NASA Grant No. NGR-03-002-011.     

Horizontal variable-speed interception game solved by forced singular perturbation technique

The time-optimal pursuit-evasion game in the horizontal plane between two airplanes is analyzed by applying the technique of forced singular perturbations (FSPT). Based on the assumption of multiple time scale separation, a zeroth-order closed-form solution is obtained, enabling one to use realistic aerodynamic and propulsion data. Control strategies are approximated by explicit feedback expressions of the state variables and the aircraft performance parameters. The zeroth-order feedback approximation is compared to the optimal openloop solution of the game. This comparison confirms the validity of the FSPT approximation for sufficiently large initial distances of separation.This work was completed during the first author's visit as a Senior NRC Associate at NASA Ames Research Center, Moffett Field, California. Its earlier phase was partially supported by AFSC Contract No. F49620-79-C-0135.     

A note on linear-quadratic pursuit-evasion differential games

An interpretation of the zero-sum, two-person, linear-quadratic differential game is provided via the bargaining and threat theory of nonzerosum games.This research was made possible through support extended by the Division of Engineering and Applied Physics, Harvard University, and the Office of Naval Research under the Joint Services Electronics Program, Contract No. N00014-67-A-0298-0006.     

On the existence of Nash strategies and solutions to coupled riccati equations in linear-quadratic games

The existence of linear Nash strategies for the linear-quadratic game is considered. The solvability of the coupled Riccati matrix equations and the stability of the closed-loop matrix are investigated by using Brower's fixed-point theorem. The conditions derived state that the linear closed-loop Nash strategies exist, if the open loop matrixA has a sufficient degree of stability which is determined in terms of the norms of the weighting matrices. WhenA is not necessarily stable, sufficient conditions for existence are given in terms of the solutions of auxiliary problems using the same procedure.This work was supported in part by the Joint Services Electronics Program (US Army, US Navy, and US Air Force) under Contract No. DAAG-29-78-C-0016, in part by the National Science Foundation under Grant No. ENG-74-20091, and in part by the Department of Energy, Electric Energy Systems Division, under Contract No. US-ERDA-EX-76-C-01-2088.     

Informational uniqueness of closed-loop Nash equilibria for a class of nonstandard dynamic games

This paper discusses an extension of the currently available theory of noncooperative dynamic games to game models whose state equations are of order higher than one. In a discrete-time framework, it first elucidates the reasons why the theory developed for first-order systems is not applicable to higher-order systems, and then presents a general procedure to obtain an informationally unique Nash equilibrium solution in the presence of random disturbances. A numerical example solved in the paper illustrates the general approach.Dedicated to G. LeitmannResearch that led to this paper was supported in part by the Office of Naval Research under Contract No N00014-82-K-0469 and in part by the U.S. Air Force under Grant No. AFOSR-84-0054.     

Extremal and game-theoretic characterizations of the probabilistic approach to income redistribution

In this paper, we cast the problem of income redistribution in two different ways, one as a nonlinear goal programming model and the other as a game theoretic model. These two approaches give characterizations for the probabilistic approach suggested by Intriligator for this problem. All three approaches reinforce the linear income redistribution plan as a desirable mechanism of income redistribution.This research was partly supported by ONR Contract No. N00014-82-K-0295 with the Center for Cybernetic Studies, The University of Texas, Austin, Texas.