模糊二人零和对策的纳什均衡求解

用三角模糊数刻画二人零和对策支付值的不确定性,提出了计算模糊二人零和对策纳什均衡解的多目标规划方法.给出了一种基于区间数比较的三角形模糊数排序方法,根据该方法将模糊二人零和对策转化为多目标线性规划.通过一个数值实例说明了该方法的有效性和实用性.     

一般化两人零和模糊对策的模糊规划法

本文在充分考虑局中人的策略集是模糊子集的基础上,给出更一般化的具有模糊支付与模糊赢得的两人零和模糊对策的模糊规划模型。利用模糊数的序方法,得到了此对策求解问题可以转化为带有模糊参数的两个经典规划的求解问题。文末给出算例予以说明。     

Application of linear programming with I-fuzzy sets to matrix games with I-fuzzy goals

In this paper we study a class of linear programming problems having fuzzy goals/constraints that can be described by (Atanassov’s) I-fuzzy sets. Duality theory is developed for this class of problems in the I-fuzzy sense which is subsequently applied to define a new solution concept for two persons zero-sum matrix games with I-fuzzy goals.     

Markov games with incomplete information

We consider zero-sum Markov games with incomplete information. Here, the second player is never informed about the current state of the underlying Markov chain. The existence of a value and of optimal strategies for both players is shown. In particular, we present finite algorithms for computing optimal strategies for the informed and uninformed player. The algorithms are based on linear programming results.     

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.     

Extensions of the potential reduction algorithm for linear programming

In this work, we study several extensions of the potential reduction algorithm that was developed for linear programming. These extensions include choosing different potential functions, generating the analytic center of a polytope, and finding the equilibrium of a zero-sum bimatrix game.     

Directed and weighted majority games

In this paper we deal with several classes of simple games; the first class is the one of ordered simple games (i.e. they admit of a complete desirability relation). The second class consists of all zero-sum games in the first one.First of all we introduce a natural partial order on both classes respectively and prove that this order relation admits a rank function. Also the first class turns out to be a rank symmetric lattice. These order relations induce fast algorithms to generate both classes of ordered games.Next we focus on the class of weighted majority games withn persons, which can be mapped onto the class of weighted majority zero-sum games withn+1 persons.To this end, we use in addition methods of linear programming, styling them for the special structure of ordered games. Thus, finally, we obtain algorithms, by combiningLP-methods and the partial order relation structure. These fast algorithms serve to test any ordered game for the weighted majority property. They provide a (frequently minimal) representation in case the answer to the test is affirmative.     

Search and Ambush Games with Capacities

Search games with capacities are bipersonal zero-sum games where a player has to hide a number of objects or an amount of material in a fixed number of containers and his opponent attempts to locate them. In this article, we deal with games on a discrete structureless set and on a discrete set with linear order. In both cases, the capacities under consideration are continuous. Some of the games studied generalize previously studied games.     

An attrition game on an acyclic network

This paper deals with noncooperative games in which two players conflict on a network through an attrition phenomenon. The associated problem has a variety of applications, but we model the problem as a military conflict between an attacker and a defender on an acyclic network. The attacker marches from a starting node to a destination node, expecting to keep his initial members untouched during the march. The defender deploys his forces on arcs to intercept the attacker. If the attacker goes through an arc with deployed defenders, the attacker incurs casualties according to Lanchester’s linear law. In this paper, we discuss two games having the number of remaining attackers as the payoff and propose systems of linear programming formulations to derive their equilibrium points. One game is a two-person zero-sum (TPZS) one-shot game with no information and the other is a TPZS game with two stages separated by information acquisition about players’ opponents.     

Vector linear programming in zero-sum multicriteria matrix games

In this paper, a multiple-objective linear problem is derived from a zero-sum multicriteria matrix game. It is shown that the set of efficient solutions of this problem coincides with the set of Paretooptimal security strategies (POSS) for one of the players in the original game. This approach emphasizes the existing similarities between the scalar and multicriteria matrix games, because in both cases linear programming can be used to solve the problems. It also leads to different scalarizations which are alternative ways to obtain the set of all POSS. The concept of ideal strategy for a player is introduced, and it is established that a pair of Pareto saddle-point strategies exists if both players have ideal strategies. Several examples are included to illustrate the results in the paper.     

Differential games without pure strategy saddle-point solutions

In some two-player, zero-sum differential games, pure strategy saddle-point solutions do not exist. For such games, the concept of a minmax strategy is examined, and sufficient conditions for a control to be a minmax control are presented. Both the open-loop and the closed-loop cases are considered.The research was partially supported by ONR under Contract No. N00014-69-A-0200-12. An earlier version of this paper was presented at the Eleventh Annual Allerton Conference on Circuit and System Theory, Monticello, Illinois, 1973.The author wishes to acknowledge his many valuable discussions of this problem with Professor G. Leitmann and also to thank one of the reviewers for his suggestions for simplifying the proof of Theorem 2.1.     

Remarks on sensitive equilibria in stochastic games with additive reward and transition structure

A class of stochastic games with additive reward and transition structure is studied. For zero-sum games under some ergodicity assumptions 1-equilibria are shown to exist. They correspond to so-called sensitive optimal policies in dynamic programming. For a class of nonzero-sum stochastic games with nonatomic transitions nonrandomized Nash equilibrium points with respect to the average payoff criterion are also obtained. Included examples show that the results of this paper can not be extented to more general payoff or transition structure.     

Pure strategy equilibria in symmetric two-player zero-sum games

We observe that a symmetric two-player zero-sum game has a pure strategy equilibrium if and only if it is not a generalized rock-paper-scissors matrix. Moreover, we show that every finite symmetric quasiconcave two-player zero-sum game has a pure equilibrium. Further sufficient conditions for existence are provided. Our findings extend to general two-player zero-sum games using the symmetrization of zero-sum games due to von Neumann. We point out that the class of symmetric two-player zero-sum games coincides with the class of relative payoff games associated with symmetric two-player games. This allows us to derive results on the existence of finite population evolutionary stable strategies.     

Mixed strategy solutions for quadratic games

Mixed strategy solutions are given for two-person, zero-sum games with payoff functions consisting of quadratic, bilinear, and linear terms, and strategy spaces consisting of closed balls in a Hilbert space. The results are applied to linear-quadratic differential games with no information, and with quadratic integral constraints on the control functions.     

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.     

Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon

In this paper we propose a new class of games, the “strategically zero-sum games,” which are characterized by a special payoff structure. We show that for a large body of correlation schemes which includes the correlated strategies “à la Aumann”, strategically zero-sum games are exactly these games for which no completely mixed Nash equilibrium can be improved upon.     

Constrainedn-person games

The usual properties of a characteristic function game were derived byvon Neumann andMorgenstern from the properties of a game in normal form. In this paper we give a linear programming principle for the calculation of the characteristic function. The principle is a direct application ofCharnes' linear programming method for the calculation of the optimal strategies and the value of a two-person zero-sum game. The linear programming principle gives another method for proving the standard properties of a characteristic function when it is derived from a game in normal form. Using an idea originated byCharnes for two person games, we develop the concept of a constrainedn-person game as a simple, practical extension of ann-person game. However the characteristic function for a constrainedn-person game may not satisfy properties, such as superadditivity, usually associated with a characteristic function.     

Existence of Value and Saddle Point in Infinite-Dimensional Differential Games

We study two-player zero-sum differential games of finite duration in a Hilbert space. Following the Berkovitz notion of strategies, we prove the existence of value and saddle-point equilibrium. We characterize the value as the unique viscosity solution of the associated Hamilton–Jacobi–Isaacs equation using dynamic programming inequalities.     

Book review

The concept of antagonistic games for classical discrete control problems is applied and new classes of zero-sum dynamic games on networks are formulated and studied. Polynomial-time algorithms for solving max–min paths problem on networks are proposed and their applications (which might occur within certain financial applications) for solving max–min control problems and determining optimal strategies in zero-sum cyclic games are described. In addition max–min control problems with infinite time horizons which lead to cyclic games are studied and polynomial-time algorithm for solving zero value cyclic games is proposed.     

Stationary,completely mixed and symmetric optimal and equilibrium strategies in stochastic games

In this paper, we address various types of two-person stochastic games—both zero-sum and nonzero-sum, discounted and undiscounted. In particular, we address different aspects of stochastic games, namely: (1) When is a two-person stochastic game completely mixed? (2) Can we identify classes of undiscounted zero-sum stochastic games that have stationary optimal strategies? (3) When does a two-person stochastic game possess symmetric optimal/equilibrium strategies? Firstly, we provide some necessary and some sufficient conditions under which certain classes of discounted and undiscounted stochastic games are completely mixed. In particular, we show that, if a discounted zero-sum switching control stochastic game with symmetric payoff matrices has a completely mixed stationary optimal strategy, then the stochastic game is completely mixed if and only if the matrix games restricted to states are all completely mixed. Secondly, we identify certain classes of undiscounted zero-sum stochastic games that have stationary optima under specific conditions for individual payoff matrices and transition probabilities. Thirdly, we provide sufficient conditions for discounted as well as certain classes of undiscounted stochastic games to have symmetric optimal/equilibrium strategies—namely, transitions are symmetric and the payoff matrices of one player are the transpose of those of the other. We also provide a sufficient condition for the stochastic game to have a symmetric pure strategy equilibrium. We also provide examples to show the sharpness of our results.