A necessary and sufficient condition for Pareto-optimal security strategies in multicriteria matrix games

In this paper, a scalar game is derived from a zero-sum multicriteria matrix game, and it is proved that the solution of the new game with strictly positive scalarization is a necessary and sufficient condition for a strategy to be a Pareto-optimal security strategy (POSS) for one of the players in the original game. This is done by proving that a certain set, which is the extension of the set of security level vectors in the criterion function space, is convex and polyhedral. It is also established that only a finite number of scalarizations are necessary to obtain all the POSS for a player. An example is included to illustrate the main steps in the proof.This work was done while the author was a Research Associate in the Department of Electrical Engineering at the Indian Institute of Science and was financially supported by the Council of Scientific and Industrial Research, Delhi, India.The author wishes to express his gratefulness to Professor U. R. Prasad for helpful discussions and to two anonymous referees for suggestions which led to an improved presentation.     

Alfa-cut based linear programming methodology for constrained matrix games with payoffs of trapezoidal fuzzy numbers

The purpose of this paper is to develop an effective methodology for solving constrained matrix games with payoffs of trapezoidal fuzzy numbers (TrFNs), which are a type of two-person non-cooperative games with payoffs expressed by TrFNs and players’ strategies being constrained. In this methodology, it is proven that any Alfa-constrained matrix game has an interval-type value and hereby any constrained matrix game with payoffs of TrFNs has a TrFN-type value. The auxiliary linear programming models are derived to compute the interval-type value of any Alfa-constrained matrix game and players’ optimal strategies. Thereby the TrFN-type value of any constrained matrix game with payoffs of TrFNs can be directly obtained through solving the derived four linear programming models with data taken from only 1-cut and 0-cut of TrFN-type payoffs. Validity and applicability of the models and method proposed in this paper are demonstrated with a numerical example of the market share game problem.     

矩阵对策的公平性研究

众所周知，零和二人有限对策也称为矩阵对策。设做一个矩阵对策的两个局中人都希望对策结果尽可能公平。当两个局中人使用对策解中的策略进行对策时，如果对策结果最公平，那么这个对策解称为最优的。本文证明了最优对策解集的一些性质，然后给出矩阵对策公平度的概念并证明了它的一些有趣的性质。     

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.     

Solving Matrix Games with I-fuzzy Payoffs: Pareto-optimal Security Strategies Approach

A recent research work of Clemente et al. [12] on Pareto-optimal security strategies (POSS) in matrix games with fuzzy payoffs is extended to I-fuzzy scenario. Besides, the membership and the non-membership functions of the I-fuzzy values for both players are obtained by employing the technique of multiobjective optimization. The presented approach provides an efficient solution to a class of I-fuzzy matrix games with piecewise linear membership and non-membership functions. This class also includes I-fuzzy matrix games with triangular and trapezoidal I-fuzzy numbers as special cases. Further, POSS approach also provides an approximate solution to I-fuzzy matrix games with payoffs as general I-fuzzy numbers.     

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.     

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.     

Cooperative games of choosing partners and forming coalitions in the marketplace

Two games of interacting between a coalition of players in a marketplace and the residual players acting there are discussed, along with two approaches to fair imputation of gains of coalitions in cooperative games that are based on the concepts of the Shapley vector and core of a cooperative game. In the first game, which is an antagonistic one, the residual players try to minimize the coalition's gain, whereas in the second game, which is a noncooperative one, they try to maximize their own gain as a coalition. A meaningful interpretation of possible relations between gains and Nash equilibrium strategies in both games considered as those played between a coalition of firms and its surrounding in a particular marketplace in the framework of two classes of n-person games is presented. A particular class of games of choosing partners and forming coalitions in which models of firms operating in the marketplace are those with linear constraints and utility functions being sums of linear and bilinear functions of two corresponding vector arguments is analyzed, and a set of maximin problems on polyhedral sets of connected strategies which the problem of choosing a coalition for a particular firm is reducible to are formulated based on the firm models of the considered kind.     

Formulation and analysis of combat problems as zero-sum bicriterion differential games

In this paper, we present a formulation and analysis of a combat game between two players as a zero-sum bicriterion differential game. Each player's twin objectives of terminating the game on his own target set, while simultaneously avoiding his opponent's target set, are quantified in this approach. The solution in open-loop pure strategies is sought from among the Pareto-optimal security strategies of the players. A specific preference ordering on the outcomes is used to classify initial events in the assured win, draw, and mutual kill regions for the players. The method is compared with the event-constrained differential game approach, recently proposed by others. Finally, a simple example of the turret game is solved to illustrate the use of this method.     

Collusive game solutions via optimization

A Nash-based collusive game among a finite set of players is one in which the players coordinate in order for each to gain higher payoffs than those prescribed by the Nash equilibrium solution. In this paper, we study the optimization problem of such a collusive game in which the players collectively maximize the Nash bargaining objective subject to a set of incentive compatibility constraints. We present a smooth reformulation of this optimization problem in terms of a nonlinear complementarity problem. We establish the convexity of the optimization problem in the case where each player's strategy set is unidimensional. In the multivariate case, we propose upper and lower bounding procedures for the collusive optimization problem and establish convergence properties of these procedures. Computational results with these procedures for solving some test problems are reported. It is with great honor that we dedicate this paper to Professor Terry Rockafellar on the occasion of his 70th birthday. Our work provides another example showing how Terry's fundamental contributions to convex and variational analysis have impacted the computational solution of applied game problems. This author's research was partially supported by the National Science Foundation under grant ECS-0080577. This author's research was partially supported by the National Science Foundation under grant CCR-0098013.     

Numerical construction of Nash and Stackelberg solutions in a two-player linear non-zero-sum positional differential game

Numerical methods are proposed for constructing Nash and Stackelberg solutions in a two-player linear non-zero-sum positional differential game with terminal cost functionals and geometric constraints on the players’ controls. The formalization of the players’ strategies and of the motions generated by them is based on the formalization and results from the theory of positional zero-sum differential games developed by N.N. Krasovskii and his school. It is assumed that the game is reduced to a planar game and the constraints on the players’ controls are given in the form of convex polygons. The problem of finding solutions of the game may be reduced to solving nonstandard optimal control problems. Several computational geometry algorithms are used to construct approximate trajectories in these problems, in particular, algorithms for constructing the convex hull as well as the union, intersection, and algebraic sum of polygons.     

Non-cooperative stochastic dominance games

A non-cooperative stochastic dominance game is a non-cooperative game in which the only knowledge about the players' preferences and risk attitudes is presumed to be their preference orders on the set ofn-tuples of pure strategies. Stochastic dominance equilibria are defined in terms of mixed strategies for the players that are efficient in the stochastic dominance sense against the strategies of the other players. It is shown that the set of SD equilibria equals all Nash equilibria that can be obtained from combinations of utility functions that are consistent with the players' known preference orders. The latter part of the paper looks at antagonistic stochastic dominance games in which some combination of consistent utility functions is zero-sum over then-tuples of pure strategies.     

半马尔可夫对策

本文考虑半马尔可夫随机对策.在一定条件下,我们证明随机对策有值函数,两个局中人相对于折扣报酬都有最优策略.     

Application of Atanassov’s I-fuzzy set theory to matrix games with fuzzy goals and fuzzy payoffs

We aim to extend some results in [6, 7, 8, 2] on two person zero sum matrix games (TPZSMG) with fuzzy goals and fuzzy payoffs to I-fuzzy scenario. Because the payoffs of the matrix game are fuzzy numbers, the aspiration levels of the players are fuzzy as well. It is reasonable to believe that there is some indeterminacy in estimating the aspiration levels of both players from their respective expected pay offs. This situation is modeled in the game using Atanassov??s I-fuzzy set theory. A new solution concept is proposed for such games and a procedure is outlined to obtain the degrees of suitability of the aspiration levels for each of the two players.     

Optimal strategies for equal-sum dice games

In this paper, we consider a non-cooperative two-person zero-sum matrix game, called dice game. In an (n,σ) dice game, two players can independently choose a dice from a collection of hypothetical dice having n faces and with a total of σ eyes distributed over these faces. They independently roll their dice and the player showing the highest number of eyes wins (in case of a tie, none of the players wins). The problem at hand in this paper is the characterization of all optimal strategies for these games. More precisely, we determine the (n,σ) dice games for which optimal strategies exist and derive for these games the number of optimal strategies as well as their explicit form.     

Markov Games with Several Ergodic Classes

We consider Markov games of the general form characterized by the property that, for all stationary strategies of players, the set of game states is partitioned into several ergodic sets and a transient set, which may vary depending on the strategies of players. As a criterion, we choose the mean payoff of the first player per unit time. It is proved that the general Markov game with a finite set of states and decisions of both players has a value, and both players have -optimal stationary strategies. The correctness of this statement is demonstrated on the well-known Blackwell's example (Big Match).     

Zero-Sum Stochastic Games with Partial Information

We study a zero-sum stochastic game on a Borel state space where the state of the game is not known to the players. Both players take their decisions based on an observation process. We transform this into an equivalent problem with complete information. Then, we establish the existence of a value and optimal strategies for both players.     

混合策略纳什均衡的新教法

理解博弈论中的最优混合策略对本科生而言具有一定困难,而目前教材中对此内容的讲述又过于抽象.提出一个简单而有效地讲授混合策略纳什均衡的方法.首先利用猜硬币游戏引入并介绍混合策略的基本该念.再通过将混合策略加入到支付矩阵中构造拓展支付矩阵,使学生可以清晰地看到采用混合策略的结果,实现从纯策略到混合策略的自然过渡.然后引导学生思考博弈参与者采用混合策略的各种动机,并在拓展支付矩阵中检验其是否达成均衡.最后介绍最优混合策略计算的一般方法,并分析其与参与者行为动机之间的一致性.课堂实践证明,方法可以有效提高学生对混合策略纳什均衡的综合理解,学生不仅能够更好地掌握求解技术,而且能更深入地理解其经济学含义.