A deterministic‐control‐based approach to fully nonlinear parabolic and elliptic equations

We show that a broad class of fully nonlinear, second‐order parabolic or elliptic PDEs can be realized as the Hamilton‐Jacobi‐Bellman equations of deterministic two‐person games. More precisely: given the PDE, we identify a deterministic, discrete‐time, two‐person game whose value function converges in the continuous‐time limit to the viscosity solution of the desired equation. Our game is, roughly speaking, a deterministic analogue of the stochastic representation recently introduced by Cheridito, Soner, Touzi, and Victoir. In the parabolic setting with no u‐dependence, it amounts to a semidiscrete numerical scheme whose timestep is a min‐max. Our result is interesting, because the usual control‐based interpretations of second‐order PDEs involve stochastic rather than deterministic control. © 2009 Wiley Periodicals, Inc.     

Risk minimizing portfolios and HJBI equations for stochastic differential games

In this paper, we consider the problem to find a market portfolio that minimizes the convex risk measure of the terminal wealth in a jump diffusion market. We formulate the problem as a two player (zero-sum) stochastic differential game. To help us find a solution, we prove a theorem giving the Hamilton–Jacobi–Bellman–Isaacs (HJBI) conditions for a general zero-sum stochastic differential game in a jump diffusion setting. We then use the theorem to study particular risk minimization problems. Finally, we extend our approach to cover general stochastic differential games (not necessarily zero-sum), and we obtain similar HJBI equations for the Nash equilibria of such games.     

Semidefinite programming for min–max problems and games

We consider two min–max problems (1) minimizing the supremum of finitely many rational functions over a compact basic semi-algebraic set and (2) solving a 2-player zero-sum polynomial game in randomized strategies with compact basic semi-algebraic sets of pure strategies. In both problems the optimal value can be approximated by solving a hierarchy of semidefinite relaxations, in the spirit of the moment approach developed in Lasserre (SIAM J Optim 11:796–817, 2001; Math Program B 112:65–92, 2008). This provides a unified approach and a class of algorithms to compute Nash equilibria and min–max strategies of several static and dynamic games. Each semidefinite relaxation can be solved in time which is polynomial in its input size and practice on a sample of experiments reveals that few relaxations are needed for a good approximation (and sometimes even for finite convergence), a behavior similar to what was observed in polynomial optimization.     

Book review

The concept of antagonistic games for classical discrete control problems is applied and new classes of zero-sum dynamic games on networks are formulated and studied. Polynomial-time algorithms for solving max–min paths problem on networks are proposed and their applications (which might occur within certain financial applications) for solving max–min control problems and determining optimal strategies in zero-sum cyclic games are described. In addition max–min control problems with infinite time horizons which lead to cyclic games are studied and polynomial-time algorithm for solving zero value cyclic games is proposed.     

Games with externalities: games in coalition configuration function form

In this paper we introduce a model of cooperative game with externalities which generalizes games in partition function form by allowing players to take part in more than one coalition. We provide an extension of the Shapley value (1953) to these games, which is a generalization of the Myerson value (1977) for games in partition function form. This value is derived by considering an adaptation of an axiomatic characterization of the Myerson value (1977).     

Discounted,positive, and noncooperative stochastic games

In this paper, we consider the stochastic games ofShapley and prove under certain conditions the stochastic game has a value and both players have optimal strategies. We also prove a similar result for noncooperative stochastic games.     

Stationary,completely mixed and symmetric optimal and equilibrium strategies in stochastic games

In this paper, we address various types of two-person stochastic games—both zero-sum and nonzero-sum, discounted and undiscounted. In particular, we address different aspects of stochastic games, namely: (1) When is a two-person stochastic game completely mixed? (2) Can we identify classes of undiscounted zero-sum stochastic games that have stationary optimal strategies? (3) When does a two-person stochastic game possess symmetric optimal/equilibrium strategies? Firstly, we provide some necessary and some sufficient conditions under which certain classes of discounted and undiscounted stochastic games are completely mixed. In particular, we show that, if a discounted zero-sum switching control stochastic game with symmetric payoff matrices has a completely mixed stationary optimal strategy, then the stochastic game is completely mixed if and only if the matrix games restricted to states are all completely mixed. Secondly, we identify certain classes of undiscounted zero-sum stochastic games that have stationary optima under specific conditions for individual payoff matrices and transition probabilities. Thirdly, we provide sufficient conditions for discounted as well as certain classes of undiscounted stochastic games to have symmetric optimal/equilibrium strategies—namely, transitions are symmetric and the payoff matrices of one player are the transpose of those of the other. We also provide a sufficient condition for the stochastic game to have a symmetric pure strategy equilibrium. We also provide examples to show the sharpness of our results.     

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.     

Maximum principle for differential games of forward–backward stochastic systems with applications

This paper is concerned with a maximum principle for both zero-sum and nonzero-sum games. The most distinguishing feature, compared with the existing literature, is that the game systems are described by forward–backward stochastic differential equations. This kind of games is motivated by linear-quadratic differential game problems with generalized expectation. We give a necessary condition and a sufficient condition in the form of maximum principle for the foregoing games. Finally, an example of a nonzero-sum game is worked out to illustrate that the theories may find interesting applications in practice. In terms of the maximum principle, the explicit form of an equilibrium point is obtained.     

Pursuit–Evasion Games with incomplete information in discrete time

Pursuit–Evasion Games (in discrete time) are stochastic games with nonnegative daily payoffs, with the final payoff being the cumulative sum of payoffs during the game. We show that such games admit a value even in the presence of incomplete information and that this value is uniform, i.e. there are e{\epsilon}-optimal strategies for both players that are e{\epsilon}-optimal in any long enough prefix of the game. We give an example to demonstrate that nonnegativity is essential and expand the results to Leavable Games.     

Totally balanced combinatorial optimization games

Combinatorial optimization games deal with cooperative games for which the value of every subset of players is obtained by solving a combinatorial optimization problem on the resources collectively owned by this subset. A solution of the game is in the core if no subset of players is able to gain advantage by breaking away from this collective decision of all players. The game is totally balanced if and only if the core is non-empty for every induced subgame of it.?We study the total balancedness of several combinatorial optimization games in this paper. For a class of the partition game [5], we have a complete characterization for the total balancedness. For the packing and covering games [3], we completely clarify the relationship between the related primal/dual linear programs for the corresponding games to be totally balanced. Our work opens up the question of fully characterizing the combinatorial structures of totally balanced packing and covering games, for which we present some interesting examples: the totally balanced matching, vertex cover, and minimum coloring games. Received: November 5, 1998 / Accepted: September 8, 1999?Published online February 23, 2000     

Zero-sum risk-sensitive stochastic games for continuous time Markov chains

We study infinite horizon discounted-cost and ergodic-cost risk-sensitive zero-sum stochastic games for controlled continuous time Markov chains on a countable state space. For the discounted-cost game, we prove the existence of value and saddle-point equilibrium in the class of Markov strategies under nominal conditions. For the ergodic-cost game, we prove the existence of values and saddle point equilibrium by studying the corresponding Hamilton-Jacobi-Isaacs equation under a certain Lyapunov condition.     

STRUCTURES OF VALUES FOR SET GAMES RESTRICTED BY PARTITION SYSTEM

§1IntroductionA cooperative game with transferable utility(TU)is a pair(N,v),where N is anonempty,finite set and v∶2N→R is a characteristic function defined on the power set ofN satisfying v()∶=0.LetCGdenote the set of all cooperative TU-games with anarbitrary player set.An element of N(notation:i∈N)and a nonempty subset S of N(notation:S N or S∈2Nwith S≠)are called a player and coalition respectively,andthe associated real number v(S)is called the worth of coalition S to be in…     

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.     

Perturbation theory for games in normal form and stochastic games

In this paper, the effect on values and optimal strategies of perturbations of game parameters (payoff function, transition probability function, and discount factor) is studied for the class of zero-sum games in normal form and for the class of stationary, discounted, two-person, zero-sum stochastic games.A main result is that, under certain conditions, the value depends on these parameters in a pointwise Lipschitz continuous way and that the sets of -optimal strategies for both players are upper semicontinuous multifunctions of the game parameters.Extensions to general-sum games and nonstationary stochastic games are also indicated.     

Stochastic Games with Average Payoff Criterion

We study two-person stochastic games on a Polish state and compact action spaces and with average payoff criterion under a certain ergodicity condition. For the zero-sum game we establish the existence of a value and stationary optimal strategies for both players. For the nonzero-sum case the existence of Nash equilibrium in stationary strategies is established under certain separability conditions. Accepted 9 January 1997     

Communication, complexity, and evolutionary stability

In games with costless preplay communication, some strategies are more complex than others in the sense that they induce a finer partition of the set of states of the world. This paper shows that if the concept of evolutionary stability, which is argued to be a natural solution concept for communication games, is modified to take lexicographic complexity preferences into account, then for a class of games of common interest only communication strategies that induce payoff-dominant Nash outcomes of the underlying game are stable. Received April 1998/Final version September 1998