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.     

Solution concepts in continuous-kernel multicriteria games

This paper considers nonzero-sum multicriteria games with continuous kernels. Solution concepts based on the notions of Pareto optimality, equilibrium, and security are extended to these games. Separate necessary and sufficient conditions and existence results are presented for equilibrium, Pareto-optimal response, and Pareto-optimal security strategies of the players.This paper is based partially on research supported by the Council of Scientific and Industrial Research, India, through a Research Associateship Grant to the first author.The authors are grateful to two anonymous referees for suggesting useful changes and pointing out some errors in a previous draft.     

Qualitative analysis of secured outcome regions for two-target games

Qualitative (game of kind) outcomes of two-target games are analyzed in this paper, under both the zero-sum and nonzero-sum preference ordering of outcomes by the players. The outcome regions of each player are defined from a security standpoint. The secured draw and mutual-kill regions of a player depend explicitly on his preference ordering of outcomes and should be constructed separately for each player, especially in a nonzero-sum game. General guidelines are presented for identifying the secured outcome regions of players in a class of two-target games that satisfy an Isaacs-like condition, in terms of the qualitative solutions of the two underlying single-target pursuit-evasion games. A construction has been proposed for obtaining the qualitative solution of a large class of two-target games. Illustrative examples are included.This work was done while the first author was a Research Associate in the Department of Electrical Engineering at the Indian Institute of Science, Bangalore, and was financially supported by the Council of Scientific and Industrial Research, Delhi, India.     

Multicriteria Goal Games

In this paper, we deal with multicriteria matrix games. Different solution concepts have been proposed to cope with these games. Recently, the concept of Pareto-optimal security strategy which assures the property of security in the individual criteria against an opponent's deviation in strategy has been introduced. However, the idea of security behind this concept is based on expected values, so that this security might be violated by mixed strategies when replications are not allowed. To avoid this inconvenience, we propose in this paper a new concept of solution for these games: the G-goal security strategy, which includes as part of the solution the probability of obtaining prespecified values in the payoff functions. Thus, attitude toward risk together with payoff values are considered jointly in the solution analysis.     

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.     

Pareto-Optimal Security Strategies as Minimax Strategies of a Standard Matrix Game

We prove that, in a multicriteria matrix game, a strategy is a Pareto-optimal security strategy if and only if it is a minimax strategy of a standard matrix game that is obtained by a suitable weighting of the criteria.     

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.     

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.     

Robust game theory

We present a distribution-free model of incomplete-information games, both with and without private information, in which the players use a robust optimization approach to contend with payoff uncertainty. Our ``robust game' model relaxes the assumptions of Harsanyi's Bayesian game model, and provides an alternative distribution-free equilibrium concept, which we call ``robust-optimization equilibrium,' to that of the ex post equilibrium. We prove that the robust-optimization equilibria of an incomplete-information game subsume the ex post equilibria of the game and are, unlike the latter, guaranteed to exist when the game is finite and has bounded payoff uncertainty set. For arbitrary robust finite games with bounded polyhedral payoff uncertainty sets, we show that we can compute a robust-optimization equilibrium by methods analogous to those for identifying a Nash equilibrium of a finite game with complete information. In addition, we present computational results. The research of the author was partially supported by a National Science Foundation Graduate Research Fellowship and by the Singapore-MIT Alliance. The research of the author was partially supported by the Singapore-MIT Alliance.     

A multistage game with incomplete information requiring an infinite memory

This paper describes a zero-sum, discrete, multistage, time-lag game in which, for one player, there is no integerk such that an optimal strategy, for a new move during play, can always be determined as a function of the pastk state positions; that is, the player requires an infinite memory. The game is a pursuit-evasion game with the payoff to the maximizing player being the time to capture.This paper is the result of work carried out at the University of Adelaide, Adelaide, Australia, under an Australian Commonwealth Postgraduate Award.The author should like to thank the referee for his valued suggestions.     

On games corresponding to sequencing situations with ready times

This paper considers the special class of cooperative sequencing games that arise from one-machine sequencing situations in which all jobs have equal processing times and the ready time of each job is a multiple of the processing time.By establishing relations between optimal orders of subcoalitions, it is shown that each sequencing game within this class is convex.This author is financially supported by the Dutch Organization for Scientific Research (NWO).     

Multicriterion Aerodynamic Shape Design Optimization and Inverse Problems Using Control Theory and Nash Games

Multicriterion design is gaining importance in aeronautics in order to cope with new needs of society. In the literature, contributions to single discipline and/or single-point design optimization abound. The goal of this paper is to introduce a new approach combining the adjoint method with a formulation derived from game theory for multipoint aerodynamic design problems. Transonic flows around lifting airfoils are analyzed via Euler computations. Airfoil shapes are optimized according to various aerodynamic criteria. The notion of player is introduced. In a competitive Nash game, each player attempts to optimize its own criterion through a symmetric exchange of information with others. A Nash equilibrium is reached when each player, constrained by the strategy of the others, cannot improve further its own criterion. Specific real and virtual symmetric Nash games are implemented to set up an optimization strategy for design under conflict. This work has benefited partially from the support of the National Science Foundation of China Grant NSFC-10372040 and Scientific Research Foundation (SRF) for Returned Overseas Chinese Scholars (ROCS) Grant 2003-091. The first author acknowledges the support of INRIA (Institut National de Recherche en Information et en Automatique), France.     

On the saddle-point solution of a class of stochastic differential games

This paper deals with the saddle-point solution of a class of stochastic differential games described by linear state dynamics and quadratic objective functionals. The information structure of the problem is such that both players have access to a common noisy linear measurement of the state and they are permitted to utilize only this information in constructing their controls. The saddle-point solution of such differential game problems has been discussed earlier in Ref. 1, but the conclusions arrived there are incorrect, as is explicitly shown in this paper. We extensively discuss the role of information structure on the saddle-point solution of such stochastic games (specifically within the context of an illustrative discrete-time example) and then obtain the saddle-point solution of the problem originally formulated by employing an indirect approach.This work was done while the author was on sabbatical leave at Twente University of Technology, Department of Applied Mathematics, Enschede, Holland, from Applied Mathematics Division, Marmara Scientific and Industrial Research Institute, Gebze, Kocaeli, Turkey.     

Computing the cores of strategic games with punishment–dominance relations

In this paper, we discuss the computational complexity of the strategic cores of a class of n-person games defined by Masuzawa (Int J Game Theory 32:479–483, 2003), which includes economic situations with monotone externality. We propose an algorithm for finding an α-core strategy of any game in this class which, counting the evaluation of a payoff for a strategy profile as one step, terminates after O(n ³· M) operations, where M is the maximum size of a strategy set of any of the n players. The idea underlying this method is based on the property of reduced games. This paper is based on a part of the doctoral dissertation of the author. The author thanks Mikio Nakayama, Masashi Umezawa, William Thomson, an associate editor, and the anonymous referee for their helpful comments, suggestions, and advice. Thanks are also due to Yukihiko Funaki for a comment that led the author to this subject. The author is responsible for errors and inadvertencies.     

Bicriterion differential games with qualitative outcomes

Combat games are studied as bicriterion differential games with qualitative outcomes determined by threshold values on the criterion functions. Survival and capture strategies of the players are defined using the notion of security levels. Closest approach survival strategies (CASS) and minimum risk capture strategies (MRCS) are important strategies for the players identified as solutions to four optimization problems involving security levels. These are used, in combination with the preference orderings of the qualitative outcomes by the players, to delineate the win regions and the secured draw and mutual kill regions for the players. It is shown that the secured draw regions and the secured mutual kill regions for the two players are not necessarily the same. Simple illustrative examples are given.This paper is based partially on research supported by the Council of Scientific and Industrial Research, India, through a Research Associateship Grant to the second author.     

Polytope Games

Starting from the definition of a bimatrix game, we restrict the pair of strategy sets jointly, not independently. Thus, we have a set , which is the set of all feasible strategy pairs. We pose the question of whether a Nash equilibrium exists, in that no player can obtain a higher payoff by deviating. We answer this question affirmatively for a very general case, imposing a minimum of conditions on the restricted sets and the payoff. Next, we concentrate on a special class of restricted games, the polytope bimatrix game, where the restrictions are linear and the payoff functions are bilinear. Further, we show how the polytope bimatrix game is a generalization of the bimatrix game. We give an algorithm for solving such a polytope bimatrix game; finally, we discuss refinements to the equilibrium point concept where we generalize results from the theory of bimatrix games.     

Periodic stopping games

Stopping games (without simultaneous stopping) are sequential games in which at every stage one of the players is chosen, who decides whether to continue the interaction or stop it, whereby a terminal payoff vector is obtained. Periodic stopping games are stopping games in which both of the processes that define it, the payoff process as well as the process by which players are chosen, are periodic and do not depend on the past choices. We prove that every periodic stopping game without simultaneous stopping, has either periodic subgame perfect ϵ-equilibrium or a subgame perfect 0-equilibrium in pure strategies. This work is part of the master thesis of the author done under the supervision of Prof. Eilon Solan. I am thankful to Prof. Solan for his inspiring guidance. I also thank two anonymous referees of the International Journal of Game Theory for their comments.     

Avoiding unfairness of Owen allocations in linear production processes

This paper deals with cooperation situations in linear production problems in which a set of goods are to be produced from a set of resources so that a certain benefit function is maximized, assuming that resources not used in the production plan have no value by themselves. The Owen set is a well-known solution rule for the class of linear production processes. Despite their stability properties, Owen allocations might give null payoff to players that are necessary for optimal production plans. This paper shows that, in general, the aforementioned drawback cannot be avoided allowing only allocations within the core of the cooperative game associated to the original linear production process, and therefore a new solution set named EOwen is introduced. For any player whose resources are needed in at least one optimal production plan, the EOwen set contains at least one allocation that assigns a strictly positive payoff to such player.