Search Results

This chapter discusses a number of key concepts for extensive form game representation. It first considers a matrix that defines a zero-sum matrix game for which the minimizer has two actions and the maximizer has three actions and shows that the matrix description, by itself, does not capture the information structure of the game and, in fact, other information structures are possible. It then describes an extensive form representation of a zero-sum two-person game, which is a decision tree, the extensive form representation of multi-stage games, and the notions of security policy, security level, and saddle-point equilibrium for a game in extensive form. It also explores the matrix form for games in extensive form, recursive computation of equilibria for single-stage games, feedback games, feedback saddle-point for multi-stage games, and recursive computation of equilibria for multi-stage games. It concludes with a practice exercise with the corresponding solution, along with additional exercises.

This chapter discusses two types of stochastic policy for extensive form game representation as well as the existence and computation of saddle-point equilibrium. For games in extensive form, a mixed policy corresponds to selecting a pure policy in random based on a previously selected probability distribution before the game starts, and then playing that policy throughout the game. It is assumed that the random selections by both players are done statistically independently and the players will try to optimize the expected outcome of the game. After providing an overview of mixed policies and saddle-point equilibria, the chapter considers the behavioral policy for games in extensive form. It also explores behavioral saddle-point equilibrium, behavioral vs. mixed policy, recursive computation of equilibria for feedback games, mixed vs. behavioral order interchangeability, and non-feedback games. It concludes with practice exercises and their corresponding solutions, along with additional exercises.

This chapter explores the concept of mixed policies and how the notions for pure policies can be adapted to this more general type of policies. A pure policy consists of choices of particular actions (perhaps based on some observation), whereas a mixed policy involves choosing a probability distribution to select actions (perhaps as a function of observations). The idea behind mixed policies is that the players select their actions randomly according to a previously selected probability distribution. The chapter first considers the rock-paper-scissors game as an example of mixed policy before discussing mixed action spaces, mixed security policy and saddle-point equilibrium, mixed saddle-point equilibrium vs. average security levels, and general zero-sum games. It concludes with practice exercises with corresponding solutions and an additional exercise.

This chapter discusses a number of key concepts for zero-sum matrix games. A zero-sum matrix game is played by two players, each with a finite set of actions. Player 1 wants to minimize the outcome and Player 2 wants to maximize it. After providing an overview of how zero-sum matrix games are played, the chapter considers the security levels and policies involved and how they can be computed using MATLAB. It then examines the case of a matrix game with alternate play and one with simultaneous play to determine whether rational players will regret their decision to play a security policy. It also describes the saddle-point equilibrium and its relation to the security levels for the two players, as well as the order interchangeability property and computational complexity of a matrix game before concluding with a practice exercise with the corresponding solution and an additional exercise.

This chapter focuses on the computation of mixed saddle-point equilibrium policies. In view of the Minimax Theorem, the mixed saddle-point equilibria can be determined by computing the mixed security policies for both players. For 2 x 2 games, the mixed security policy can be computed in closed form using the “graphical method.” After providing an overview of the graphical method, the chapter considers a systematic numerical procedure to find the linear program solution for mixed saddle-point equilibria and the use of MATLAB's Optimization Toolbox to numerically solve linear programs. It then describes a strictly dominating policy and a “weakly” dominating policy before concluding with practice exercises and their corresponding solutions, along with an additional exercise.

This chapter focuses on the computation of the saddle-point equilibrium of a zero-sum continuous time dynamic game in a state-feedback policy. It begins by considering the solution for two-player zero sum dynamic games in continuous time, assuming a finite horizon integral cost that Player 1 wants to minimize and Player 2 wants to maximize, and taking into account a state feedback information structure. Continuous time dynamic programming can also be used to construct saddle-point equilibria in state-feedback policies. The discussion then turns to continuous time linear quadratic dynamic games and the use of dynamic programming to construct a saddle-point equilibrium in a state-feedback policy for a two-player zero sum differential game with variable termination time. The chapter also describes pursuit-evasion games before concluding with a practice exercise and the corresponding solution.

This chapter focuses on the computation of the saddle-point equilibrium of a zero-sum discrete time dynamic game in a state-feedback policy. It begins by considering solution methods for two-player zero sum dynamic games in discrete time, assuming a finite horizon stage-additive cost that Player 1 wants to minimize and Player 2 wants to maximize, and taking into account a state feedback information structure. The discussion then turns to discrete time dynamic programming, the use of MATLAB to solve zero-sum games with finite state spaces and finite action spaces, and discrete time linear quadratic dynamic games. The chapter concludes with a practice exercise that requires computing the cost-to-go for each state of the tic-tac-toe game, and the corresponding solution.