Monitoring cooperative equilibria in a stochastic differential game

This paper deals with a class of equilibria which are based on the use of memory strategies in the context of continuous-time stochastic differential games. In order to get interpretable results, we will focus the study on a stochastic differential game model of the exploitation of one species of fish by two competing fisheries. We explore the possibility of defining a so-called cooperative equilibrium, which will implement a fishing agreement. In order to obtain that equilibrium, one defines a monitoring variable and an associated retaliation scheme. Depending on the value of the monitoring variable, which provides some evidence of a deviation from the agreement, the probability increases that the mode of a game will change from a cooperative to a punitive one. Both the monitoring variable and the parameters of this jump process are design elements of the cooperative equilibrium. A cooperative equilibrium designed in this way is a solution concept for a switching diffusion game. We solve that game using the sufficient conditions for a feedback equilibrium which are given by a set of coupled HJB equations. A numerical analysis, approximating the solution of the HJB equations through an associated Markov game, enables us to show that there exist cooperative equilibria which dominate the classical feedback Nash equilibrium of the original diffusion game model.This research was supported by FNRS-Switzerland, NSERC-Canada, FCAR-Quebec.     

Variational inequality formulation for the games with random payoffs

We consider an n-player non-cooperative game with random payoffs and continuous strategy set for each player. The random payoffs of each player are defined using a finite dimensional random vector. We formulate this problem as a chance-constrained game by defining the payoff function of each player using a chance constraint. We first consider the case where the continuous strategy set of each player does not depend on the strategies of other players. If a random vector defining the payoffs of each player follows a multivariate elliptically symmetric distribution, we show that there exists a Nash equilibrium. We characterize the set of Nash equilibria using the solution set of a variational inequality (VI) problem. Next, we consider the case where the continuous strategy set of each player is defined by a shared constraint set. In this case, we show that there exists a generalized Nash equilibrium for elliptically symmetric distributed payoffs. Under certain conditions, we characterize the set of a generalized Nash equilibria using the solution set of a VI problem. As an application, the random payoff games arising from electricity market are studied under chance-constrained game framework.     

Pure subgame-perfect equilibria in free transition games

We consider a class of stochastic games, where each state is identified with a player. At any moment during play, one of the players is called active. The active player can terminate the game, or he can announce any player, who then becomes the active player. There is a non-negative payoff for each player upon termination of the game, which depends only on the player who decided to terminate. We give a combinatorial proof of the existence of subgame-perfect equilibria in pure strategies for the games in our class.     

OPTIMAL RECOVERY OF A SHARED RESOURCE STOCK: A DIFFERENTIAL GAME MODEL WITH EFFICIENT MEMORY EQUILIBRIA

We consider an optimal two-country management of depleted transboundary renewable resources. The management problem is modelled as a differential game, in which memory strategies are used. The countries negotiate an agreement among Pareto efficient harvesting programs. They monitor the evolution of the agreement, and they memorize deviations from the agreement in the past. If the agreement is observed by the countries, they continue cooperation. If one of the countries breaches the contract, then both countries continue in a noncooperative management mode for the rest of the game. This noncooperative option is called a threat policy. The credibility of the threats is guaranteed by their equilibrium property. Transfer or side payments are studied as a particular cooperative management program. Transfer payments allow one country to buy out the other from the fishery for the purpose of eliminating the inefficiency caused by the joint access to the resources. It is shown that efficient equilibria can be reached in a class of resource management games, which allow the use of memory strategies. In particular, continuous time transfer payments (e.g., a share of the harvest) should be used instead of a once-and-for-all transfer payment.     

On stochastic games with additive reward and transition structure

In this paper, we introduce a new class of two-person stochastic games with nice properties. For games in this class, the payoffs as well as the transitions in each state consist of a part which depends only on the action of the first player and a part dependent only on the action of the second player.For the zero-sum games in this class, we prove that the orderfield property holds in the infinite-horizon case and that there exist optimal pure stationary strategies for the discounted as well as the undiscounted payoff criterion. For both criteria also, finite algorithms are given to solve the game. An example shows that, for nonzero sum games in this class, there are not necessarily pure stationary equilibria. But, if such a game possesses a stationary equilibrium point, then there also exists a stationary equilibrium point which uses in each state at most two pure actions for each player.     

On Pareto equilibria in vector-valued extensive form games

In this paper we investigate the existence of Pareto equilibria in vector-valued extensive form games. In particular we show that every vector-valued extensive form game with perfect information has at least one subgame perfect Pareto equilibrium in pure strategies. If one tries to prove this and develop a vector-valued backward induction procedure in analogy to the real-valued one, one sees that different effects may occur which thus have to be taken into account: First, suppose the deciding player at a nonterminal node makes a choice such that the equilibrium payoff vector of the subgame he would enter is undominated under the equilibrium payoff vectors of the other subgames he might enter. Then this choice need not to lead to a Pareto equilibrium. Second, suppose at a nonterminal node a chance move may arise. The combination of the Pareto equilibria of the subgames to give a strategy combination of the entire game need not be a Pareto equilibrium of the entire game.     

连续区间策略下二人零和对策问题研究

考虑连续区间策略下的二人零和对策问题,研究其均衡策略的存在性。首先分析了完全信息下的二人零和对策问题,证明了该问题均衡策略的存在性并给出求解方法。然后进一步研究了收益函数不确定的不完全信息二人零和对策问题,在各局中人都认为对方是风险厌恶型的假设下,分析该类对策纯策略均衡的存在性,并通过研究纯策略均衡存在的充要条件给出判断并寻找纯策略均衡解的方法。最后给出一个数值算例,验证本文所提出方法的可行性。     

Closed-loop Stackelberg solution to a multistage linear-quadratic game

A new solution of a two-person, nonzero-sum Stackelberg game, with linear dynamics, quadratic performance criteion, and closed-loop information available to both players, is presented. This solution is applicable to all problems where the leader is able to influence the objective function of the follower, and this function is strictly convex with respect to the control variable handled by the follower. The resulting equilibrium strategies adapt to the possible nonoptimal behavior of players at some stages of the game. The strategy of the leader has a simple interpretation of a threat formulated by the leader toward the follower and, if necessary, carried out one stage after the follower has played inconsistently with the leader's wishes.     

A markov chain game with dynamic information

Two players, not knowing each other's position, move in a domain and can flash a searchlight. The game terminates when one player is caught within the area illuminated by the flash of the other. However, if this first player is not in this area, then the other player has disclosed his position to the former one, who may be able to exploit this information. The game is considered on a finite state space and in discrete time.The work of the second author was supported by ZWO, The Netherlands Organization for the Advancement of Pure Research, Contract No. B62-239, by the US Air Force Office of Scientific Research, Grant No. AFOSR-85-0245, and by the National Science Foundation, Grant No. NSF-INT-8504097.Visiting Professor at Delft University of Technology during 1986.     

On differential games with Markov perfect triggering

This paper is an attempt to throw some light on the issue of whether defining history-dependent state variables in a differential game does allow for a dynamic play of precommitment equilibria. We suggest the application of trigger strategies in a state-feedback context. Based on a punishment mode in Markov perfect strategies and being able to detect even past deviations followed by histories returning to equilibrium, these subgame-perfect strategies lead to the enforcement of certain outcomes by means of dynamic rules of strategic interaction. The last part of our exposition is devoted to specific game structures under which a trigger equilibrium can be used as well as a punishment mode.     

Bounded rationality, strategy simplification, and equilibrium

It is frequently suggested that predictions made by game theory could be improved by considering computational restrictions when modeling agents. Under the supposition that players in a game may desire to balance maximization of payoff with minimization of strategy complexity, Rubinstein and co-authors studied forms of Nash equilibrium where strategies are maximally simplified in that no strategy can be further simplified without sacrificing payoff. Inspired by this line of work, we introduce a notion of equilibrium whereby strategies are also maximally simplified, but with respect to a simplification procedure that is more careful in that a player will not simplify if the simplification incents other players to deviate. We study such equilibria in two-player machine games in which players choose finite automata that succinctly represent strategies for repeated games; in this context, we present techniques for establishing that an outcome is at equilibrium and present results on the structure of equilibria.     

An orderfield property for stochastic games when one player controls transition probabilities

When the transition probabilities of a two-person stochastic game do not depend on the actions of a fixed player at all states, the value exists in stationary strategies. Further, the data of the stochastic game, the values at each state, and the components of a pair of optimal stationary strategies all lie in the same Archimedean ordered field. This orderfield property holds also for the nonzero sum case in Nash equilibrium stationary strategies. A finite-step algorithm for the discounted case is given via linear programming.This research was partially supported by the Air Force Office of Scientific Research, Grant No. 78-3495. The authors are indebted to Mr. J. Filar for some helpful suggestions in redrafting an earlier version of the paper, especially toward clarifying some obscurities in the proofs of Theorems 3.1 and 4.2 that existed in the earlier versions. This paper is dedicated to Professor C. R. Rao on his 60th birthday.     

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.     

Congestion games with failures

We introduce a new class of games, congestion games with failures (CGFs), which allows for resource failures in congestion games. In a CGF, players share a common set of resources (service providers), where each service provider (SP) may fail with some known probability (that may be constant or depend on the congestion on the resource). For reliability reasons, a player may choose a subset of the SPs in order to try and perform his task. The cost of a player for utilizing any SP is a function of the total number of players using this SP. A main feature of this setting is that the cost for a player for successful completion of his task is the minimum of the costs of his successful attempts. We show that although CGFs do not, in general, admit a (generalized ordinal) potential function and the finite improvement property (and thus are not isomorphic to congestion games), they always possess a pure strategy Nash equilibrium. Moreover, every best reply dynamics converges to an equilibrium in any given CGF, and the SPs’ congestion experienced in different equilibria is (almost) unique. Furthermore, we provide an efficient procedure for computing a pure strategy equilibrium in CGFs and show that every best equilibrium (one minimizing the sum of the players’ disutilities) is semi-strong. Finally, for the subclass of symmetric CGFs we give a constructive characterization of best and worst equilibria.     

Bargaining on whales: A differential game model with pareto optimal equilibria

A two-country differential game model of whaling is used for analysing a dynamic bargaining problem. At a given initial time, the two countries may either continue on a noncooperative mood of play characterized by an open-loop Nash-equilibrium, or negotiate a bargaining solution which we define as the Kalaï-Smorodinsky solution. The cooperative solution calls for a restraint in the whaling efforts which leaves a temptation to cheat for any player. The model shows how, by announcing a credible threat, namely to make whaling an ‘open-access’ fishery, a country can eliminate this temptation to cheat and transform the cooperative solution into an equilibrium.     

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.     

Probabilities of Pure Nash Equilibria in Matrix Games when the Payoff Entries of One Player Are Randomly Selected

The Nash equilibrium in pure strategies represents an important solution concept in nonzero sum matrix games. Existence of Nash equilibria in games with known and with randomly selected payoff entries have been studied extensively. In many real games, however, a player may know his own payoff entries but not the payoff entries of the other player. In this paper, we consider nonzero sum matrix games where the payoff entries of one player are known, but the payoff entries of the other player are assumed to be randomly selected. We are interested in determining the probabilities of existence of pure Nash equilibria in such games. We characterize these probabilities by first determining the finite space of ordinal matrix games that corresponds to the infinite space of matrix games with random entries for only one player. We then partition this space into mutually exclusive spaces that correspond to games with no Nash equilibria and with r Nash equilibria. In order to effectively compute the sizes of these spaces, we introduce the concept of top-rated preferences minimal ordinal games. We then present a theorem which provides a mechanism for computing the number of games in each of these mutually exclusive spaces, which then can be used to determine the probabilities. Finally, we summarize the results by deriving the probabilities of existence of unique, nonunique, and no Nash equilibria, and we present an illustrative example.     

A new approach toN-person,nonzero-sum,linear differential games

It is shown that there exist equilibrium strategies forn-person, nonero-sum, linear differential games if the cost to each player is convex. The approach used is believed to be novel, and is based on a theorem of Fan.This research was supported by the National Research Council of Canada under Grant No. A-7790.     

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.     

基于供需网企业合作博弈模型的演化路径分析

传统企业间合作博弈问题的研究大都是基于合作策略和不合作策略两种情形展开,而与传统研究不同,本文在此基础上将企业间不合作策略细分为竞争策略和中立策略。以多功能开放型供需网企业为研究对象,运用演化博弈理论分析方法,通过构建供需网企业合作演化博弈模型,进而分析供需网企业合作过程中策略的选择以及博弈演化路径问题。研究结果表明:在长期的演化博弈过程中,企业策略的选择情形出现不稳定现象,即出现完全合作、完全不合作或者一方合作而另一方选择不合作策略的多种状态,其演化路径最终稳定于何种情形与模型的支付矩阵和初始参数设置有关。