Skip to main content
main-content

Über dieses Buch

This book focuses on various aspects of dynamic game theory, presenting state-of-the-art research and serving as a testament to the vitality and growth of the field of dynamic games and their applications. The selected contributions, written by experts in their respective disciplines, are outgrowths of presentations originally given at the 13th International Symposium of Dynamic Games and Applications held in Wrocław. The book covers a variety of topics, ranging from theoretical developments in game theory and algorithmic methods to applications, examples, and analysis in fields as varied as environmental management, finance and economics, engineering, guidance and control, and social interaction. Featured throughout are useful tools and valuable resources for researchers, practitioners, and graduate students interested in dynamic games and their applications in applied mathematics, engineering, economics, and management science. Also included in the volume is a special tribute to Arik Melikyan, honoring his memory and the many contributions he made to the field of dynamic games.

Inhaltsverzeichnis

Frontmatter

Dynamic-Differential Games: Theoretical Developments

Frontmatter

On a Structure of the Set of Differential Games Values

The set of value functions of all-possible zero-sum differential games with terminal payoff is characterized. The necessary and sufficient condition for a given function to be a value of some differential game with terminal payoff is obtained.
Yurii Averboukh

Existence and Uniqueness of Disturbed Open-Loop Nash Equilibria for Affine-Quadratic Differential Games

In this note, we investigate the solution of a disturbed quadratic open loop (OL) Nash game, whose underlying system is an affine differential equation and with a finite time horizon. We derive necessary and sufficient conditions for the existence/uniqueness of the Nash/worst-case equilibrium. The solution is obtained either via solving initial/terminal value problems (IVP/TVP, respectively) in terms of Riccati differential equations or solving an associated boundary value problem (BVP). The motivation for studying the case of the affine dynamics comes from practical applications, namely the optimization of gas networks. As an illustration, we applied the results obtained to a scalar problem and compare the numerical effectiveness between the proposed approach and an usual Scilab BVP solver.
Teresa-Paula Azevedo-Perdicoúlis, Gerhard Jank

Fields of Extremals and Sufficient Conditions for a Class of Open-Loop Variational Games

In a 1967 note, Leitmann observed that coordinate transformations may be used to deduce extrema (minimizers or maximizers) of integrals in the simplest problem of the calculus of variations. This has become known as Leitmann’s direct method. Subsequently, in a series of papers, starting in 2001, he revived this approach and extended it in a variety of ways. Shortly thereafter, Carlson presented an important generalization of this approach and connected it to Carathéodory’s equivalent problem method. This in turn was followed by a number of joint papers addressing applications to dynamic games, multiple integrals, and other related topics. Recently, for the simplest problem of the calculus of variations in n-variables, making use of the classical notion of fields of extremals we employed Leitmann’s direct method, as extended by Carlson, to present an elementary proof of Weierstrass’ sufficiency theorem for strong local and global extrema. In this chapter, we extend the notion of a field of extremals to a class of dynamic games and give an extension of the classical Weierstrass sufficiency theorem for open-loop Nash equilibria.
Dean A. Carlson, George Leitmann

Riemann–Liouville, Caputo, and Sequential Fractional Derivatives in Differential Games

There exists a number of definitions of the fractional order derivative. The classical one is the definition by Riemann–Liouville [26, 19, 23, 21]. The Riemann–Liouville fractional derivatives have a singularity at zero. That is why differential equations involving these derivatives require initial conditions of special form lacking clear physical interpretation. These shortcomings do not occur with the regularized fractional derivative in the sense of Caputo. Both the Riemann–Liouville and Caputo derivatives possess neither semigroup nor commutative property. That is why so-called sequential derivatives were introduced by Miller and Ross [19]. In this chapter, we treat sequential derivatives of special form [8, 7, 9]. Their relation to the Riemann–Liouville and Caputo fractional derivatives and to each other is established. Differential games for the systems with the fractional derivatives of Riemann–Liouville, Caputo, as well as with the sequential derivatives are studied. Representations of such systems’ solutions involving the Mittag–Leffler generalized matrix functions [6] are given. The use of asymptotic representations of these functions in the framework of the Method of Resolving Functions [2, 3, 4, 5, 10, 17, 11] allows to derive sufficient conditions for solvability of corresponding game problems. These conditions are based on the modified Pontryagin’s condition [2]. The results are illustrated on a model example where a dynamic system of order π pursues another system of order e.
Arkadii Chikrii, Ivan Matychyn

The Mixed Zero-Sum Stochastic Differential Game in the Model with Jumps

In this chapter, we show that the mixed zero-sum differential-integral game has a value. The main tool is the notion of Backward Stochastic Differential Equations (BSDE for short) with two reflecting right continuous with left limits obstacles (or barriers) when the noise is given by a Brownian motion and a Poisson random measure mutually independent.
Saïd Hamadène, Hao Wang

Discontinuous Value Function in Time-Optimal Differential Games

The article is devoted to the study of the value function in time-optimal differential games. Suppose that some function to be tested is constructed. It is required to prove that this function coincides with the value function of the game. A theorem on sufficient conditions for a tested function to coincide with the value function of the time-optimal differential game under consideration is proved. The theorem covers the case of a discontinuous value function. An application of the theorem is illustrated by an example of a time-optimal second-order differential game with the dynamics of conflict-controlled material point.
Liudmila Kamneva

On Grid Optimal Feedbacks to Control Problems of Prescribed Duration on the Plane

We consider optimal control problems of prescribed duration. A new numerical method is suggested to solve the problems of controlling until a given instant. The solution is based on a generalization of the method of characteristics for Hamilton–Jacobi–Bellman equations. Constructions of optimal grid synthesis are suggested and numerical algorithms solving the problems on the plane are created. Efficiency of the grid feedback is estimated. Results of simulations using the numerical algorithms are exposed.
Nina N. Subbotina, Timofey B. Tokmantsev

Sub- and Super-optimality Principles and Construction of Almost Optimal Strategies for Differential Games in Hilbert Spaces

We prove sub- and superoptimality principles of dynamic programming and show how to use the theory of viscosity solutions to construct almost optimal strategies for two-player, zero-sum differential games driven by abstract evolution equations in Hilbert spaces.
Andrzej Świȩch

Pursuit Evasion Games

Frontmatter

Extremal Aiming in Problems with Unknown Level of Dynamic Disturbance

The procedure of extremal aiming (shift), which is well known in the theory of differential games, is applied to problems where no constraint for dynamic disturbance is given a priori. Problems are considered with linear dynamics, fixed terminal time, and geometric constraint for the useful control. The objective of the useful control is to guide the system to a given terminal set at the termination instant. A method for constructing a feedback control is suggested, which is adaptive with respect to the disturbance level. The method guarantees guiding the system to the terminal set if the disturbance is not larger than some critical level. With that, a “weak” disturbance is parried by a “weak” useful control. A theorem about the guarantee is formulated and proved. The method is applied to the problem of aircraft landing under wind disturbances.
Sergei A. Ganebny, Sergey S. Kumkov, Valerii S. Patsko, Sergei G. Pyatko

A Generalization of the Multi-Stage Search Allocation Game

This chapter deals with a multistage two-person zero-sum game called multistage search allocation game (MSSAG), in which a searcher and a target participate. The searcher distributes his searching resource in a search space to detect the target and the target moves under an energy constraint to evade the searcher. At the beginning of each stage, the searcher is informed of the target’s position and of his moving energy, and the target knows the amount of the searcher’s resource used so far. The game ends when the searcher detects the target. The payoff of the game is the probability of detecting the target during the search. There have been few search games on the MSSAG. We started the discussion on the MSSAG in a previous paper, where we assumed an exponential function for the detection probability of the target. In this chapter, we introduce a general function for the detection probability, aiming at more applicability. We first formulate the problem as a dynamic program. Then, by convex analysis, we propose a general method to solve the problem, and elucidate some general properties of optimal solutions.
Ryusuke Hohzaki

Linear Differential Game with Two Pursuers and One Evader

We study the situation involving two pursuers and one evader in the framework of DGL/1 (Linear Differential Game with bounded controls and first order dynamics for both players). The criterion of the one-on-one DGL/1 game is the terminal miss distance (perpendicular to the initial pursuer/evader Line Of Sight). The pursuer is minimizing this outcome meantime the evader is maximizing the same criterion. We introduce one pursuer more and analyze the changes. A new optimal evasion strategy is then derived to compromise the terminal miss distance with respect to each pursuer. This trade-off strategy and the resulting 2 ×1 No Escape Zone have been computed when the pursuers have the same time-to-go as well as with different times-to-go (equal and different durations of the individual games).
Stéphane Le Ménec

Homicidal Chauffeur Game: History and Modern Studies

“Homicidal chauffeur” game is one of the most well-known model problems in the theory of differential games. “A car” striving as soon as possible to run over “a pedestrian” – this demonstrative model suggested by R. Isaacs turned out to be appropriate for many applied problems. No less remarkable is the fact that the game is a difficult and interesting object for mathematical investigation. This chapter gives a survey of publications on the homicidal chauffeur problem and its modifications.
Valerii S. Patsko, Varvara L. Turova

Collision Avoidance Strategies for a Three-Player Game

Collision avoidance strategies for a game with three players, two pursuers and one evader, are constructed by determining the semipermeable curves that form the barrier. The vehicles are assumed to have the same capabilities, speed, and turn-rates. The game is assumed to be played on a two-dimensional plane. We consider avoidance strategies for a particular form of the game defined in the following way: the pursuers are assumed to act noncooperatively, the evader upon realizing that one (or both) of the pursuers can cause capture, takes an evasive action. We find states from which the pursuer can cause capture following this evasive action by the evader. The envelope of states that can lead to capture is denoted by the barrier set. Capture is assumed to have occurred when one (or both) pursuers have reached within a circle of radius, l, from the evader. The usable part and its boundary are first determined along with the strategy along the boundary. Semipermeable curves are evolved from the boundary. If two curves intersect (they have a common point), the curves are not extended beyond the intersection point. As in the game of two cars, universal curves and the characteristics that terminate and emanate from the universal curve are used to fill voids on the barrier surface. For the particular game (and associated strategies) considered in this paper, numerical simulations suggest that the enlarged set of initial states that lead to capture is closed. As the game considered here is a subset of the more complete game, when two pursuers try to cause capture of a single evader, the avoidance strategies are most likely to belong to the set of strategies for the complete game.
Sriram Shankaran, Dušan M. Stipanović, Claire J. Tomlin

Evolutionary Games

Frontmatter

Imitative Behavior in a Two-Population Model

We study an evolutionary game with two asymmetric populations where agents from each population are randomly paired with members of the other population. We present two imitation models. In the first model, dissatisfaction drives imitation. In the second model, agents imitate the successful. In the first model, we use a simple reviewing rule, while in the second model we use a proportional imitation rule where switching depends on agents comparing their payoffs to others’ payoffs. We show that such imitative behavior can be approximated by a replicator dynamic system. We characterize the evolutionarily stable strategies for a two asymmetric populations normal form game and we show that a mixed strategy is evolutionary stable if and only if it is a strict Nash equilibrium. We offer one clear conclusion: whom an agent imitates is more important than how an agent imitates.
Elvio Accinelli, Juan Gabriel Brida, Edgar J. Sanchez Carrera

ESS, Population Games, Replicator Dynamics: Dynamics and Games if not Dynamic Games

We review some classical definitions and results concerning Evolutionarily Stable Strategies (E.S.S.) with special emphasis on their link to Wardrop equilibrium, and on the nonlinear case where the fitness accrued by an individual depends nonlinearly on the state of the population. On our way, we provide a simple criterion to check that a linear finite dimensional Wardrop equilibrium – or Nash point in the classical E.S.S. literature – satisfies the second-order E.S.S. condition. We also investigate a bifurcation phenomenon in the replicator equation associated with a population game. Finally, we give two nontrivial examples of Wardrop equilibria in problems where the strategies are controls in a dynamic system.
Pierre Bernhard

A Markov Decision Evolutionary Game for Individual Energy Management

We study in this paper a noncooperative game with an infinite number of players that are involved in many local interactions, each involving a randomly selected pair of players. Each player has to choose between an aggressive or a nonaggressive action. The expected lifetime of an individual as well as its expected total fitness during its lifetime (given as the total amount of packets it transmits during the lifetime) depend on the level of aggressiveness (power level) of all actions it takes during its life. The instantaneous reward of each player depends on the level of aggressiveness of his action as well as on that of his opponent. We model this as a Markov Decision Evolutionary Game which is an extension of the evolutionary game paradigm introduced in 1972 by Maynard Smith, and study the structure of equilibrium policies.
Yezekael Hayel, Hamidou Tembine, Eitan Altman, Rachid El-Azouzi

Mutual Mate Choice with Multiple Criteria

This article presents a model of mutual mate search based on two trait measures. One measure describes the attractiveness of an individual and preferences are common according to this measure i.e., each female prefers highly attractive males and all females agree as to which males are attractive. Preferences are homotypic with respect to the second measure, referred to as character i.e., all individuals prefer mates of a similar character. It is assumed that attractiveness is easy to measure, but to observe the character of a prospective partner, it is necessary to court. Hence, on meeting a prospective partner an individual must decide whether to try and court the other. Courtship only occurs by mutual consent. During courtship, individuals observe the character of the prospective partner and then decide whether to mate or not. Mutual acceptance is required for mating to occur. This paper presents the model and outlines a procedure for finding a Nash equilibrium which satisfies a set of criteria based on the concept of subgame perfection. Two examples are presented and it is shown that multiple equilibria may exist.
David M. Ramsey

Cooperative games

The Shapley Value in Cooperative Differential Games with Random Duration

The class of cooperative differential games with random duration is studied in this chapter. The problem of the Shapley Value calculation is examined. As a result, the Hamilton–Jacobi–Bellman equation for the problem with random duration is derived. The Shapley Value calculation method, which uses the obtained equation, is represented by an algorithm. An application of the theoretical results is illustrated with a model of nonrenewable resource extraction by n firms or countries.
Ekaterina Shevkoplyas

Dynamically Consistent Cooperative Solutions in Differential Games with Asynchronous Players’ Horizons

This paper considers cooperative differential games in which players enter the game at different times and have diverse horizons. Moreover, the types of future players are not known with certainty. Dynamically consistent cooperative solutions and analytically tractable payoff distribution mechanisms leading to the realization of these solutions are derived. This analysis widens the application of cooperative differential game theory to problems where the players’ game horizons are asynchronous and the types of future players are uncertain. It represents the first attempt to seek dynamically consistent solution for cooperative games with asynchronous players’ horizons and uncertain types of future players.
David W. K. Yeung

Applications and numerical approaches

Measure-Valued Solutions to a Harvesting Game with Several Players

We consider Nash equilibrium solutions to a harvesting game in one-space dimension. At the equilibrium configuration, the population density is described by a second-order O.D.E. accounting for diffusion, reproduction, and harvesting. The optimization problem corresponds to a cost functional having sublinear growth, and the solutions in general can be found only within a space of measures. In this chapter, we derive necessary conditions for optimality, and provide an example where the optimal harvesting rate is indeed measure valued. We then consider the case of many players, each with the same payoff. As the number of players approaches infinity, we show that the population density approaches a well-defined limit, characterized as the solution of a variational inequality. In the last section, we consider the problem of optimally designing a marine park, where no harvesting is allowed, so that the total catch is maximized.
Alberto Bressan, Wen Shen

Optimal Distributed Uplink Channel Allocation: A Constrained MDP Formulation

Several users share a common channel for transmission, which has an average rate constraint. The packets not yet transmitted are queued. The problem of optimal channel allocation to minimize the average sum queue occupancy subject to this constraint splits into individual Markov decision processes (MDPs) coupled through the Lagrange multiplier for the rate constraint. This multiplier can be computed by an on-line stochastic gradient ascent in a centralized or distributed manner. This gives a stochastic dynamic version of Kelly’s decomposition. A learning scheme is also presented.
Vivek S. Borkar, Joy Kuri

Binomial Approximations for Barrier Options of Israeli Style

We show that prices and shortfall risks of game (Israeli) barrier options in a sequence of binomial approximations of the Black–Scholes (BS) market converge to the corresponding quantities for similar game barrier options in the BS market with path dependent payoffs and we estimate the speed of convergence. The results are also new for usual American style options and they are interesting from a computational point of view, since in binomial markets these quantities can be obtained via dynamic programming algorithms. The paper extends [6] and [3] but requires substantial additional arguments in view of peculiarities of barrier options which, in particular, destroy the regularity of payoffs needed in the above papers.
Yan Dolinsky, Yuri Kifer

A Game of International Climate Policy Solved by a Homogeneous Oracle-Based Method for Variational Inequalities

This paper presents a game-theoretic model for the international negotiations that should take place to renew or extend the Kyoto protocol beyond 2012. These negotiations should lead to a self-enforcing agreement on a burden sharing scheme to realize the necessary global emissions abatement that would preserve the world against irreversible ecological impacts. The model assumes a noncooperative behavior of the parties except for the fact that they will be collectively committed to reach a target on cumulative emissions by the year 2050. The concept of normalized equilibrium, introduced by J.B. Rosen for concave games with coupled constraints, is used to characterize a family of dynamic equilibrium solutions in an m-player game where the agents are (groups of) countries and the payoffs are the welfare gains obtained from a Computable General Equilibrium (CGE) model. The model is solved using an homogeneous version of the oracle-based optimization engine (OBOE) permitting an implicit definition of the payoffs to the different players, obtained through simulations performed with the global CGE model GEMINI-E3.
Laurent Drouet, Alain Haurie, Jean-Philippe Vial, Marc Vielle

Optimal Stopping of a Risk Process with Disruption and Interest Rates

It is a standard approach in classical risk theory to assume a claim process which does not change throughout the whole observation period. Most commonly, encountered models deal with compound Poisson processes. It would be beneficial to investigate more general classes of claim processes with arbitrary distributions of random variables governing inter-occurrence times between losses and loss severities. Further generalization of such framework would be a model allowing for disruptions i.e. changes of such distributions according to some unobservable random variables, representing fluctuating environmental conditions. The question of providing the company with tools allowing for detection of such change and maximizing the returns leads to an optimal stopping problem which we solve explicitly to some extent. Moreover, we provide references to previously examined models as well as numerical examples emphasizing the efficiency of the suggested method.
Elżbieta Z. Ferenstein, Adam Pasternak-Winiarski

Examples in Dynamic Optimal Taxation

One famous result in the theory of capital income taxation is that the optimal tax is zero in equilibrium (Chamley, Econometrica 54(3):607–622, 1986; Judd, J. Public Econ. 28:59–83, 1985) . This result has been derived as an open-loop Stackelberg solution to an appropriate differential game. In this paper, we consider specific feedback solutions to three dynamic models of taxation and find that the optimal tax is generally different from zero.
Mikhail Krastanov, Rossen Rozenov

On a Discounted Inventory Game

We investigate a problem where a company requires a comodity for its production. The demand is random. The company has one main supplier. It can also buy this commodity from the free market, but for a higher price. The supplier produces this commodity and delivers first to the company, but it has also an additional random demand. The problem is considered as a stochastic game with perfect information. We treat pairs of production strategies of a certain structure and show that there is such a pair which is a Nash equilibrium.
Heinz-Uwe Küenle

Time-Consistent Emission Reduction in a Dynamic Leader-Follower Game

IIn this paper, we search for multistage realization of international environmental agreements (IEAs). To analyze countries incentives and results of their interactions, we mathematically represent players’ strategic preferences and apply game-theoretic approach to make predictions about their outcomes. Initial decision on emission reduction is determined by the Stackelberg equilibrium concept. We generalize Barrett’s static ‘emission’ model to a dynamic framework and answer the question ‘how fast should the emission reduction be?’ It appears that sharper abatement is desirable in the early terms, which is similar to the conclusion of the Stern review. As discounting of the future payoffs becomes larger, more immediate reductions should be undertaken by the agreement parties. We show that without incentives from external organizations or governments, such depollution path can lead to a decline of the membership size.
Yulia Pavlova

Fish Wars with Changing Area for a Fishery

In this paper, a discrete-time game model related to a bioresource management problem (fish catching) is considered. The center (referee) shares a reservoir between the competitors, the players (countries) harvest the fish stock on their territory.We consider power population’s growth function and logarithmic players’ profits. Both cases of finite and infinite planning horizon are investigated. The Nash and cooperative equilibria are derived. We investigate a new type of equilibrium – cooperative incentive equilibrium.Hence, the center punishes players for a deviation from the cooperative equilibrium by changing the harvesting territory. A numerical illustration is carried out and results are compared.
Anna Rettieva
Weitere Informationen

Premium Partner

    Bildnachweise