On Nikaido-Isoda type theorems for discounted stochastic games

We present a class of countable state space stochastic games with discontinuous payoff functions satisfying some assumptions similar to the ones of Nikaido and Isoda for one-stage games. We prove that these games possess stationary equilibria. We show that after adding some concavity assumptions these equilibria are nonrandomized. Further, we present an example of input (or production) dynamic game satisfying the assumptions of our model. We give a closed-form solution for this game.     

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 value for multichoice games

A multichoice game is a generalization of a cooperative TU game in which each player has several activity levels. We study the solution for these games proposed by Van Den Nouweland et al. (1995) [Van Den Nouweland, A., Potters, J., Tijs, S., Zarzuelo, J.M., 1995. Cores and related solution concepts for multi-choice games. ZOR-Mathematical Methods of Operations Research 41, 289–311]. We show that this solution applied to the discrete cost sharing model coincides with the Aumann-Shapley method proposed by Moulin (1995) [Moulin, H., 1995. On additive methods to share joint costs. The Japanese Economic Review 46, 303–332]. Also, we show that the Aumann-Shapley value for continuum games can be obtained as the limit of multichoice values for admissible convergence sequences of multichoice games. Finally, we characterize this solution by using the axioms of balanced contributions and efficiency.     

A Strong Equilibrium in Noncooperative Games

A new concept of game equilibrium is proposed, which makes it possible to find a unique solution in a wide class of noncooperative games in pure strategies. Its place in the hierarchical sequence of previously known equilibria is defined. Examples of static and differential games are used to demonstrate the procedure that finds this new equilibrium.     

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.     

战斗对策:有约束极小极大途径(Ⅰ)(英文)

本文把战斗对策归结为有约束极小极大问题,讨论解的存在性．引进不连续罚函数后,把有约束问题化为无约束极小极大问题．     

Conflict dissolution by reframing game payoffs using linear perturbations

Human beings have a prevailing drive to achieve their self-interest goals or equilibrium states, which may subsume their social interests. An ideal working environment or cooperative game situation would be one in which each participant or player maximizes his/her own interest while maximizing his/her contribution to the collective group interest. This paper addresses the feasibility, methods, and bounds for reframing a generaln-person game into an ideal game in which full cooperation or a targeted solution can be induced and maintained by the players' self-interest maximization. Criteria for good reframing are introduced. Monotonic games, self-interest cooperative and noncooperative games, and a decomposition theory of general games are also introduced to facilitate the study. It is shown that everyn-person game can be written as the sum of a self-interest cooperative game and a self-interest noncooperative game. Everyn-person game can be reframed so that full cooperation can be achieved by the players' self-interest maximization. Everyn-person game can be reframed so that a targeted solution can be obtained and maintained through the players' self-interest maximization.     

战斗对策:有约束极小极大途径(I)

本文把战斗对策归结为有约束极小极大问题，讨论解的存在性．引进不连续罚函数后，把有约束问题化为无约束极小极大问题。     

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.     

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.     

A generalized linear production model: A unifying model

We introduce a generalized linear production model whose attractive feature being that the resources held by any subset of producersS is not restricted to be the vector sum of the resources held by the members ofS. We provide sufficient conditions for the non-emptiness of the core of the associated generalized linear production game, and show that if the core of the game is not empty then a solution in it can be produced from a dual optimal solution to the associated linear programming problem. Our generalized linear production model is a proper generalization of the linear production model introduced by Owen, and it can be used to analyze cooperative games which cannot be studied in the ordinary linear production model framework. We use the generalized model to show that the cooperative game induced by a network optimization problem in which players are the nodes of the network has a non-empty core. We further employ our model to prove the non-emptiness of the core of two other classes of cooperative games, which were not previously studied in the literature, and we also use our generalized model to provide an alternative proof for the non-emptiness of the core of the class of minimum cost spanning tree games. Thus, it appears that the generalized linear production model is a unifying model which can be used to explain the non-emptiness of the core of cooperative games generated by various, seemingly different, optimization models.This research was partially done while the author was visiting the Graduate School of Business Administration at Tel-Aviv University. The research was partially supported by Natural Sciences and Engineering Research Council Canada Grant A4181 and by SSHRC leave fellowship 451-83-0030.Dedicated to George B. Dantzig.     

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.     

Structural satisfaction in simple games

A fundamental maxim for any theory of social behavior is that knowledge of the theory should not cause behavior that contradicts the theory's assertions. Although this maxim consistently has been heeded in the theory of noncooperative games, it largely has been ignored in solution theory for cooperative games. Solution theory, the central concern of this paper, seeks to identify a subset of the feasible outcomes of a cooperative game that are ‘stable’ results of competition among participants, each of whom attempts to bring about an outcome he favors, rather than to prescribe ‘fair’ outcomes that accord with a standard of equity. We show that learning by participants about the solution theory can cause the outcomes identified as stable by certain solution concepts to become unstable, and discover that an important distinction in this regard is whether the solution concept requires each element of the solution set to defend itself against alternatives rather than relying on other elements for its defense. Finally, we develop a concept of ‘solid’ solutions which have a special claim for stability.The unifying theme of this paper concerns the sense in which certain outcomes of a cooperative game may be regarded as stable, and the extent to which this stability requires that the players are ignorant of the theory. Although the issues raised here have implications for the theory of cooperative games in general, Section 1 establishes the focus of the analysis on collective decision games. Section 2 develops some general perspectives on solution theory which are used in Sections 3 and 4 to evaluate the Condorcet solution, the core, the robust proposals set, von Neumann- Morgenstern solutions and competitive solutions. Section 5 presents the concept of a solid solution and relates this idea to the solution concepts reviewed earlier. We demonstrate that in general a solution concept has a strong claim to stability only if it is solid. Finally, Section 6 concludes by indicating that the basic argument also can be applied to Aumann and Maschler's bargaining sets and, more generally, to solution theory for any cooperative game.     

The semireactive bargaining set of a cooperative game

The semireactive bargaining set, a solution for cooperative games, is introduced. This solution is in general a subsolution of the bargaining set and a supersolution of the reactive bargaining set. However, on various classes of transferable utility games the semireactive and the reactive bargaining set coincide. The semireactive prebargaining set on TU games can be axiomatized by one-person rationality, the reduced game property, a weak version of the converse reduced game property with respect to subgrand coalitions, and subgrand stability. Furthermore, it is shown that there is a suitable weakening of subgrand stability, which allows to characterize the prebargaining set. Replacing the reduced game by the imputation saving reduced game and employing individual rationality as an additional axiom yields characterizations of both, the bargaining set and the semireactive bargaining set. Received September 2000/Revised version June 2001     

Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games

The noncooperative multi-leader-follower game can be formulated as a generalized Nash equilibrium problem where each player solves a nonconvex mathematical program with equilibrium constraints. Two major deficiencies exist with such a formulation: One is that the resulting Nash equilibrium may not exist, due to the nonconvexity in each players problem; the other is that such a nonconvex Nash game is computationally intractable. In order to obtain a viable formulation that is amenable to practical solution, we introduce a class of remedial models for the multi-leader-follower game that can be formulated as generalized Nash games with convexified strategy sets. In turn, a game of the latter kind can be formulated as a quasi-variational inequality for whose solution we develop an iterative penalty method. We establish the convergence of the method, which involves solving a sequence of penalized variational inequalities, under a set of modest assumptions. We also discuss some oligopolistic competition models in electric power markets that lead to multi-leader-follower games.Jong-Shi Pang: The work of this authors research was partially supported by the National Science Foundation under grant CCR-0098013 and ECS-0080577 and by the Office of Naval Research under grant N00014-02-1-0286.Masao Fukushima: The work of this authors research was partially supported by a Grant-in-Aid for Scientific Research from the Ministry of Education, Science, Culture and Sports of Japan.     

Regularity of Nash payoffs of Markovian nonzero-sum stochastic differential games

In this paper we deal with the problem of existence of a smooth solution of the Hamilton–Jacobi–Bellman–Isaacs (HJBI for short) system of equations associated with nonzero-sum stochastic differential games. We consider the problem in unbounded domains either in the case of continuous generators or for discontinuous ones. In each case we show the existence of a smooth solution of the system. As a consequence, we show that the game has smooth Nash payoffs which are given by means of the solution of the HJBI system and the stochastic process which governs the dynamic of the controlled system.     

Dynamic programming approach to discrete time dynamic feedback Stackelberg games with independent and dependent followers

Stackelberg games play an extremely important role in such fields as economics, management, politics and behavioral sciences. Stackelberg game can be modelled as a bilevel optimization problem. There exists extensive literature about static bilevel optimization problems. However, the studies on dynamic bilevel optimization problems are relatively scarce in spite of the importance in explaining and predicting some phenomena rationally. In this paper, we consider discrete time dynamic Stackelberg games with feedback information. Dynamic programming algorithms are presented for the solution of discrete time dynamic feedback Stackelberg games with multiple players both for independent followers and for dependent followers. When the followers act dependently, the game in this paper is a combination of Stackelberg game and Nash game.     

A dynamic transfer scheme deriving from the dual similar associated game

Dynamic process is an approach to cooperative games, and it can be defined as that which leads the players to a solution for cooperative games. Hwang et al. (2005) adopted Hamiache’s associated game (2001) to provide a dynamic process leading to the Shapley value. In this paper, we propose a dynamic transfer scheme on the basis of the dual similar associated game, to lead to any solution satisfying both the inessential game property and continuity, starting from an arbitrary efficient payoff vector.     

Accessibility measures to nodes of directed graphs using solutions for generalized cooperative games

The aim of this paper consists of constructing accessibility measures to the nodes of directed graphs using methods of Game Theory. Since digraphs without a predefined game are considered, the main part of the paper is devoted to establish conditions on cooperative games so that they can be used to measure accessibility. Games that satisfy desirable properties are called test games. Each ranking on the nodes is then obtained according to a pair formed by a test game and a solution defined on cooperative games whose utilities are given on ordered coalitions. The solutions proposed here are extensions of the wide family of semivalues to games in generalized characteristic function form.     

A general characterization of the mean field limit for stochastic differential games

The mean field limit of large-population symmetric stochastic differential games is derived in a general setting, with and without common noise, on a finite time horizon. Minimal assumptions are imposed on equilibrium strategies, which may be asymmetric and based on full information. It is shown that approximate Nash equilibria in the n-player games admit certain weak limits as n tends to infinity, and every limit is a weak solution of the mean field game (MFG). Conversely, every weak MFG solution can be obtained as the limit of a sequence of approximate Nash equilibria in the n-player games. Thus, the MFG precisely characterizes the possible limiting equilibrium behavior of the n-player games. Even in the setting without common noise, the empirical state distributions may admit stochastic limits which cannot be described by the usual notion of MFG solution.