Handbook of Dynamic Game Theory

This chapter provides a general introduction to the theory of games, as a prelude to other chapters in this Handbook of Dynamic Game Theory which discuss in depth various aspects of dynamic and differential games. The present chapter describes in general terms what game theory is, its historical origins, general formulation (concentrating primarily on static games), various solution concepts, and some key results (again primarily for static games). The conceptual framework laid out here sets the stage for dynamic games covered by other chapters in the Handbook.

This chapter provides an overview of the theory of nonzero-sum differential games, describing the general framework for their formulation, the importance of information structures, and noncooperative solution concepts. Several special structures of such games are identified, which lead to closed-form solutions.

In this chapter, we expose a full theory for infinite-horizon concave differential games with coupled state-constraints. Concave games provide an attractive setting for many applications of differential games in economics, management science and engineering, and state coupling constraints happen to be quite natural features in many of these applications. After recalling the results of Rosen (1965) regarding existence and uniqueness of equilibrium of concave game with coupling contraints, we introduce the classical model of Ramsey and presents the Hamiltonian systems approach for its treatment. Next, we extend to a differential game setting the Hamiltonian systems approach and this formalism to the case of coupled state-constraints. Finally, we extend the theory to the case of discounted rewards.

In this chapter, we build on the concept of a repeated game and introduce the notion of a multistage game. In both types of games, several antagonistic agents interact with each other over time. The difference is that, in a multistage game, there is a dynamic system whose state keeps changing: the controls chosen by the agents in the current period affect the system’s future. In contrast with repeated games, the agents’ payoffs in multistage games depend directly on the state of this system. Examples of such settings range from a microeconomic dynamic model of a fish biomass exploited by several agents to a macroeconomic interaction between the government and the business sector. In some multistage games, physically different decision-makers engage in simultaneous-move competition. In others, agents execute their actions sequentially rather than simultaneously. We also study hierarchical games, where a leader moves ahead of a follower. The chapter concludes with an example of memory-based strategies that can support Pareto-efficient outcomes.

In this chapter, we describe a major part of the theory of zero-sum discrete-time stochastic games. We review all basic streams of research in this area, in the context of the existence of value and uniform value, algorithms, vector payoffs, incomplete information, and imperfect state observation. Also some models related to continuous-time games, e.g., games with short-stage duration, semi-Markov games, are mentioned. Moreover, a number of applications of stochastic games are pointed out. The provided reference list reveals a tremendous progress made in the field of zero-sum stochastic games since the seminal work of Shapley (Proc Nat Acad Sci USA 39:1095–1100, 1953).

This chapter describes a number of results obtained in the last 60 years on the theory of nonzero-sum discrete-time stochastic games. We provide an overview of almost all basic streams of research in this area such as the existence of stationary Nash and correlated equilibria in models on countable and general state spaces, the existence of subgame-perfect equilibria, algorithms, stopping games, and the existence of uniform equilibria. Our survey incorporates several examples of games studied in operations research and economics. In particular, separate sections are devoted to intergenerational games, dynamic Cournot competition and game models of resource extraction. The provided reference list includes not only seminal papers that commenced research in various directions but also exposes recent advances in this field.

The chapter is devoted to two-player, zero-sum differential games, with a special emphasis on the existence of a value and its characterization in terms of a partial differential equation, the Hamilton-Jacobi-Isaacs equation. We discuss different classes of games: in finite horizon, in infinite horizon, and pursuit-evasion games. We also analyze differential games in which the players do not have a full information on the structure of the game or cannot completely observe the state. We complete the chapter by a discussion on differential games depending on a singular parameter: for instance, we provide conditions under which the differential game has a long-time average.

We describe several problems of “robust control” that have a solution using game theoretical tools. This is by no means a general overview of robust control theory beyond that specific purpose nor a general account of system theory with set description of uncertainties.

Evolutionary game theory developed as a means to predict the expected distribution of individual behaviors in a biological system with a single species that evolves under natural selection. It has long since expanded beyond its biological roots and its initial emphasis on models based on symmetric games with a finite set of pure strategies where payoffs result from random one-time interactions between pairs of individuals (i.e., on matrix games). The theory has been extended in many directions (including nonrandom, multiplayer, or asymmetric interactions and games with continuous strategy (or trait) spaces) and has become increasingly important for analyzing human and/or social behavior as well. This chapter initially summarizes features of matrix games before showing how the theory changes when the two-player game has a continuum of traits or interactions become asymmetric. Its focus is on the connection between static game-theoretic solution concepts (e.g., ESS, CSS, NIS) and stable evolutionary outcomes for deterministic evolutionary game dynamics (e.g., the replicator equation, adaptive dynamics).

In distributed architecture control problems, there is a collection of interconnected decision-making components that seek to realize desirable collective behaviors through local interactions and by processing local information. Applications range from autonomous vehicles to energy to transportation. One approach to control of such distributed architectures is to view the components as players in a game. In this approach, two design considerations are the components’ incentives and the rules that dictate how components react to the decisions of other components. In game-theoretic language, the incentives are defined through utility functions, and the reaction rules are online learning dynamics. This chapter presents an overview of this approach, covering basic concepts in game theory, special game classes, measures of distributed efficiency, utility design, and online learning rules, all with the interpretation of using game theory as a prescriptive paradigm for distributed control design.

This chapter provides a general overview of the topic of network games, its application in a number of areas, and recent advances, by focusing on four major types of games, namely, congestion games, resource allocation games, diffusion games, and network formation games. Several algorithmic aspects and methodologies for analyzing such games are discussed, and connections between network games and other relevant topical areas are identified.

In many instances, players find it individually and collectively rational to sign a long-term cooperative agreement. A major concern in such a setting is how to ensure that each player will abide by her commitment as time goes by. This will occur if each player still finds it individually rational at any intermediate instant of time to continue to implement her cooperative control rather than switch to a noncooperative control. If this condition is satisfied for all players, then we say that the agreement is time consistent. This chapter deals with the design of schemes that guarantee time consistency in deterministic differential games with transferable payoffs.

Cooperation in an inter-temporal framework under nontransferable utility/payoffs (NTU) presents a highly challenging and extremely intriguing task to game theorists. This chapter provides a coherent analysis on NTU cooperative dynamic games. The formulations of NTU cooperative dynamic games in continuous time and in discrete time are provided. The issues of individual rationality, Pareto optimality, and an individual player’s payoff under cooperation are presented. Monitoring and threat strategies preventing the breakup of the cooperative scheme are presented. Maintaining the agreed-upon optimality principle in effect throughout the game horizon plays an important role in the sustainability of cooperative schemes. The notion of time (subgame optimal trajectory) consistency in NTU differential games is expounded. Subgame consistent solutions in NTU cooperative differential games and subgame consistent solutions via variable payoff weights in NTU cooperative dynamic games are provided.

This chapter provides a selective survey of dynamic game models of exploitation of natural resources. It covers both renewable resources and exhaustible resources. In relation to earlier surveys (Long, A survey of dynamic games in economics, World Scientific, Singapore, 2010; Long, Dyn Games Appl 1(1):115–148, 2011), the present work includes many references to new developments that appeared after January 2011 and additional suggestions for future research. Moreover, there is a greater emphasis on intuitive explanation.

A differential game is the natural framework of analysis for many problems in environmental economics. This chapter focuses on the game of international pollution control and more specifically on the game of climate change with one global stock of pollutants. The chapter has two main themes. First, the different noncooperative Nash equilibria (open loop, feedback, linear, nonlinear) are derived. In order to assess efficiency, the steady states are compared with the steady state of the full-cooperative outcome. The open-loop Nash equilibrium is better than the linear feedback Nash equilibrium, but a nonlinear feedback Nash equilibrium exists that is better than the open-loop Nash equilibrium. Second, the stability of international environmental agreements (or partial-cooperation Nash equilibria) is investigated, from different angles. The result in the static models that the membership game leads to a small stable coalition is confirmed in a dynamic model with an open-loop Nash equilibrium. The result that in an asymmetric situation transfers exist that sustain full cooperation under the threat that the coalition falls apart in case of deviations is extended to the dynamic context. The result in the static model that farsighted stability leads to a set of stable coalitions does not hold in the dynamic context if detection of a deviation takes time and climate damage is relatively important.

In this chapter, we survey how the methods of dynamic and stochastic games have been applied in macroeconomic research. In our discussion of methods for constructing dynamic equilibria in such models, we focus on strategic dynamic programming, which has found extensive application for solving macroeconomic models. We first start by presenting some prototypes of dynamic and stochastic games that have arisen in macroeconomics and their main challenges related to both their theoretical and numerical analysis. Then, we discuss the strategic dynamic programming method with states, which is useful for proving existence of sequential or subgame perfect equilibrium of a dynamic game. We then discuss how these methods have been applied to some canonical examples in macroeconomics, varying from sequential equilibria of dynamic nonoptimal economies to time-consistent policies or policy games. We conclude with a brief discussion and survey of alternative methods that are useful for some macroeconomic problems.

In this chapter, we provide an overview of continuous-time games in industrial organization, covering classical papers on adjustment costs, sticky prices, and R&D races, as well as more recent contributions on oligopolistic exploitation of renewable productive assets and strategic investments under uncertainty.

Finance is a discipline that encompasses all the essential ingredients of dynamic games, through the involvement of investors, managers, and financial intermediaries as players who have competing interests and who interact strategically over time. This chapter presents various applications of dynamic game models used in the broad area of finance, with the objective of illustrating the scope of possibilities in this field. Both corporate and investment finance applications are presented. Topics covered include game options and their use as financial instruments, bankruptcy games and their association with the valuation of debt and equity, and dynamic game models used to explain empirical observations about the financial decisions made by firms, for instance, on capital structure, dividend payments, and investment choices. In each case, the presentation highlights the game’s various ingredients, the choice of the equilibrium concept, and the solution approach used. The chapter’s focus is on the contributions made by dynamic game models to financial theory and practice.

Marketing is a functional area within a business firm. It includes all the activities that the firm has at its disposal to sell products or services to other firms (wholesalers, retailers) or directly to the final consumers. A marketing manager needs to decide strategies for pricing (toward consumers and middlemen), consumer promotions (discounts, coupons, in-store displays), retail promotions (trade deals), support of retailer activities (advertising allowances), advertising (television, internet, cinemas, newspapers), personal selling efforts, product strategy (quality, brand name), and distribution channels. Our objective is to demonstrate that differential games have proved to be useful for the study of a variety of problems in marketing, recognizing that most marketing decision problems are dynamic and involve strategic considerations. Marketing activities have impacts not only now but also in the future; they affect the sales and profits of competitors and are carried out in environments that change.

In this chapter, some applications of game theory in social network analysis are presented. We first focus on the opinion dynamics of a social network. Viewing the individuals as players of a game with appropriately defined action (opinion) sets and utility functions, we investigate the best response dynamics and its variants for the game, which would in effect represent the evolution of the individuals’ opinions within a social network. The action sets are defined according to the nature of the opinions, which may be continuous, as for the political beliefs of the individuals, or discrete, as for the type of technology adopted by the individuals to use in their daily lives. The utility functions, on the other hand, are to best capture the social behavior of the individuals such as conformity and stubbornness. For every formulation of the game, we characterize the formation of the opinions as time grows. In particular, we determine whether an agreement among all of the individuals is reached, a clustering of opinions occurs, or none of the said cases happens. We further investigate the Nash equilibria of the game and make clear if the game dynamics converges to one of the Nash equilibria. The rate of convergence to the equilibrium, if it is the case, is also obtained. We then turn our attention to decision-making processes (elections) in social networks, where a collective decision (social choice) must be made by multiple individuals (voters) with different preferences over the alternatives (candidates). We argue that the nonexistence of a perfectly fair social choice function that takes all voter preferences into account leads to the emergence of various strategic games in decision-making processes, most notably strategic voting, strategic candidacy, and coalition formation. While the strategic voting would be played among the voters, the other two games would be played among the candidates. We explicitly discuss the games of strategic candidacy and coalition formation.

Applied problems whose investigation involves methods of pursuit-evasion differential games are described. The main focus of this chapter is on time-optimal problems close to R. Isaacs’ “homicidal chauffeur” game and to linear differential games of fixed terminal time with J. Shinar’s space interception problem as the major example. These problems are taken because after a change of variables they can be reduced to models with two state variables. This allows us to provide adequate graphical representations of the level sets of the value functions being obtained numerically and emphasize important peculiarities of these sets. Also, other conflict control problems and control problems with uncertainties being extensively investigated nowadays are briefly outlined.

This chapter surveys some evolutionary games used in biological sciences. These include the Hawk–Dove game, the Prisoner’s Dilemma, Rock–Paper–Scissors, the war of attrition, the Habitat Selection game, predator–prey games, and signaling games.

The development of a homing missile guidance law against an intelligent adversary requires the solution to a differential game. First, we formulate the deterministic homing guidance problem as a linear dynamic system with an indefinite quadratic performance criterion (LQ). This formulation allows the navigation ratio to be greater than three, which is obtained by the one-sided linear-quadratic regulator and appears to be more realistic. However, this formulation does not allow for saturation in the actuators. A deterministic game allowing saturation is formulated and shown to be superior to the LQ guidance law, even though there is no control penalty. To improve the performance of the quadratic differential game solution in the presence of saturation, trajectory-shaping feature is added. Finally, if there are uncertainties in the measurements and process noise, a disturbance attenuation function is formulated that is converted into a differential game. Since only the terminal state enters the cost criterion, the resulting estimator is a Kalman filter, but the guidance gains are a function of the assumed system variances.

This chapter presents a game theoretic framework for studying Stackelberg routing games on parallel transportation networks. A new class of latency functions is introduced to model congestion due to the formation of physical queues, inspired from the fundamental diagram of traffic. For this new class, some results from the classical congestion games literature (in which latency is assumed to be a nondecreasing function of the flow) do not hold. A characterization of Nash equilibria is given, and it is shown, in particular, that there may exist multiple equilibria that have different total costs. A simple polynomial-time algorithm is provided, for computing the best Nash equilibrium, i.e., the one which achieves minimal total cost. In the Stackelberg routing game, a central authority (leader) is assumed to have control over a fraction of the flow on the network (compliant flow), and the remaining flow responds selfishly. The leader seeks to route the compliant flow in order to minimize the total cost. A simple Stackelberg strategy, the non-compliant first (NCF) strategy, is introduced, which can be computed in polynomial time, and it is shown to be optimal for this new class of latency on parallel networks. This work is applied to modeling and simulating congestion mitigation on transportation networks, in which a coordinator (traffic management agency) can choose to route a fraction of compliant drivers, while the rest of the drivers choose their routes selfishly.

This chapter considers three fundamental problems in the general area of communication networks and their relationship to game theory. These problems are (i) allocation of shared bandwidth resources, (ii) routing across shared links, and (iii) scheduling across shared spectrum. Each problem inherently involves agents that experience negative externalities under which the presence of one degrades the utility perceived by others. Two approaches to solving such problems are (i) to find a globally optimal allocation and simply implement it in a fait accompli fashion, and (ii) request information from the competing agents (traffic flows) and construct a mechanism to allocate resources. Often, only the second option is viable, since a centralized solution using complete information might be impractical (or impossible) with many millions of competing flows, each one having private information about the application that it corresponds to. Hence, a game theoretical analysis of these problems is natural. In what follows, we will present results on each problem and characterize the efficiency loss that results from the mechanism employed.

In recent years, the power system has undergone unprecedented changes that have led to the rise of an interactive modern electric system typically known as the smart grid. In this interactive power system, various participants such as generation owners, utility companies, and active customers can compete, cooperate, and exchange information on various levels. Thus, instead of being centrally operated as in traditional power systems, the restructured operation is expected to rely on distributed decisions taken autonomously by its various interacting constituents. Due to their heterogeneous nature, these constituents can possess different objectives which can be at times conflicting and at other times aligned. Consequently, such a distributed operation has introduced various technical challenges at different levels of the power system ranging from energy management to control and security. To meet these challenges, game theory provides a plethora of useful analytical tools for the modeling and analysis of complex distributed decision making in smart power systems.

The goal of this chapter is to provide an overview of the application of game theory to various aspects of the power system including: i) strategic bidding in wholesale electric energy markets, ii) demand-side management mechanisms with special focus on demand response and energy management of electric vehicles, iii) energy exchange and coalition formation between microgrids, and iv) security of the power system as a cyber-physical system presenting a general cyber-physical security framework along with applications to the security of state estimation and automatic generation control. For each one of these applications, first an introduction to the key domain aspects and challenges is presented, followed by appropriate game-theoretic formulations as well as relevant solution concepts and main results.

Security is a critical concern around the world, whether it is the challenge of protecting ports, airports, and other critical infrastructure; interdicting the illegal flow of drugs, weapons, and money; protecting endangered wildlife, forests, and fisheries; or suppressing urban crime or security in cyberspace. Unfortunately, limited security resources prevent full security coverage at all times; instead, we must optimize the use of limited security resources. To that end, we founded a new “security games” framework that has led to building of decision aids for security agencies around the world. Security games are a novel area of research that is based on computational and behavioral game theory while also incorporating elements of AI planning under uncertainty and machine learning. Today security-games-based decision aids for infrastructure security are deployed in the US and internationally; examples include deployments at ports and ferry traffic with the US Coast Guard, for security of air traffic with the US Federal Air Marshals, and for security of university campuses, airports, and metro trains with police agencies in the US and other countries. Moreover, recent work on “green security games” has led our decision aids to be deployed, assisting NGOs in protection of wildlife; and “opportunistic crime security games” have focused on suppressing urban crime. In cyber-security domain, the interaction between the defender and adversary is quite complicated with high degree of incomplete information and uncertainty. Recently, applications of game theory to provide quantitative and analytical tools to network administrators through defensive algorithm development and adversary behavior prediction to protect cyber infrastructures has also received significant attention. This chapter provides an overview of use-inspired research in security games including algorithms for scaling up security games to real-world sized problems, handling multiple types of uncertainty, and dealing with bounded rationality and bounded surveillance of human adversaries.