Game Theory - Games

• A game is a decision process which involves multiple players that affect the environment and each other.

Games §

• A finite game is a game with a finite number of players in which the number of strategies is finite for all players .

Static Games §

• A static game is a game where players simultaneously and independently make a once and for all decision, after which all outcomes are realized and payoffs are distributed to each player.

• The normal-form game is a tuple

  • A finite set of players
  • A set of actions for each player
  • A set of payoff functions for each player that gives a payoff vale to each combination of the players’ chosen actions. They are functions

• Any 2-player finite normal-form game can be represented as a matrix where

  • Rows represent one player 1’s strategies.
  • Columns represent one of 2’s strategies
  • Entries represent a two element vector representing the players’ payoffs.

Dynamic Games §

• A dynamic game is a game where players take turns and make a decision, potentially based on the choices of other players.

• An extensive-from game is a tuple where

  • Let represent the decision nodes
  • is a finite tree called the game tree with vertices , a unique initial node , a set of terminal nodes . and an immediate predecessor function on which the game rules are represented.
  • is a partition on called the information partition.
    • The information partition consists of information sets which partition the nodes of the game at which player moves with the player properties.
      • If is singleton, that includes only , then player who moves at knows he is at
      • If and both and , then player who moves at does not know whether he is at or , and .
    • The restriction hides any information that can be distinguished about the player’s current state on the board.

• is a set of actions available for each information set which forms a partition over all actions .

• is an action partition associating each node to a single action such that , and where denotes the successor nodes of , is a bijection

• is the set of players. denotes the player Nature who is independent of the strategy of the players.

• is a family of probabilities of the actions of Nature

• denotes the payoff profile function

• A potentially small set of moves can translate into a much larger set of strategies when sequential moves are possible, and when players have knowledge of what preceded their play

• Any extensive-form game can be transformed into a normal-form game by using the set of pure strategies of the extensive form as the set of pure strategies in the normal form and the set of payoff functions is derived from how combinations of pure strategies result in the selection of terminal nodes

  • The pure strategies are represented as follows (for two player games). Let the actions be ordered . Say player 1 has an entry where
    • . The ’s need not be distinct
    • denotes that player 1 plays action in response to player playing

Multistage Games §

• A multistage game is a finite sequence of normal-form stage games in which each stage-game is an independent, well-defined game of complete but imperfect information. The games are played sequentially by players and the total payoffs are evaluated using the sequence of outcomes in the game.

  • Assume: Each stage game takes place in a single time step.
  • Assume: After each stage is completed, all players observe the outcome of the stage and the information structure is common knowledge.

• The total payoff is calculated as a discounted sum of payoffs.

• The game can be represented using a game tree

• Each information set is associated with the history of play from previous stage games

Repeated Game §

• Given a stage game , denotes a finitely repeated game in which the stage game is played times with as the common discount factor.

• For an infinitely repeated game, denoted we can define the following for discount factor .

  The present value given payoffs is given as

  • In this context, we can interpret discounting as a response to an uncertain future — there is a probability that the game will halt.
  • The game is, therefore, infinite in the sense that it is unclear how long the foreseeable future is.

• The average payoff of the given payoffs is

Information §

• An event is common knowledge if:

  • Everyone knows
  • Everyone knows that everyone knows ad infinitum

• Common knowledge allows a strategic framework because we know that everyone will act according to their belief that everyone else has the common knowledge.

• Games of Complete Information require the following for components to be common knowledge among all players of the game

  • All possible actions of all the players
  • All the possible outcomes
  • How each combination of actions of all players affect which outcome will materialize
  • The preferences of each and every player over outcomes.

• Games of Perfect Information are games of complete information where every information set is singleton, and there are no moves of Nature.

• Games of Imperfect Information are games where some information sets contain several nodes or where there are moves of nature.

  • These are games capture two kinds of uncertainty. Exogenous uncertainty - comes from not knowing the move of another player. Endogenous uncertainty - comes from not knowing the realization of a choice of Nature.

• Games of Incomplete Information are games where the players have belief for the other player’s types but these beliefs are not certain.

  • The set of each players and their possible actions are common knowledge.
  • Each player may be associated with one of possibly many payoff functions (each payoff function denotes a type). A type, however, is a general construct that denotes information given to the players, such as their preferences or knowledge about the world.
  • At the beginning of the game, Nature chooses each player’s type from a probability distribution.
  • Each player is assumed to know their preferences
  • Common Prior Assumption The probability distribution over types is common knowledge among the players.

Recall §

• Games of Perfect Recall are those where no player ever forgets information they previously knew .

• Under games of perfect recall, Mixed Strategies and Behavioral Strategies are equivalent.

  • A mixed strategy can be obtained from a behavioral strategy by conditioning on the information set.
  • A behavioral strategy can be obtained from a mixed strategy by “un-conditioning” on the information set.

• Stochastic environments (where the dynamics of the environment change) are games where perfect recall is impossible.

Links §

• Tadelis Ch. 3