Extensive form of a game

from Wikipedia, the free encyclopedia
Game tree with two single-element sets of information

The extensive form of a game , shortly extensive form is, in game theory a representation form of games , in contrast to the normal form of the game into account the timing of decisions and to this end a game tree called tree structure used.

definition

The extensive form of a game is a mathematically formal description of a game, with which the possible course of the game according to the rules of the game can be fully characterized. Specifically, it concerns the following information:

  • The number of players.
  • For each score ( called position ) the information about
    • whose turn it is
    • which moves are available for the player concerned and
    • On the basis of which information (e.g. knowledge of his own cards and those that have already been played) he has to make his decision.
  • For final positions, who won how much (a player's profit is called the payout ).
  • In the case of random moves, how likely the possible outcomes are and how they may be correlated with one another .

The formalization of the extensive form is based on a mathematical graph , where the nodes correspond to the positions and the edges to the possibilities of movement. Specifically, this includes formalization

  • a tree (this is a connected graph without loops),
  • a node that represents the root of the tree and symbolizes the starting position of the game ( making the tree a directed graph ),
  • a set of players (including, if applicable, a fictional player who "decides" the random moves),
  • an assignment that assigns a player to each node (who moves in this position , i.e. selects an allowed move),
  • for each player a partition of the nodes in which he pulls, in information sets,
  • an assignment that assigns a payout for each player to each end node.

The information sets each contain those nodes (also referred to as decision nodes ) that are indistinguishable for the drawing player due to the information currently available to him - for example, because the previous branch within the game tree on a decision by another player that is not recognizable for the drawing player is based. All nodes of an information set must therefore contain the same number of possible moves. Within the extensive form, the options for moving all nodes of an information set must be identified in a consistent manner (for example by numbering). Within a graphical representation of the game tree, the nodes of the individual information sets are usually summarized as shown above. Because of this representation, one also speaks of information areas .

A game of which all sets of information contain only one element at a time is called a game with perfect information . Some authors also speak of perfect information. As is usual with most board games , a player who moves then always knows the entire history of the current game. Counterexamples are card games in which the players only know their own cards. Such games are examples of games with imperfect (or imperfect ) information.

Even a game with imperfect information can have complete information , which means that the players are sure about the rules of the game.

Properties of games and their presentation

The difference between the representation in extensive form and that in normal form is that in the extensive form a game is modeled as a sequence of decisions by the players, while in the normal form all decisions are viewed as taking place simultaneously.

Sequential structures of games require solution concepts that go beyond the Nash equilibrium . In particular, Nash equilibria can contain threats that are implausible given the sequential structure of the game. One way to rule out such equilibria is to use the concept of subgame-perfect equilibria .

Individual evidence

  1. ↑ Jörg Bewersdorff : Luck, Logic and Bluff: Mathematics in Play - Methods, Results and Limits , Vieweg + Teubner Verlag, 5th edition 2010, ISBN 3834807753 , doi: 10.1007 / 978-3-8348-9696-4 , p. IX .
  2. ^ Christian Rieck : Spieltheorie , Gabler, Wiesbaden 1993, ISBN 340916801X , pp. 84–97.

literature

  • Alós-Ferrer, Carlos / Ritzberger, Klaus (2005): Trees and Decisions , in: Economic Theory 25 (4): 763–798.
  • Fudenberg, Drew / Tirole, Jean (1991): Game Theory . Cambridge (Mass.): MIT Press.
  • Gibbons, Robert (1999): A Primer in Game Theory . Harlow: Pearson Education.
  • Eichberger, Jürgen (1993): Game Theory for Economists . New York: Academic Press.