Subgame Consistent Solutions for Cooperative Stochastic Dynamic Games

In cooperative games over time with uncertainty, a stringent condition (subgame consistency) is required for a dynamically stable solution. In particular, a cooperative solution is subgame consistent if an extension of the solution policy to a situation with a later starting time and any feasible state brought about by prior optimal behavior would remain optimal. This paper derives an analytically tractable payoff distribution procedure leading to the realization of subgame consistent solutions in cooperative stochastic dynamic games. This is the first time that subgame consistent solutions in discrete-time dynamic games under uncertainty are provided.     

Subgame Consistent Solutions of a Cooperative Stochastic Differential Game with Nontransferable Payoffs

Subgame consistency is a fundamental element in the solution of cooperative stochastic differential games. In particular, it ensures that the extension of the solution policy to a later starting time and any possible state brought about by the prior optimal behavior of the players would remain optimal. Recently, mechanisms for the derivation of subgame consistent solutions in stochastic cooperative differential games with transferable payoffs have been found. In this paper, subgame consistent solutions are derived for a class of cooperative stochastic differential games with nontransferable payoffs. The previously intractable subgame consistent solution for games with nontransferable payoffs is rendered tractable.This research was supported by the Research Grant Council of Hong Kong, Grant HKBU2056/99H and by Hong Kong Baptist University, Grant FRG/02-03/II16.Communicated by G. Leitmann     

Subgame Consistent Cooperative Solution of Dynamic Games with Random Horizon

In cooperative dynamic games, a stringent condition—that of subgame consistency—is required for a dynamically stable cooperative solution. In particular, under a subgame-consistent cooperative solution an extension of the solution policy to a subgame starting at a later time with a state brought about by prior optimal behavior will remain optimal. This paper extends subgame-consistent solutions to dynamic (discrete-time) cooperative games with random horizon. In the analysis, new forms of the Bellman equation and the Isaacs–Bellman equation in discrete-time are derived. Subgame-consistent cooperative solutions are obtained for this class of dynamic games. Analytically tractable payoff distribution mechanisms, which lead to the realization of these solutions, are developed. This is the first time that subgame-consistent solutions for cooperative dynamic games with random horizon are presented.     

Subgame-consistent cooperative solutions in randomly furcating stochastic differential games

The paradigm of randomly-furcating stochastic differential games incorporates additional stochastic elements via randomly branching payoffs in stochastic differential games. This paper considers dynamically stable cooperative solutions in randomly furcating stochastic differential games. Analytically tractable payoff distribution procedures contingent upon specific random realizations of the state and payoff structure are derived. This new approach widens the application of cooperative differential game theory to problems where the evolution of the state and future environments are not known with certainty. Important cases abound in regional economic cooperation, corporate joint ventures and environmental control. An illustration in cooperative resource extraction is presented.     

The consistent Shapley value for hyperplane games

A new value is defined for n-person hyperplane games, i.e., non-sidepayment cooperative games, such that for each coalition, the Pareto optimal set is linear. This is a generalization of the Shapley value for side-payment games. It is shown that this value is consistent in the sense that the payoff in a given game is related to payoffs in reduced games (obtained by excluding some players) in such a way that corrections demanded by coalitions of a fixed size are cancelled out. Moreover, this is the only consistent value which satisfies Pareto optimality (for the grand coalition), symmetry and covariancy with respect to utility changes of scales. It can be reached by players who start from an arbitrary Pareto optimal payoff vector and make successive adjustments.     

Consistent and covariant solutions for TU games

One of the important properties characterizing cooperative game solutions is consistency. This notion establishes connections between the solution vectors of a cooperative game and those of its reduced game. The last one is obtained from the initial game by removing one or more players and by giving them the payoffs according to a specific principle (e.g. a proposed payoff vector). Consistency of a solution means that the restriction of a solution payoff vector of the initial game to any coalition belongs to the solution set of the corresponding reduced game. There are several definitions of the reduced games (cf., e.g., the survey of T. Driessen [2]) based on some intuitively acceptable characteristics. In the paper some natural properties of reduced games are formulated, and general forms of the reduced games possessing some of them are given. The efficient, anonymous, covariant TU cooperative game solutions satisfying the consistency property with respect to any reduced game are described.The research was supported by the NWO grant 047-008-010 which is gratefully acknowledgedReceived: October 2001     

Dynamically stable cooperative solutions in randomly furcating differential games

The paradigm of randomly furcating differential games incorporates stochastic elements via randomly branching payoffs in differential games. This paper considers dynamically stable cooperative solutions in randomly furcating differential games. Analytically tractable payoff distribution procedures contingent upon specific random events are derived. This new approach widens the application of cooperative differential game theory to problems where future environments are not known with certainty.     

Two-person zero-sum stochastic games

Two-person zero-sum stochastic games with finite state and action spaces are considered. The expected average payoff criterion is introduced. In the special case of single controller games it is shown that the optimal stationary policies and the value of the game can be obtained from the optimal solutions to a pair of dual programs. For multichain structures, a decomposition algorithm is given which produces such optimal stationary policies for both players. In the case of both players controlling the transitions, a generalized game is obtained, the solution of which gives the optimal policies.     

Bias and Overtaking Equilibria for Zero-Sum Stochastic Differential Games

This paper deals with zero-sum stochastic differential games with long-run average payoffs. Our main objective is to give conditions for existence and characterization of bias and overtaking optimal equilibria. To this end, first we characterize the family of optimal average payoff strategies. Then, within this family, we impose suitable conditions to determine the subfamilies of bias and overtaking equilibria. A key step to obtain these facts is to show the existence of solutions to the average payoff optimality equations. This is done by the usual “vanishing discount” approach. Finally, a zero-sum game associated to a certain manufacturing process illustrates our results.     

Computing payoff allocations in the approximate core of linear programming games in a privacy-preserving manner

We investigate privacy-preserving ways of allocating payoffs among players participating in a joint venture, using tools from cooperative game theory and differential privacy. In particular, we examine linear programming games, an important class of cooperative games that model a myriad of payoff sharing problems, including those from logistics and network design. We show that we can compute a payoff allocation in the approximate core of these games in a way that satisfies joint differential privacy.     

Game theoretic formalization of the concept of sustainable development in the hierarchical control systems

The resolution of numerous ecological problems on different levels must be implemented on the base of sustainable development concept that determines the conditions to the state of ecological-economic systems and impacting control actions. Those conditions can’t be realized by themselves and require special collaborative efforts of different agents using both cooperation and hierarchical control. To formalize the inevitable trade-offs it is natural to use game theoretic models. Unfortunately, the main optimality principles of hierarchical control (compulsion, impulsion) are not time consistent and therefore can’t be recommended as the direct base for collective solutions. The most prospective is the conviction method which is formalized as a transition from hierarchy to cooperation and allows a regularization that provides the time consistency. However, in current social conditions other methods of hierarchical control also keep their actuality. To ensure the time consistency of those optimality principles it is necessary to build cooperative differential games on their base. An example of the approach is considered in this paper.     

Stability of the core mapping in games with a countable set of players

Greenberg (1990) and Ray (1989) showed that in coalitional games with a finite set of players the core consists of those and only those payoffs that cannot be dominated using payoffs in the core of a subgame. We extend the definition of the dominance relation to coalitional games with an infinite set of players and show that this result may not hold in games with a countable set of players (even in convex games). But if a coalitional game with a countable set of players satisfies a mild continuity property, its core consists of those and only those payoff vectors which cannot be dominated using payoffs in the core of a subgame.     

Stochastic differential games: Occupation measure based approach

A new approach based on occupation measures is introduced for studying stochastic differential games. For two-person zero-sum games, the existence of values and optimal strategies for both players is established for various payoff criteria. ForN-person games, the existence of equilibria in Markov strategies is established for various cases.     

On the Time Consistency of Equilibria in a Class of Additively separable Differential Games

A class of state-redundant differential games is detected, where players can be partitioned into two groups, so that the state dynamics and the payoff functions of all players are additively separable w.r.t. controls and states of any two players belonging to different groups. We prove that, in this class of games, open-loop Nash and feedback Stackelberg equilibria coincide, both being strongly time consistent. This allows us to bypass the issue of the time inconsistency that typically affects the open-loop Stackelberg solution.     

Zero-Sum Ergodic Semi-Markov Games with Weakly Continuous Transition Probabilities

Zero-sum ergodic semi-Markov games with weakly continuous transition probabilities and lower semicontinuous, possibly unbounded, payoff functions are studied. Two payoff criteria are considered: the ratio average and the time average. The main result concerns the existence of a lower semicontinuous solution to the optimality equation and its proof is based on a fixed-point argument. Moreover, it is shown that the ratio average as well as the time average payoff stochastic games have the same value. In addition, one player possesses an ε-optimal stationary strategy (ε>0), whereas the other has an optimal stationary strategy. A. Jaśkiewicz is on leave from Institute of Mathematics and Computer Science, Wrocław University of Technology. This work is supported by MNiSW Grant 1 P03A 01030.     

Nash bargaining solution under externalities

We define a Nash bargaining solution (NBS) of partition function games. Based on a partition function game, we define an extensive game, which is a propose–respond sequential bargaining game where the rejecter of a proposal exits from the game with some positive probability. We show that the NBS is supported as the expected payoff profile of any stationary subgame perfect equilibrium (SSPE) of the extensive game such that in any subgame, a coalition of all active players forms immediately. We provide a necessary and sufficient condition for such an SSPE to exist. Moreover, we consider extensions to the cases of nontransferable utilities, time discounting and multiple-coalition formation.     

Discrete-time zero-sum Markov games with first passage criteria

In this paper, we deal with two-person zero-sum stochastic games for discrete-time Markov processes. The optimality criterion to be studied is the discounted payoff criterion during a first passage time to some target set, where the discount factor is state-dependent. The state and action spaces are all Borel spaces, and the payoff functions are allowed to be unbounded. Under the suitable conditions, we first establish the optimality equation. Then, using dynamic programming techniques, we obtain the existence of the value of the game and a pair of optimal stationary policies. Moreover, we present the exponential convergence of the value iteration and a ‘martingale characterization’ of a pair of optimal policies. Finally, we illustrate the applications of our main results with an inventory system.     

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.     

From hierarchies to levels: new solutions for games with hierarchical structure

Recently, applications of cooperative game theory to economic allocation problems have gained popularity. In many of these problems, players are organized according to either a hierarchical structure or a levels structure that restrict the players’ possibilities to cooperate. In this paper, we propose three new solutions for games with hierarchical structure and characterize them by properties that relate a player’s payoff to the payoffs of other players located in specific positions in the hierarchical structure relative to that player. To define each solution, we consider a certain mapping that transforms the hierarchical structure into a levels structure, and then we apply the standard generalization of the Shapley value to the class of games with levels structure. Such transformation mappings are studied by means of properties that relate a player’s position in both types of structure.