The associated maximization problem for separable games

Two-person zero-sum games with separable payoff functions are examined using the geometric concept of dual cones. It is shown that the value of such games may be found by solving an associated maximization problem. Some numerical implications, particularly the application of linear programming to finding approximate solutions, are discussed. With the value known, optimal mixed strategies may, in principle, be readily determined.This research was sponsored in part by the U.S. Air Force Office of Scientific Research, Air Force Systems Command, USAF Grant AFOSR No. 71-2116A.     

Extra-proximal methods for solving two-person nonzero-sum games

We consider two-person nonzero-sum game, both in the classical form and in the form of a game with coupled variables. An extra-proximal approach for finding the game’s solutions is suggested and justified. We provide our algorithm with an analysis of its convergence.      

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.     

Teraoka-type two-person nonzero-sum silent duel

The paper discusses a silent nonzero-sum duel between two players each of whom has a single bullet. The duel is terminated at a random time in [0, 1] given by a cumulative distribution function. It is shown that the game has a unique Nash equilibrium under a wide range of possible payoff values for simultaneous firing. This contrasts with a very similar game considered by Teraoka for which there are many Nash equilibria.This work was carried out while the second author was visiting the University of Southampton on a Postdoctoral Fellowship of The Royal Society of London.     

Side-payment contracts in two-person nonzero-sum supply chain games: Review,discussion and applications

This paper investigates supply chain coordination with side-payment contracts. We first summarize specific side-payment contracts and present our review on the literature that developed general side-payment schemes to coordinate supply chains. Following our review, we discuss two criteria that a proper side-payment contract must satisfy, and accordingly introduce a decision-dependent transfer payment function and a constant transfer term. We present the condition that the transfer function must satisfy, and use Nash arbitration scheme and Shapley value to compute the constant transfer term and derive its closed-form solution. Next, we provide a five-step procedure for the development of side-payment contract, and apply it to four supply chain games: Cournot and Bertrand games, a two-retailer supply chain game with substitutable products and a one-supplier, one-retailer supply chain. More specifically, for the Cournot game, we construct a linear transfer function and a constant side-payment to coordinate two producers. For the Bertrand game, we build a nonlinear transfer function which is equivalent to a revenue-sharing contract, and show that the constant term is zero and two firms in the game equally share the system-wide profit. For a supply chain with substitutable products, we present a side-payment contract to coordinate two retailers. For a two-echelon supply chain, we develop a proper side-payment scheme that can coordinate the supply chain and also help reduce the impact of forward buying on supply chain performance.     

An improved algorithm for finding saddlepoints of two-person zero-sum games

It is well-known that one can sort (order)n real numbers in at mostF ₀(n) =nl – 2 ^l + 1 steps (comparisons), wherel = [log₂ n]. We snow how to find the strict saddlepoint or prove its absence in anm byn matrix,m n, in at mostF ₀(m)+F ₀(m+1)+n+m – 3 + (n–m) [log₂(m+1)] steps.     

A symmetrization for finite two-person games

The symmetrization method of Gale, Kuhn and Tucker for matrix games is extended for bimatrix games. It is shown that the equilibria of a bimatrix game and its symmetrization correspond two by two. A similar result is found with respect to quasi-strong, regular and perfect equilibria.     

Further properties of nonzero-sum differential games

The general nonzero-sum differential game hasN players, each controlling a different set of inputs to a single nonlinear dynamic system and each trying to minimize a different performance criterion. These general games have several interesting features which are absent in the two bestknown special cases (the optimal control problem and the two-person, zero-sum differential game). This paper considers some of the difficulties which arise in attempting to generalize ideas which are well known in optimal control theory, such as theprinciple of optimality and the relation betweenopen-loop andclosed-loop controls. Two types of solutions are discussed: theNash equilibrium and thenoninferior set. Some simple multistage discrete games are used to illustrate phenomena which also arise in the continuous formulation.This research was supported by Joint Services Electronics Contracts Nos. N00014-67-A-0298-0006, 0005, 0008 and by NASA Grant No. NGR 22-007-068.     

Extraproximal method for solving two-person saddle-point games

An equilibrium model is proposed for a two-person saddle-point game with partially coincident or conflicting interests. Meaningful interpretations of such a game are discussed. Three variants of the extraproximal method for finding an equilibrium point are proposed, and their convergence is proved.     

Nondominated equilibrium solutions of a multiobjective two-person nonzero-sum game in extensive form and corresponding mathematical programming problem

In most of studies on multiobjective noncooperative games, games are represented in normal form and a solution concept of Pareto equilibrium solutions which is an extension of Nash equilibrium solutions has been focused on. However, for analyzing economic situations and modeling real world applications, we often see cases where the extensive form representation of games is more appropriate than the normal form representation. In this paper, in a multiobjective two-person nonzero-sum game in extensive form, we employ the sequence form of strategy representation to define a nondominated equilibrium solution which is an extension of a Pareto equilibrium solution, and provide a necessary and sufficient condition that a pair of realization plans, which are strategies of players in sequence form, is a nondominated equilibrium solution. Using the necessary and sufficient condition, we formulate a mathematical programming problem yielding nondominated equilibrium solutions. Finally, giving a numerical example, we demonstrate that nondominated equilibrium solutions can be obtained by solving the formulated mathematical programming problem.     

A linearization method inN-person nonzero-sum differential games

In the present treatment, a nonlinear system of anN-person nonzero-sum differential game is linearized with respect to the controls. It is shown that the optimal trajectory and the optimal costs of the linearized system lead, under certain conditions, to an approximation of the optimal trajectory and the optimal costs of the original nonlinear system.     

Relevant aspects in two-person games

The present paper is concerned with characterizing in a nonusual form the equilibrium points for the mixed extension of a two-person game. We study interesting properties about such equilibrium points which are concerned with different pairs of them. Finally, we introduce an elimination procedure for pure strategies and relate in a general way the complete set of equilibrium points.This work has been partially supported by the Consejo Nacional de Investigaciones Cientificas y Tecnicas, Buenos Aires, Argentina.     

Classification of two-person ordinal bimatrix games

The set of possible outcomes of a strongly ordinal bimatrix games is studied by imbedding each pair of possible payoffs as a point on the standard two-dimensional integral lattice. In particular, we count the number of different Pareto-optimal sets of each cardinality; we establish asymptotic bounds for the number of different convex hulls of the point sets, for the average shape of the set of points dominated by the Pareto-optimal set, and for the average shape of the convex hull of the point set. We also indicate the effect of individual rationality considerations on our results. As most of our results are asymptotic, the appendix includes a careful examination of the important case of 2×2 games.Supported by the Program in Discrete Mathematics and its Applications at Yale and NSF Grant CCR-8901484.     

Constrained nonzero-sum games with partially controllable strategies

The present paper deals with a class of nonzero-sum, two-person games with finite strategies when there are constraints on the strategies selected by the players. The constraints arise due to the subjective difficulty that each player often has in assigning to the states probabilities with which he is completely satisfied, and the model specifies how much each player must perturb his initial probability estimate in order to change his maximum utility alternative from the alternative originally best under the initial estimate. It is shown that the Nash-equilibrium solution of this class of nonzero-sum games can be characterized by an equivalent nonlinear program which leads in some cases to a pair of complementary eigenvalue problems. Applications to normal or approximate solutions of linear programming problems are also indicated.     

On the Stackelberg strategy in nonzero-sum games

The properties of the Stackelberg solution in static and dynamic nonzero-sum two-player games are investigated, and necessary and sufficient conditions for its existence are derived. Several game problems, such as games where one of the two players does not know the other's performance criterion or games with different speeds in computing the strategies, are best modeled and solved within this solution concept. In the case of dynamic games, linear-quadratic problems are formulated and solved in a Hilbert space setting. As a special case, nonzero-sum linear-quadratic differential games are treated in detail, and the open-loop Stackelberg solution is obtained in terms of Riccati-like matrix differential equations. The results are applied to a simple nonzero-sum pursuit-evasion problem.This work was supported in part by the US 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.     

Sequential Stackelberg equilibria in two-person games

The concept of sequential Stackelberg equilibrium is introduced in the general framework of dynamic, two-person games defined in the Denardo contracting operator formalism. A relationship between this solution concept and the sequential Nash equilibrium for an associated extended game is established. This correspondence result, which can be related to previous results obtained by Baar and Haurie (1984), is then used for studying the existence of such solutions in a class of sequential games. For the zero-sum case, the sequential Stackelberg equilibrium corresponds to a sequential maxmin equilibrium. An algorithm is proposed for the computation of this particular case of equilibrium.This research was supported by SSHRC Grant No. 410-83-1012, NSERC Grant No. A4952, and FCAR Grants Nos. 86-CE-130 and EQ-0428.The authors thank T. R. Bielecki and J. A. Filar, who pointed out some mistakes and helped improving the paper.At the time of this research, this author was with GERMA, Ecole Mohammedia d'Ingénieurs, Rabat, Morocco.     

Approximate calculation of Nash equilibria for two-person games

An approximate method for calculating Nash equilibrium points in a two-person game is developed.