Game Theory  

• Taxonomy of games
  • Static game vs. dynamic game
    • static game: it is a single-act (one-stage) game; the players act only once (open-loop control).
    • dynamic game: it is a multi-stage game; at least one player is allowed to use a strategy based on previous actions (closed-loop control).
  • Zero-sum game vs. nonzero-sum game
  • Two players vs. N players
  • Pure strategy vs. mixed strategy
    • pure strategy: deterministic; it consists of only one action.  It is a special case of the mixed strategy where one action is taken with probability 1.
    • mixed strategy: probabilistic; a mixed strategy is actually a probability mass function.  Mixed strategies consist of pure strategies and proper mixed strategies (the underlying probability distribution of which is not one point).
  • Finite game vs. infinite game
    • A finite (infinite) game has a finite (infinite) set of actions.
  • Games with complete information vs. game with incomplete information
    • When some players do not know the payoffs of the others, a game is said to have incomplete information; otherwise, the game is said to have complete information.
    • Bayesian games: model the uncertainty with a probability distribution (assuming the distribution is known to the players)
    • Bayesian equilibrium (or Bayesian Nash equilibrium) is a Nash equilibrium for Bayesian games.
  • Dynamic games 
    • finite state (countable state) vs. continuous state
    • finite action (countable action) vs. continuous action
    • discrete time vs. continuous time 
    • finite horizon vs. infinite horizon (time duration of the game)
    • perfect state-measurements vs. imperfect state-measurements
    • open loop vs. closed loop
  • Noncooperative vs. cooperative
    • noncooperative game: players make decisions independently; communications between players are not allowed.
      • team problem: players have identical payoff function in a nonzero-sum game.
    • cooperative game: communications (e.g., negotiations) between players are allowed; it requires some kind of faith and thereby cooperation.
  • Atomic vs. non-atomic game
    • A continuum of players, say [0,1].
    • a sigma-algebra is defined on the continuum [0,1].
• Action vs. strategy:
  • Action (control): a decision.
  • Strategy (decision rule): a map from the states (environmental information) to the actions.
• Static game:
  • single-act (one-stage) game: the players act only once and the player choose their actions simultaneously.
  • if the strategies are from a discrete set,  the game is in a matrix form.
  • strategic (or normal) form: consists of three elements
    • the set of players
    • the pure strategy space for each player
    • the payoff function for each player,  which maps each combination of the strategies of all players to a utility.
  • if there is only one player, it reduces to mathematical programming.
• Dynamic game: 
  • multi-stage game: at least one player is allowed to use a strategy based on previous actions (closed loop).
  • for continuous time, it is also called differential game.
  • solutions: 
    • Discrete-time: dynamic programming with minimax/max-min cost-to-go function.
    • Continuous-time: Hamilton-Jacobi-Isaacs partial differential equation 
  • if there is only one player, it reduces to optimal control problem (can be solved by dynamic programming).
• Game in extensive form (a dynamic game)
  • used to model the following dynamics
    • the order in which players move
    • what information is available to the players at the time of their decisions
    • evolution of the game
  • the extensive form is a decision tree of multi-players.
• Game with chance moves: chance moves are caused by another play, i.e., mother nature.   For zero-sum games, taking the expectation of the payoff matrices results in a new payoff matrix.  With this new matrix, the problem can be solved as usual.
• Zero-sum game 
  • matrix game (normal form)
  • saddle-point solutions and saddle-point equilibrium: minimax cost  = max-min cost.
  • computation: linear programming
  • a game in extensive form (dynamic game) is characterized by
    • order of play in the decision process
    • information available to the players at the time of their decisions
    • evolution of the game
  • multi-act (open loop) game
    • delayed commitment vs. prior commitment
    • feedback game with behavioral strategies
    • randomized strategies
• Nonzero-sum (general sum) game
  • bimatrix game
  • computation: nonlinear programming
• Cooperative game
  • Side payments are not allowed
  • Side payments are allowed: cooperative games in characteristic function form.
• Optimality
  • Non-cooperative game
    • Saddle-point solution
    • Nash equilibrium solution (Nash solution)
    • Stackelberg equilibrium solution
  • Cooperative game: 
    • Pareto optimality:   no other joint decision of the N players can improve the performance of at least one of them, without degrading the performance of any other player.
• Stackelberg game: a game with one leader and others being followers.
• Tasks:
  • study existence, uniqueness, and derivation of (pure and mixed) saddle point, Nash and Stackelberg equilibria.
• Pursuit-evasion game: zero-sum differential game for which the duration is not fixed a priori.
• H_infinity optimal control vs. dynamic game (use a dynamic game approach to design a minimax controller)
  • The H-infinity optimal controller in frequency domain is different from the minimax controller; in time domain, H-infinity optimal controller is the same as the minimax controller.
  • The design of minimax controllers use dynamic programming where the cost-to-go function is a minimax function.
• Saddle point (existence, uniqueness, and derivation)
  • Noncooperative, two-person, zero-sum, finite, matrix  game 
    • may not have a saddle point solution in pure strategies.  Sufficient condition: 
    • must have at lease one saddle point solution in mixed strategies.  
      • the saddle point solution can be obtained by solving a linear program.
  • vs. nonzero-sum game
  • Two players vs. N players
  • Pure strategy vs. mixed strategy
    • pure strategy: 
    • mixed strategy: 
  • Finite game vs. infinite game
    • A finite (infinite) game has a finite (infinite) set of actions.
  • Games with complete information vs. game with incomplete information
  • Noncooperative vs. cooperative
    • noncooperative game: players make decisions independently; communications between players are not allowed.
    • cooperative game: communications (e.g., negotiations) between players are allowed; it requires some kind of faith and thereby cooperation.
• Nash equilibria (existence, uniqueness, and derivation)
  • Static game vs. dynamic game
    • static game: it is a single-act (one-stage) game; the players act only once (open-loop control).
    • dynamic game: it is a multi-stage game; at least one player is allowed to use a strategy based on previous actions (closed-loop control).
  • Zero-sum game vs. nonzero-sum game
  • Two players vs. N players
  • Pure strategy vs. mixed strategy
    • pure strategy: deterministic; it consists of only one action.
    • mixed strategy: probabilistic; a mixed strategy is actually a probability mass function.
  • Finite game vs. infinite game
    • A finite (infinite) game has a finite (infinite) set of actions.
  • Games with complete information vs. game with incomplete information
  • Dynamic games 
    • finite state (countable state) vs. continuous state
    • finite action (countable action) vs. continuous action
    • discrete time vs. continuous time 
    • finite horizon vs. infinite horizon (time duration of the game)
    • perfect state-measurements vs. imperfect state-measurements
  • Noncooperative vs. cooperative
    • noncooperative game: players make decisions independently; communications between players are not allowed.
    • cooperative game: communications (e.g., negotiations) between players are allowed; it requires some kind of faith and thereby cooperation.
• Stackelberg equilibria (existence, uniqueness, and derivation)
  • Static game vs. dynamic game
    • static game: it is a single-act (one-stage) game; the players act only once (open-loop control).
    • dynamic game: it is a multi-stage game; at least one player is allowed to use a strategy based on previous actions (closed-loop control).
  • Zero-sum game vs. nonzero-sum game
  • Two players vs. N players
  • Pure strategy vs. mixed strategy
    • pure strategy: deterministic; it consists of only one action.
    • mixed strategy: probabilistic; a mixed strategy is actually a probability mass function.
  • Finite game vs. infinite game
    • A finite (infinite) game has a finite (infinite) set of actions.
  • Games with complete information vs. game with incomplete information
  • Dynamic games 
    • finite state (countable state) vs. continuous state
    • finite action (countable action) vs. continuous action
    • discrete time vs. continuous time 
    • finite horizon vs. infinite horizon (time duration of the game)
    • perfect state-measurements vs. imperfect state-measurements
  • Noncooperative vs. cooperative
    • noncooperative game: players make decisions independently; communications between players are not allowed.
      • coalition game: each coalition (group of players) is regarded as one player with the payoff function equal to the sum of payoff functions of its members.
    • cooperative game: communications (e.g., negotiations) between players are allowed; it requires some kind of faith and thereby cooperation.
  • Hierarchical game: a multi-level game with at least two players at each level.
    • noncooperative
    • coalition
    • cooperative
• Relation between optimization and game theory

• There may exist multiple (local) Pareto-optimal solutions.  How to find a global Pareto-optimal solution?

Key Techniques: