Subgame Consistent Cooperative Solutions in Stochastic Differential Games

Subgame consistency is a fundamental element in the solution of cooperative stochastic differential games. In particular, it ensures that: (i) the extension of the solution policy to a later starting time and to any possible state brought about by the prior optimal behavior of the players would remain optimal; (ii) all players do not have incentive to deviate from the initial plan. In this paper, we develop a mechanism for the derivation of the payoff distribution procedures of subgame consistent solutions in stochastic differential games with transferable payoffs. The payoff distribution procedure of the subgame consistent solution can be identified analytically under different optimality principles. Demonstration of the use of the technique for specific optimality principles is shown with an explicitly solvable game. For the first time, analytically tractable solutions of cooperative stochastic differential games with subgame consistency are derived.     

Generalized correlated equilibrium for two-person games in extensive form with perfect information

A correlation scheme (leading to a special equilibrium called “soft” correlated equilibrium) is applied for two-person finite games in extensive form with perfect information. Randomization by an umpire takes place over the leaves of the game tree. At every decision point players have the choice either to follow the recommendation of the umpire blindly or freely choose any other action except the one suggested. This scheme can lead to Pareto-improved outcomes of other correlated equilibria. Computational issues of maximizing a linear function over the set of soft correlated equilibria are considered and a linear-time algorithm in terms of the number of edges in the game tree is given for a special procedure called “subgame perfect optimization”.     

On the centipede game with a social norm

In this paper, we present a formulation of the centipede game where inter-subjectivity between players is formalized through random costs that are an increasing function, in the sense of first-order stochastic dominance, of the number of iterations for which the game is played. This injection of a time-dependent social norm, one that also parametrizes player proximity, as an element of each player’s introspective calculations formalizes a setting under which subgame perfection dictates cooperative outcomes.     

基于时隙ALOHA协议的数据传输二人随机博弈模型

在一个给定的拓扑网络中研究关于数据传输的二人随机博弈模型.两个局中人（源节点）试图通过一个公共节点向目的节点传输随机数据包,这些数据包被分为重要的数据包和不重要的数据包两类,假设每个局中人都有一个用于存储数据包的有限容量的缓冲器.通过构造数据传输的成本分摊和奖励体系,把这种动态的冲突控制过程建模为具有有限状态集合的随机博弈,研究局中人在这种随机博弈模型下的非合作以及合作行为.在非合作情形下,给出纳什均衡的求解算法;在合作情形下,选择Shapley值作为局中人支付总和的分配方案,并讨论其子博弈一致性,提出使得Shapley值为子博弈一致的分配补偿程序.     

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     

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.     

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.     

情绪影响下选时博弈模型及其最优策略

依据Quiggin的秩依期望效用理论研究经典选时博弈问题。通过引入可以刻画局中人在博弈中情绪状态的非线性决策权重函数,将RDEU有限策略博弈扩展到连续博弈,构建了RDEU选时博弈模型。基于Riccati微分方程的解法,求出博弈模型中局中人的最优策略。最后,通过数值仿真,分析了不同情绪状态对局中人博弈决策行为的影响。研究发现,情绪对混合策略意义下的局中人最优策略有着显著的影响,在乐观情绪状态下,局中人对混合策略极易产生自信和较高的信任倾向,表现出"风险爱好者"行为;在悲观情绪状态下,局中人往往对混合策略缺乏自信和信任,表现出“风险厌恶者”行为。     

A model of a 2-player stopping game with priority and asynchronous observation

Various models of 2-player stopping games have been considered which assume that players simultaneously observe a sequence of objects. Nash equilibria for such games can be found by first solving the optimal stopping problems arising when one player remains and then defining by recursion the normal form of the game played at each stage when both players are still searching (a 2 × 2 matrix game). The model considered here assumes that Player 1 always observes an object before Player 2. If Player 1 accepts the object, then Player 2 does not see that object. If Player 1 rejects an object, then Player 2 observes it and may choose to accept or reject it. It is shown that such a game can be solved using recursion by solving appropriately defined subgames, which are played at each moment when both players are still searching. In these subgames Player 1 chooses a threshold, such that an object is accepted iff its value is above this threshold. The strategy of Player 2 in this subgame is a stopping rule to be used when Player 1 accepts this object, together with a threshold to be used when Player 1 rejects the object. Whenever the payoff of Player 1 does not depend on the value of the object taken by Player 2, such a game can be treated as two optimisation problems. Two examples are given to illustrate these approaches.     

考虑损失厌恶行为与谈判破裂的Rubinstein谈判博弈研究

本文考虑具有损失厌恶行为与破裂风险的Rubinstein谈判博弈。首先构建子博弈完美均衡,并证明子博弈完美均衡的存在性及唯一性。然后分析子博弈完美均衡的性质,结果表明:参与人受益于对手的损失厌恶行为,而因自身具有损失厌恶行为遭受损失;谈判破裂概率对均衡结果的影响取决于贴现因子与参与人的损失厌恶系数;当谈判破裂的概率趋于零时,极限均衡结果收敛于经典的Rubinstein谈判博弈结果。最后建立了与非对称Nash谈判解的关系,其中参与人的议价能力与自身的损失厌恶水平呈负相关性,与对手的损失厌恶水平呈正相关性;参与人的议价能力依赖于谈判破裂概率与出价时间间隔的比值。     

Sequential share bargaining

This paper presents a new extension of the Rubinstein-St?hl bargaining model to the case with n players, called sequential share bargaining. The bargaining protocol is natural and has as its main feature that the players’ shares in the surplus are determined sequentially rather than simultaneously. The protocol also assumes orderly voting, a restriction on the order in which players respond to a proposal. The bargaining protocol requires unanimous agreement for proposals to be implemented. Unlike all existing bargaining protocols with unanimous agreement, the resulting game has unique subgame perfect equilibrium utilities for any value of the discount factor. The result builds on the analysis of so-called one-dimensional bargaining problems. We show that also one-dimensional bargaining problems have unique subgame perfect equilibrium utilities for any value of the discount factor.     

Observability analysis and model formulation for nonlinear state estimation

A suitable design of state estimators for advanced control requires a detailed and representative mathematical model for capturing the nonlinear process behavior. The system observability, i.e. when the set of measurements provides enough information to estimate all the system states, is not a premise of the derivation of the Kalman filter. However, this propriety can improve the state estimator performance. On the basis of these design tasks, we outline a state estimation tuning strategy for different model formulations and present an algorithm to select the smallest number of measured variables to guarantee the system observability. The Williams–Otto semi-batch reactor was selected as case study, since its model formulation can be represented by two different set of states: (a) a mass basis states set and (b) a mass fraction basis states set. While the process-noise covariance matrix Q in the state estimator can be a diagonal and constant for the first model formulation, the matrix Q is not diagonal and time-varying for the second one due to their highly correlated states. Our results have shown how to convert the tuning matrices between different state definitions so that similar estimation results can be achieved.     

Finitely repeated prisoners’ dilemma experiments without a commonly known end

Using a symmetric two-player prisoners’ dilemma as base game, each player receives a signal for the number of rounds to be played with the same partner. One of these signals is the true number of rounds R while the other is R − 5. Thus both players know that the game has a finite end. They both know that the opponent knows this, but the finite end is not commonly known. As a consequence, both mutual defection and mutual cooperation until the second last round are subgame perfect equilibrium outcomes. We find experimental evidence that many players do in fact cooperate beyond their individual signal round.     

On the notion of perfect Bayesian equilibrium

Often, perfect Bayesian equilibrium is loosely defined by stating that players should be sequentially rational given some beliefs in which Bayes rule is applied “whenever possible.” We argue that there are situations in which it is not clear what “whenever possible” means. Then we provide an elementary definition of perfect Bayesian equilibrium for general extensive games that refines both weak perfect Bayesian equilibrium and subgame perfect equilibrium.     

Stochastic games with non-observable actions

We examine n-player stochastic games. These are dynamic games where a play evolves in stages along a finite set of states; at each stage players independently have to choose actions in the present state and these choices determine a stage payoff to each player as well as a transition to a new state where actions have to be chosen at the next stage. For each player the infinite sequence of his stage payoffs is evaluated by taking the limiting average. Normally stochastic games are examined under the condition of full monitoring, i.e. at any stage each player observes the present state and the actions chosen by all players. This paper is a first attempt towards understanding under what circumstances equilibria could exist in n-player stochastic games without full monitoring. We demonstrate the non-existence of -equilibria in n-player stochastic games, with respect to the average reward, when at each stage each player is able to observe the present state, his own action, his own payoff, and the payoffs of the other players, but is unable to observe the actions of them. For this purpose, we present and examine a counterexample with 3 players. If we further drop the assumption that the players can observe the payoffs of the others, then counterexamples already exist in games with only 2 players.     

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.     

Semi-markov strategies in stochastic games

For a stochastic game with countable state and action spaces we prove, that solutions in the game where all players are restricted to semi-markov strategies are solutions for the unrestricted game. In addition we show, that if all players, except for one, fix a stationary strategy, then the best the remaining player can do, is solving a markov decision problem, corresponding to the fixed stationary strategies.     

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.     

Equilibrium payoffs of dynamic games

We give a characterization of the equilibrium payoffs of a dynamic game, which is a stochastic game where the transition function is either one or zero and players can only use pure actions in each stage. The characterization is in terms of convex combinations of connected stationary strategies; since stationary strategies are not always connected, the equilibrium set may not be convex. We show that subgame perfection may reduce the equilibrium set.     

A non-cooperative foundation for the continuous Raiffa solution

This paper provides a non-cooperative foundation for (asymmetric generalizations of) the continuous Raiffa solution. Specifically, we consider a continuous-time variation of the classic Ståhl–Rubinstein bargaining model, in which there is a finite deadline that ends the negotiations, and in which each player’s opportunity to make proposals is governed by a player-specific Poisson process, in that the rejecter of a proposal becomes proposer at the first next arrival of her process. Under the assumption that future payoffs are not discounted, it is shown that the expected payoffs players realize in subgame perfect equilibrium converge to the continuous Raiffa solution outcome as the deadline tends to infinity. The weights reflecting the asymmetries among the players correspond to the Poisson arrival rates of their respective proposal processes.